Giáo án ppt chuyên đề KHMT 11 kết nối: Bài 5 Thực hành thiết kế thuật toán theo kĩ thuật đệ quy

Giáo án ppt chuyên đề Tin học khoa học máy tính 11 kết nối tri thức: Bài 5 Thực hành thiết kế thuật toán theo kĩ thuật đệ quy. Bài giảng thiết kế hiện đại, sáng tạo giúp tiết học thêm phần thú vị, giúp giáo viên tiết kiệm thời gian nhưng vẫn có thể ứng dụng công nghệ vào công tác giảng dạy.

Bài khác

Nội dung chi tiết

... Còn nữa ...

MỜI CÁC EM

ĐẾN VỚI TIẾT HỌC!

KHỞI ĐỘNG

Hãy phân tích một số ưu, nhược điểm của việc áp dụng kĩ thuật đệ quy trong lập trình?

BÀI 5: THỰC HÀNH

THIẾT KẾ THUẬT TOÁN THEO KĨ THUẬT ĐỆ QUY

NHIỆM VỤ 1.

THUẬT TOÁN SẮP XẾP CHÈN

Nhiệm vụ:

Viết chương trình mô tả thuật toán sắp xếp chèn theo kĩ thuật đệ quy.

  • Thuật toán sắp xếp chèn được mô tả ngắn gọn như sau:

1 for i in range(1,n):

2 Chèn phần tử A[i] vào vị trí đúng của các phần tử A[0],A[1],…,A[i-1]

  • Giả sử gọi insertionSortRec (A,i) là thao tác tương ứng với dòng 2 của mô tả trên, khi đó chương trình được viết lại như sau:

1 for insertionSortRec(A,i):

2 if i > 0:

3 insertionSortRec(A,i-1)

4 chèn phần tử A[i] vào vị trí đúng của các phần tử A[0],A[1],…,A[i-1]

  • Chương trình có thể được viết thành như sau:

1 def insertionSortRec(A,i):

2 if I > 0:

3 insertionSortRec(A,i-1)

4 value = A[i]

5 j = i-1

6 while j >= 0 and A[j] > value:

7 A[j+1] = A[j]

8 j = j – 1

9 A[j+1] = value

Lời gọi đệ quy của hàm là:

insertionSortRec(A,len(A)-1)

NHIỆM VỤ 2.

CHUYỂN SỐ THẬP PHÂN SANG HỆ ĐẾM NHỊ PHÂN

STTnn//2n%2
11151
2521
3210
4101
50 Số nhị phân cần tìm là 1011, dãy các số dư theo thứ tự ngược lại, từ dưới lên trên.

Bảng 5.1. Các bước triển khai nhị phân n = 11

LƯU Ý

a) Nếu bỏ qua các lệnh 4, 5 thì kết quả sẽ luôn chèn chữ số 0 vào đầu xâu kết quả, dẫn đến không chính xác, vì vậy cần có thêm các lệnh 4, 5.

b) Nếu bỏ qua lệnh 4, 5 và lệnh 3 thay thế bằng lệnh return “” thì kết quả sẽ đúng với mọi n > 0 nhưng sai với n = 0.

  • Gọi binary (n) là xâu biểu diễn khai triển nhị phân của số tự nhiên n. Khi đó theo cách phân tích trên chúng ta có công thức truy hồi sau:
binary(n) = binary(n//2) + str(n%2)

Quá trình thực hiện

Biến đổi n = n//2

Ghi lại số dư n%2

Quá trình kết thúc khi n = 0

Kết quả là dãy các số dư được ghép lại theo thứ tự ngược từ dưới lên

  • Chương trình có thể được viết như sau:

1 def binary(n):

2 if n == 0:

3 return “0”

4 elif n == 1:

5 Return “1”

6 else:

7 return binary(n//2) + str(n%2)

LUYỆN TẬP

Câu 1. Viết chương trình đệ quy giải quyết nhiệm vụ 2 nhưng với yêu cầu đầu ra của hàm là một dãy (list) các số 0 và 1.

Câu 2. Viết hàm decimal(s) chuyển đổi xâu nhị phân s sang số thập phân tương ứng. Ví dụ nếu đầu vào là "10" thì kết quả 2, nều đầu vào "1011" thì kết quả là 11. Yêu cầu viết theo kĩ thuật đệ quy.

HƯỚNG DẪN THỰC HIỆN

1

1 def binary(n):

2 if n == 0:

3 return [0]

4 elif n == 1:

5 Return [1]

6 else:

7 return binary(n//2) + str(n%2)

2

1 def decimal(s,n):

2 if n == 0:

3 return 0

4 elif n == 1:

5 return int(s[0])

6 else:

7 return 2*decimal(s,n-1) + int(s[n-1])

Lời gọi đệ quy là:

decimal(s,len(s))

VẬN DỤNG

--------------- Còn tiếp ---------------

Đầy đủ Giáo án ppt chuyên đề tin học khoa học máy tính 11 kết nối tri thức

Tài liệu cùng môn học

Tài liệu khác

Xem thêm nội dung

CHUYÊN ĐỀ 1. THỰC HÀNH THIẾT KẾ THUẬT TOÁN THEO KĨ THUẬT ĐỆ QUY

CHUYÊN ĐỀ 2. THỰC HÀNH THIẾT KẾ THUẬT TOÁN THEO KĨ THUẬT CHIA ĐỂ TRỊ

CHUYÊN ĐỀ 3. THỰC HÀNH THIẾT KẾ THUẬT TOÁN THEO KĨ THUẬT DUYỆT