Giáo trình Toán rời rạc - Chương 1: Thuật toán

2, ab2.2
2
 = 
(110)2.1.2
2
 = (11000)2. Để tìm tích, hãy cộng (110)2, (0000)2 và (11000)2. Từ đó ta có 
ab= (11110)2. 
Thủ tục trên được mô tả bằng đoạn giả mã sau: 
procedure nhân (a,b: positive integers) 
 for j := 0 to n-1 
 begin 
 if bj = 1 then cj := a được dịch đi j chỗ 
 else cj := 0 
 end 
{c0, c1,..., cn-1 là các tích riêng phần} 
 p := 0 
 for j := 0 to n-1 
 p := p + cj 
{p là giá trị của tích ab} 
 Thuật toán trên tính tích của hai số nguyên a và b bằng cách cộng các tích riêng 
phần c0, c1, c2, ..., cn-1. Khi bj=1, ta tính tích riêng phần cj bằng cách dịch khai triển nhị 
phân của a đi j bit. Khi bj=0 thì không cần có dịch chuyển nào vì cj=0. Do đó, để tìm tất 
cả n số nguyên abj.2
j
 với j=0, 1, ..., n-1, đòi hỏi tối đa là 
0 + 1 + 2 + ... + n1 = 
2
)1( nn
phép dịch chỗ. Vì vậy, số các dịch chuyển chỗ đòi hỏi là O(n2). 
 17 
 Để cộng các số nguyên abj từ j=0 đến n1, đòi hỏi phải cộng một số nguyên n bit, 
một số nguyên n+1 bit, ... và một số nguyên 2n bit. Ta đã biết rằng mỗi phép cộng đó 
đòi hỏi O(n) phép cộng bit. Do đó, độ phức tạp của thuật toán này là O(n2). 
1.5. THUẬT TOÁN ĐỆ QUY. 
1.5.1. Khái niệm đệ quy: 
 Đôi khi chúng ta có thể quy việc giải bài toán với tập các dữ liệu đầu vào xác 
định về việc giải cùng bài toán đó nhưng với các giá trị đầu vào nhỏ hơn. Chẳng hạn, bài 
toán tìm UCLN của hai số a, b với a > b có thể rút gọn về bài toán tìm ƯCLN của hai số 
nhỏ hơn, a mod b và b. Khi việc rút gọn như vậy thực hiện được thì lời giải bài toán ban 
đầu có thể tìm được bằng một dãy các phép rút gọn cho tới những trường hợp mà ta có 
thể dễ dàng nhận được lời giải của bài toán. Ta sẽ thấy rằng các thuật toán rút gọn liên 
tiếp bài toán ban đầu tới bài toán có dữ liệu đầu vào nhỏ hơn, được áp dụng trong một 
lớp rất rộng các bài toán. 
Định nghĩa: Một thuật toán được gọi là đệ quy nếu nó giải bài toán bằng cách rút gọn 
liên tiếp bài toán ban đầu tới bài toán cũng như vậy nhưng có dữ liệu đầu vào nhỏ hơn. 
Thí dụ 10: Tìm thuật toán đệ quy tính giá trị an với a là số thực khác không và n là số 
nguyên không âm. 
 Ta xây dựng thuật toán đệ quy nhờ định nghĩa đệ quy của an, đó là an+1=a.an với 
n>0 và khi n=0 thì a
0=1. Vậy để tính an ta quy về các trường hợp có số mũ n nhỏ hơn, 
cho tới khi n=0. 
procedure power (a: số thực khác không; n: số nguyên không âm) 
 if n = 0 then power(a,n) := 1 
 else power(a,n) := a * power(a,n-1) 
Thí dụ 11: Tìm thuật toán đệ quy tính UCLN của hai số nguyên a,b không âm và a > b. 
procedure UCLN (a,b: các số nguyên không âm, a > b) 
 if b = 0 then UCLN (a,b) := a 
 else UCLN (a,b) := UCLN (a mod b, b) 
Thí dụ 12: Hãy biểu diễn thuật toán tìm kiếm tuyến tính như một thủ tục đệ quy. 
 Để tìm x trong dãy tìm kiếm a1,a2,...,an trong bước thứ i của thuật toán ta so sánh 
x với ai. Nếu x bằng ai thì i là vị trí cần tìm, ngược lại thì việc tìm kiếm được quy về dãy 
có số phần tử ít hơn, cụ thể là dãy ai+1,...,an. Thuật toán tìm kiếm có dạng thủ tục đệ quy 
như sau. 
 Cho search (i,j,x) là thủ tục tìm số x trong dãy ai, ai+1,..., aj. Dữ liệu đầu vào là bộ 
ba (1,n,x). Thủ tục sẽ dừng khi số hạng đầu tiên của dãy còn lại là x hoặc là khi dãy còn 
lại chỉ có một phần tử khác x. Nếu x không là số hạng đầu tiên và còn có các số hạng 
khác thì lại áp dụng thủ tục này, nhưng dãy tìm kiếm ít hơn một phần tử nhận được bằng 
cách xóa đi phần tử đầu tiên của dãy tìm kiếm ở bước vừa qua. 
 18 
procedure search (i,j,x) 
 if ai = x then loacation := i 
 else if i = j then loacation := 0 
 else search (i+1,j,x) 
Thí dụ 13: Hãy xây dựng phiên bản đệ quy của thuật toán tìm kiếm nhị phân. 
 Giả sử ta muốn định vị x trong dãy a1, a2, ..., an bằng tìm kiếm nhị phân. Trước 
tiên ta so sánh x với số hạng giữa a[(n+1)/2]. Nếu chúng bằng nhau thì thuật toán kết thúc, 
nếu không ta chuyển sang tìm kiếm trong dãy ngắn hơn, nửa đầu của dãy nếu x nhỏ hơn 
giá trị giữa của của dãy xuất phát, nửa sau nếu ngược lại. Như vậy ta rút gọn việc giải 
bài toán tìm kiếm về việc giải cũng bài toán đó nhưng trong dãy tìm kiếm có độ dài lần 
lượt giảm đi một nửa. 
procedure binary search (x,i,j) 
m := [(i+j)/2] 
if x = am then loacation := m 
else if (x < am and i < m) then binary search (x,i,m-1) 
else if (x > am and j > m) then binary search (x,m+1,j) 
else loacation := 0 
1.5.2. Đệ quy và lặp: 
Thí dụ 14. Thủ tục đệ quy sau đây cho ta giá trị của n! với n là số nguyên dương. 
procedure factorial (n: positive integer) 
 if n = 1 then factorial(n) := 1 
 else factorial(n) := n * factorial(n-1) 
Có cách khác tính hàm giai thừa của một số nguyên từ định nghĩa đệ quy của nó. Thay 
cho việc lần lượt rút gọn việc tính toán cho các giá trị nhỏ hơn, ta có thể xuất phát từ giá 
trị của hàm tại 1và lần lượt áp dụng định nghĩa đệ quy để tìm giá trị của hàm tại các số 
nguyên lớn dần. Đó là thủ tục lặp. 
procedure iterative factorial (n: positive integer) 
 x := 1 
 for i := 1 to n 
 x := i * x 
{x là n!} 
Thông thường để tính một dãy các giá trị được định nghĩa bằng đệ quy, nếu dùng 
phương pháp lặp thì số các phép tính sẽ ít hơn là dùng thuật toán đệ quy (trừ khi dùng 
các máy đệ quy chuyên dụng). Ta sẽ xem xét bài toán tính số hạng thứ n của dãy 
Fibonacci. 
procedure fibonacci (n: nguyên không âm) 
 19 
 if n = 0 the fibonacci(n) := 0 
 else if n = 1 then fibonacci(n) := 1 
 else fibonacci(n) := fibonacci(n - 1) + fibonacci(n - 2) 
Theo thuật toán này, để tìm fn ta biểu diễn fn = fn-1 + fn-2. Sau đó thay thế cả hai số 
này bằng tổng của hai số Fibonacci bậc thấp hơn, cứ tiếp tục như vậy cho tới khi f0 và f1 
xuất hiện thì được thay bằng các giá trị của chúng theo định nghĩa. Do đó để tính fn cần 
fn+1-1 phép cộng. 
 Bây giờ ta sẽ tính các phép toán cần dùng để tính fn khi sử dụng phương pháp 
lặp. Thủ tục này khởi tạo x là f0 = 0 và y là f1 = 1. Khi vòng lặp được duyệt qua tổng của 
x và y được gán cho biến phụ z. Sau đó x được gán giá trị của y và y được gán giá trị 
của z. Vậy sau khi đi qua vòng lặp lần 1, ta có x = f1 và y = f0 + f1 = f2. Khi qua vòng lặp 
lần n-1 thì x = fn-1. Như vậy chỉ có n – 1 phép cộng được dùng để tìm fn khi n > 1. 
procedure Iterative fibonacci (n: nguyên không âm) 
 if n = 0 then y := 0 
 else 
 begin 
 x := 0 ; y := 1 
 for i := 1 to n - 1 
 begin 
 z := x + y 
 x := y ; y := z 
 end 
 end 
{y là số Fibonacci thứ n} 
Ta đã chỉ ra rằng số các phép toán dùng trong thuật toán đệ quy nhiều hơn khi 
dùng phương pháp lặp. Tuy nhiên đôi khi người ta vẫn thích dùng thủ tục đệ quy hơn 
ngay cả khi nó tỏ ra kém hiệu quả so với thủ tục lặp. Đặc biệt, có những bài toán chỉ có 
thể giải bằng thủ tục đệ quy mà không thể giải bằng thủ tục lặp. 
BÀI TẬP CHƯƠNG I: 
1. Tìm một số nguyên n nhỏ nhất sao cho f(x) là O(xn) đối với các hàm f(x) sau: 
a) f(x) = 2x
3
 + x
2
log x. 
b) f(x) = 2x
3
 + (log x)
4
. 
c) f(x) = 
1
1
3
24


x
xx
 20 
d) f(x) = 
1
log5
4
5


x
xx
. 
2. Chứng minh rằng 
a) x
2
 + 4x + 7 là O(x
3), nhưng x3 không là O(x2 +4x + 17). 
b) xlog x là O(x
2), nhưng x2 không là O(xlog x). 
3. Cho một đánh giá big-O đối với các hàm cho dưới đây. Đối với hàm g(x) trong đánh 
giá f(x) là O(g(x)), hãy chọn hàm đơn giản có bậc thấp nhất. 
a) nlog(n
2
 + 1) + n
2
logn. 
b) (nlogn + 1)
2
 + (logn + 1)(n
2
 + 1). 
c) 
22 nnn
n
 . 
4. Cho Hn là số điều hoà thứ n: 
Hn = 1 + 
2
1
 + 
3
1
 + ... + 
n
1
Chứng minh rằng Hn là O(logn). 
5. Lập một thuật toán tính tổng tất cả các số nguyên trong một bảng. 
6. Lập thuật toán tính xn với x là một số thực và n là một số nguyên. 
7. Mô tả thuật toán chèn một số nguyên x vào vị trí thích hợp trong dãy các số nguyên 
a1, a2, ..., an xếp theo thứ tự tăng dần. 
8. Tìm thuật toán xác định vị trí gặp đầu tiên của phần tử lớn nhất trong bảng liệt kê các 
số nguyên, trong đó các số này không nhất thiết phải khác nhau. 
9. Tìm thuật toán xác định vị trí gặp cuối cùng của phần tử nhỏ nhất trong bảng liệt kê 
các số nguyên, trong đó các số này không nhất thiết phải khác nhau. 
10. Mô tả thuật toán đếm số các số 1 trong một xâu bit bằng cách kiểm tra mỗi bit của 
xâu để xác định nó có là bit 1 hay không. 
11. Thuật toán tìm kiếm tam phân. Xác định vị trí của một phần tử trong một bảng liệt 
kê các số nguyên theo thứ tự tăng dần bằng cách tách liên tiếp bảng liệt kê đó thành ba 
bảng liệt kê con có kích thước bằng nhau (hoặc gần bằng nhau nhất có thể được) và giới 
hạn việc tìm kiếm trong một bảng liệt kê con thích hợp. Hãy chỉ rõ các bước của thuật 
toán đó. 
12. Lập thuật toán tìm trong một dãy các số nguyên số hạng đầu tiên bằng một số hạng 
nào đó đứng trước nó trong dãy. 
 21 
