Giáo án điện tử chuyên đề Khoa học máy tính 11 kết nối Bài 5: Thực hành thiết kế thuật toán theo kĩ thuật đệ quy
Tải giáo án điện tử Chuyên đề học tập Tin học 11 - Khoa học máy tính (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ộ giáo án chuyên đề được thiết kế sinh động, đẹp mắt. Thao tác tải về đơn giản, dễ dàng sử dụng và chỉnh sửa. Thầy, cô kéo xuống để xem chi tiết.
Xem: => Giáo án tin học 11 theo định hướng khoa học máy tính kết nối tri thức
Xem toàn bộ: Giáo án điện tử chuyên đề Tin học 11 - Khoa học máy tính Kết nối tri thức
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
| STT | n | n//2 | n%2 |
| 1 | 11 | 5 | 1 |
| 2 | 5 | 2 | 1 |
| 3 | 2 | 1 | 0 |
| 4 | 1 | 0 | 1 |
| 5 | 0 | 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 ---------------
Trên chỉ là 1 phần của giáo án. Giáo án khi tải về có đầy đủ nội dung của bài. Đủ nội dung của học kì I + học kì II
Hệ thống có đầy đủ các tài liệu:
- Giáo án word (350k)
- Giáo án Powerpoint (400k)
- Trắc nghiệm theo cấu trúc mới (200k)
- Đề thi cấu trúc mới: ma trận, đáp án, thang điểm..(200k)
- Phiếu trắc nghiệm câu trả lời ngắn (200k)
- Trắc nghiệm đúng sai (250k)
- Lý thuyết bài học và kiến thức trọng tâm (200k)
- File word giải bài tập sgk (150k)
- Phiếu bài tập để học sinh luyện kiến thức (200k)
Nâng cấp lên VIP đê tải tất cả ở tài liệu trên
- Phí nâng cấp VIP: 800k
=> Chỉ gửi 450k. Tải về dùng thực tế. Nếu hài lòng, 1 ngày sau mới gửi phí còn lại
Cách nâng cấp:
- Bước 1: Chuyển phí vào STK: 1214136868686 - cty Fidutech - MB(QR)
- Bước 2: Nhắn tin tới Zalo Fidutech - nhấn vào đây để thông báo và nhận tài liệu
Xem toàn bộ: Giáo án điện tử chuyên đề Tin học 11 - Khoa học máy tính Kết nối tri thức
ĐẦY ĐỦ GIÁO ÁN CÁC BỘ SÁCH KHÁC
GIÁO ÁN WORD LỚP 11 KẾT NỐI TRI THỨC
GIÁO ÁN POWERPOINT LỚP 11 KẾT NỐI TRI THỨC
GIÁO ÁN CHUYÊN ĐỀ LỚP 11 KẾT NỐI TRI THỨC
GIÁO ÁN DẠY THÊM 11 KẾT NỐI TRI THỨC
CÁCH ĐẶT MUA:
Liên hệ Zalo: Fidutech - nhấn vào đây