Bài 5: Thực hành thiết kế thuật toán theo kĩ thuật đệ quy - Chuyên đề Tin học 11 Kết nối tri thức

Câu 1

Trả lời câu hỏi khởi động trang 25 Chuyên đề Tin học 11 Kết nối tri thức

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

Lời giải chi tiết:

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

Luyện tập Câu 1

Trả lời câu hỏi Luyện tập 1 trang 27 Chuyên đề Tin học 11 Kết nối tri thức

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

Lời giải chi tiết:

Để chuyển từ số thập phân sang nhị phân bằng đệ quy, ta cần thực hiện các bước sau:

1. Chia số thập phân cho 2 và lấy phần nguyên và phần dư

2. Lưu phần dư vào danh sách

3. Lặp lại cho đến khi số thập phân bằng 0

Ví dụ, nếu ta gọi hàm decimal_to_binary(13), kết quả trả về sẽ là [1, 1, 0, 1], tương ứng với số nhị phân 1101.

Luyện tập Câu 2

Trả lời câu hỏi Luyện tập 2 trang 27 Chuyên đề Tin học 11 Kết nối tri thức

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.

Lời giải chi tiết:

Để chuyển đổi một xâu nhị phân sang số thập phân, ta có thể sử dụng thuật toán đệ quy như sau:

- Nếu xâu chỉ có một kí tự, trả về giá trị của kí tự đó (0 hoặc 1).

- Ngược lại, lấy kí tự đầu tiên của xâu và nhân với 2^(độ dài xâu - 1), sau đó cộng với giá trị của phần còn lại của xâu đã bỏ đi kí tự đầu tiên.

Ví dụ:

Vận dụng Câu 1

Trả lời câu hỏi Vận dụng 1 trang 27 Chuyên đề Tin học 11 Kết nối tri thức

Cho trước dãy số A = A[0], A[1], ...., A[n - 1]. Cặp phần tử (A[i], A[j]) được gọi là nghịch đảo nếu i < j nhưng A[i] > A[j]. Viết chương trình đếm số các cặp phần tử nghịch đảo của dãy A

a) Viết chương trình không đệ quy.

b) Viết chương trình theo kĩ thuật đệ quy

Lời giải chi tiết:

a) Viết chương trình không đệ quy, sử dụng 2 vòng lặp

b) Viết chương trình theo kĩ thuật đệ quy, khá phức tạp

Vận dụng Câu 2

Trả lời câu hỏi Vận dụng 2 trang 27 Chuyên đề Tin học 11 Kết nối tri thức

Thiết kế thuật toán cho bài toán tính giá trị của đa thức

 (1)

Ở đây, đầu vào là các giá trị x,a0,a1,...,an

Gọi A = [a0,a1,...,an] là dãy các hệ số của đa thức (1).

Công thức (1) có thể viết lại với định nghĩa hàm F(A, x, n) như sau:

 (2)

Lời giải chi tiết:

Thuật toán:

- Nếu i = 0, ta trả về a[0]

- Ngược lại, ta tính giá trị của đa thức đến bậc i - 1, rồi nhân với x, cuối cùng cộng với a[i].

Viết chương tình và kiểm tra kết quả như sau:

Thu được kết quả: