(Trang 16)
| Sau bài này em sẽ:
|
|
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ì? |
NHIỆM VỤ 1
Bài toán biến đổi số nhị phân sang số thập phân
Đầ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 có độ dài n:
S = s0 s1 ... sn-1.
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:
s[0], s[1], ..., s[n - 1]. (1)
Chúng ta sẽ thiết kế hàm dec(s, n) để tính giá trị số thập phân của biểu diễn nhị phân theo dãy (1).
Với n = 1 thì s chỉ là một kí tự, do đó hàm dec(s, 1) sẽ chính là int(s[0]).
Với n > 1 là trường hợp tổng quát của bài toán. Chúng ta đã biết nếu số M được biểu diễn bằng số nhị phân dạng a₀a₁...aₙ-₁ thì ta phải có công thức sau:
M = a₀2ⁿ⁻¹ + a₁2ⁿ⁻² + ... + aₙ-₂2¹ + aₙ-₁
Biến đổi công thức trên, chúng ta có:
M = 2(a02n-2 + a12n-3 + ... + an-321+an-2) + an-1. (2)
Rõ ràng biểu thức trong ngoặc trên chính là biểu diễn thập phân của số nhị phân a₀, a₁, ..., aₙ-₂.
Vậy 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:
dec(s, n) = 2dec(s, n - 1) + int(s[n - 1]). (3)
Áp dụng công thức (3) vào bài toán của chúng ta, chú ý rằng đầu vào của s là xâu nhị phân nên các phần tử s[k] đều là chữ số. Hàm đệ quy dec(s,n) được thiết kế như sau:
(Trang 17)
1 def dec(s, n):
2 if n == 1:
3 return int(s)
4 else:
5 return 2 * dec(s, n - 1) + int(s[n - 1])
Lưu ý: Công thức tại dòng 5 ở trên chính là công thức (3). Lệnh gọi hàm đệ quy như sau:
dec(s, len(s))
NHIỆM VỤ 2
Tìm UCLN của hai số nguyên không âm
Cho 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à UCLN (a, b) hay gcd(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:
1. Cách tính tự nhiên
Có rất nhiều cách tìm ƯCLN của hai số a, b cho trước. Cách tìm đơn giản như sau: 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 cho 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. Ví dụ cần tính gcd(12, 9), chúng ta thực hiện theo các bước sau:
1. gcd(12, 9) = gcd(3, 9).
2. gcd(3, 9) = gcd(3, 6).
3. gcd(3, 6) = gcd(3, 3).
4. gcd(3, 3) = 3.
Việc thiết lập chương trình tính gcd(a, b) theo cách trên (theo cả hai phương án đệ quy và không đệ quy) sẽ được cho trong phần vận dụng.
2. Cách tính nhanh theo thuật toán Euclid
Chúng ta sẽ tìm hiểu một cách tính khác cho bài toán trên. Cách tính này do nhà toán học Euclid đưa ra vào năm 300 trước công nguyên và là một trong những thuật toán nổi tiếng nhất. Để tìm hiểu thuật toán Euclid tính ƯCLN, chúng ta quan sát quy trình tính toán hàm gcd() theo bảng 3.1 dựa vào ví dụ tính gcd(12, 9).
Bảng 3.1. Quy trình tính toán gcd()
| STT | a | b | a%b | Ghi chú |
| 1 | 12 | 9 | 3 | |
| 2 | 9 | 3 | 0 | |
| 3 | 3 | 0 | Nếu b = 0 thì dừng lại, thông báo ƯCLN = a |
Kết quả thu được gcd(12, 9) = 3.
Dễ thấy thuật toán Euclid sẽ nhanh hơn thuật toán tự nhiên đã mô tả ở trên.
(Trang 18)
Thuật toán tìm ƯCLN có thể mô tả theo hai quy luật sau:
1. Nếu b = 0 thì gcd(a, 0) = a.
2. Nếu b > 0 thì gcd(a, b) = gcd(b, a mod b).
Từ các phân tích trên chúng ta thiết lập chương trình đệ quy tính gcd(a, b) theo thuật toán Euclid như sau:
1 def gcd(a, b):
2 if b == 0:
3 return a
4 else:
5 return gcd(b, a % b)
LUYỆN TẬP
1. Mô tả các bước tính gcd(93, 60).
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.
VẬN DỤNG
1. Bài toán tính UCLN của hai số nguyên dương a, b có một cách tính khác như sau:
1 def gcd(a, b):
2 while a != b:
3 if a < b:
4 b = b - a
5 else:
6 a = a - b
7 return a
Hãy viết lại chương trình trên theo kĩ thuật đệ quy.
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 đệ quy.
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 cho Ban Giám hiệu tên và chiều cao của bạn thấp nhất và kết quả lại một 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:
| chieucao.inp | ketqua.out |
| Nguyễn Việt Hà 1.75 Bùi Quang Mơ 1.66 Trương Thị Lộc 1.50 Trần Văn Hoá 1.78 | Trương Thị Lộc 1.50 Trần Văn Hoá 1.78 |
