Giáo án điện tử chuyên đề Khoa học máy tính 11 kết nối Bài 3: Thực hành giải toán theo kĩ thuật đệ quy

CHÀO MỪNG CÁC EM ĐẾN VỚI BÀI HỌC NGÀY HÔM NAY!

KHỞI ĐỘNG

Khi áp dụng kĩ thuật đệ quy để giải các bài toán, theo em cần phải đặc biệt lưu ý đến điều gì?

BÀI 3: THỰC HÀNH GIẢI TOÁN THEO KĨ THUẬT ĐỆ QUY

NHIỆM VỤ 1

Bài toán biến đổi số nhị phân sang số thập phân

Yêu cầu: Đầu vào của bài toán là một xâu nhị phân bất kì, ở đây xâu nhị phân được hiểu là xâu chỉ bao gồm các chữ số 0 và 1. Xâu này là biểu diễn của một số tự nhiên n trong hệ đếm nhị phân. Yêu cầu của bài toán là tìm số thập phân tương ứng với biểu diễn nhị phân của xâu đầu vào. Bài toán cần giải bằng kĩ thuật đệ quy.

HƯỚNG DẪN

• Phân tích: Gọi s là xâu kí tự nhị phân đầu vào có độ dài n:
• Vì các kí tự của xâu có thể biểu diễn thông qua chỉ số nên xâu s có thể được coi là một dãy các chữ số 0, 1 như sau:
• Chúng ta sẽ thiết kế hàm dec(s, n) để tính giá trị số thập phân có biểu diễn nhị phân theo dãy (1).

• Nếu M được biểu diễn bằng số nhị phân dạng a0a1…an-1 thì ta có công thức:
• Biến đổi công thức, ta có:
• Nếu gọi dec(s, n) là số thập phân cần tìm của dãy nhị phân (1) thì công thức (2) sẽ cho chúng ta công thức truy hồi sau:
• Áp dụng công thức (3) vào bài toán, hàm đệ quy dec(s,n) được thiết kế như sau:

Công thức

Công thức tại dòng lệnh 5 ở trên chính là công thức (3)

Lệnh gọi hàm như sau:

dec(s, len(s))

NHIỆM VỤ 2

Tìm ước chung lớn nhất của hai số nguyên không âm

Yêu cầu: Cho trước hai số nguyên a, b không âm, không đồng thời bằng 0. Ước chung lớn nhất của hai số này sẽ kí hiệu là ƯCLN(a,b). Bài toán yêu cầu tính gcd(a,b) với a,b cho trước.

HƯỚNG DẪN

• Nếu a = b thì ƯCLN sẽ chính là các số này, ngược lại nếu hai số này không bằng nhau, ví dụ a > b thì chúng ta biền đổi số lớn hơn bằng cách trừ đi số kia, ví dụ đặt a = a - b.
• Quá trình như vậy sẽ tiếp tục và kết thúc khi a = b, chúng ta tìm được ƯCLN.

Cách tính tự nhiên

Bảng 3.1. Quy trình tính toán hàm gcd()

Cách tính nhanh theo thuật toán Euclid

1

Nếu b = 0 thì gcd(a, 0) = a.

2

Nếu b > 0 thì gcd(a, b) = gcd(b,a mod b).

LUYỆN TẬP

• Câu 1. Mô tả các bước tính gcd(93, 60).
• Câu 2. Viết chương trình chuyển đổi số nhị phân sang số 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 thực hiện

Các bước tính gcd(93,60) như sau.

1

• Bước 1. gcd(93,60) = gcd(60, 33)
• Bước 2, gcd(60,33) = gcd(33,27)
• Bước 3. gcd(33,27) = gcd(27,6)
• Bước 4. gcd(27,6) = gcd(6,3)
• Bước 5. gcd(6,3) = gcd(3,0) = 3

Chương trình này tương tự chương trình của Nhiệm vụ 1.

2

VẬN DỤNG

Bà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 như sau:

Hãy viết lại chương trình trên theo kĩ thuật đệ quy.

HƯỚNG DẪN

VẬN DỤNG

Bài 2. Thiết lập chương trì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 sử dụng kĩ thuật đệ quy.

HƯỚNG DẪN

Bà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á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 lạ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 lớp, kết quả phải lưu ra tệp ketqua.out. Em hãy giúp bạn An 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à ra của bài toán sẽ như sau:

HƯỚNG DẪN

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