13. Lập thuật toán tìm trong một dãy các số nguyên tất cả các số hạng lớn hơn tổng tất 
cả các số hạng đứng trước nó trong dãy. 
14. Cho đánh giá big-O đối với số các phép so sánh được dùng bởi thuật toán trong Bài 
tập 10. 
15. Đánh giá độ phức tạp của thuật toán tìm kiếm tam phân được cho trong Bài tập 11. 
16. Đánh giá độ phức tạp của thuật toán trong Bài tập 12. 
17. Mô tả thuật toán tính hiệu của hai khai triển nhị phân. 
18. Lập một thuật toán để xác định a > b, a = b hay a < b đối với hai số nguyên a và b ở 
dạng khai triển nhị phân. 
19. Đánh giá độ phức tạp của thuật toán tìm khai triển theo cơ số b của số nguyên n qua 
số các phép chia được dùng. 
20. Hãy cho thuật toán đệ quy tìm tổng n số nguyên dương lẻ đầu tiên. 
21. Hãy cho thuật toán đệ quy tìm số cực đại của tập hữu hạn các số nguyên. 
22. Mô tả thuật toán đệ quy tìm xn mod m với n, x, m là các số nguyên dương. 
23. Hãy nghĩ ra thuật toán đệ quy tính 
n
a2 trong đó a là một số thực và n là một số 
nguyên dương. 
24. Hãy nghĩ ra thuật toán đệ quy tìm số hạng thứ n của dãy được xác định như sau: 
a0=1, a1 = 2 và an = an-1 an-2 với n = 2, 3, 4, ... 
25. Thuật toán đệ quy hay thuật toán lặp tìm số hạng thứ n của dãy trong Bài tập 24 là 
có hiệu quả hơn?