Giải chi tiết chuyên đề tin học định hướng Khoa học máy tính 11 Kết nối mới bài 3 Thực hành giải toán theo kĩ thuật đệ quy
Giải bài 3 Thực hành giải toán theo kĩ thuật đệ quy sách Chuyên đề Tin học 11 định hướng Khoa học máy tính kết nối tri thức. Phần đáp án chuẩn, hướng dẫn giải chi tiết cho từng bài tập có trong chương trình học của sách giáo khoa. Hi vọng, các em học sinh hiểu và nắm vững kiến thức bài học.
KHỞI ĐỘNG
Câu hỏi: Khi áp dụng kỹ thuật đệ quy để giải các bài toán, cần phải đặc biệt lưu ý đến điều gì?
Hướng dẫn trả lời:
Khi áp dụng kĩ thuật giải đệ quy để giải các bài toán, cần lưu ý đến điều kiện kết thúc đệ quy: Cần xác định điều kiện để thoát khỏi vòng lặp đệ quy, nếu không sẽ gây ra lỗi vô hạn lặp lại.
Luyện tập
Câu hỏi 1. Mô tả các bước tĩnh gcd(93,60).
Hướng dẫn trả lời:
STT | a | b | a%b | Ghi chú |
1 | 93 | 60 | 33 |
|
2 | 60 | 33 | 27 |
|
3 | 33 | 27 | 6 |
|
4 | 27 | 6 | 3 |
|
5 | 6 | 3 | 0 |
|
6 | 3 | 0 |
| Nếu b = 0 thì dừng lại, thông báo ƯCLN = a |
Câu hỏi 2. Viết chương trình chuyên đổi số nhị phân sang hệ thập phân (tương tự nhiệm vụ 1) nhưng dãy nhị phân đầu vào được cho dưới dạng một dây (list) các số 0 và 1. Ví dụ nêu dãy đầu vào là A = [1, 1, 1, 1, 1, 1, 1] thì kết quả đầu ra là 127.
Hướng dẫn trả lời:
Để chuyển đổi số nhị phân sang hệ thập phân, ta có thể sử dụng kĩ thuật đệ quy như sau
Vận dụng
Câu hỏi 1. Bài toán tính ƯCLN của hai số nguyên dương a, b có một cách tính khác nhau sau:
- def gcd(a,b)
- while a !=b:
- if a<b
- else :
- a = a-b
- return a
Hãy viết lại chương trình trên theo kĩ thuật đệ quy.
Hướng dẫn trả lời:
Câu hỏi 2. Thiết lập chương trình tính hàm gcd(a,b) - ƯCLN của các số nguyên không âm a, b theo thuật toán Euclid nhưng không đệ quy.
Hướng dẫn trả lời:
Bước cơ sở của đệ quy sẽ là trường hợp a hoặc b bằng 0, trong trường hợp này kết quả sẽ là giá trị khác 0 của a hoặc b.
Câu hỏi 3. Lớp An tiến hành đo chiều cao của cả lớp, kết quả lưu vào một tệp có tên chieucao.inp, trong tệp ghi lần lượt họ tên của các bạn trong lớp và chiều cao tương ứng. Thầy hiệu trưởng yêu cầu tổng kết và gửi cho Ban giám hiệu tên và chiều cao của bạn thấp nhất và cao nhất trong lớp. Viết chương trình giải quyết yêu cầu này theo kĩ thuật đệ quy. Ví dụ thông tin đầu vào và đầu ra của bài toán sẽ như sau:
| chieucao.inp | ketqua.out |
Nguyễn Việt Hà 1.75 Bùi Quang Mơ 1.86 Trương Thị Lộc 1.50 Trần văn Hóa 1.78 | Trương Thị Lộc 1.50 Trần Văn Hóa 1.78 |
Hướng dẫn trả lời:
Để giải quyết yêu cầu này, ta có thể sử dụng kĩ thuật đệ quy để tìm chiều cao lớn nhất và nhỏ nhất trong danh sách.
Đầu tiên, ta đọc danh sách chiều cao từ tệp chieucao.inp. Tiếp theo, ta sử dụng hàm đệ quy để tìm chiều cao lớn nhất và nhỏ nhất.
