1.4. SỐ NGUYÊN VÀ THUẬT TOÁN.
1.4.1. Thuật toán Euclide:
Phương pháp tính ước chung lớn nhất của hai số bằng cách dùng phân tích các số nguyên đó ra thừa số nguyên tố là không hiệu quả. Lý do l à ở chỗ thời gian phải tiêu tốn cho sự phân tích đó. Dưới đây là phương pháp hiệu quả hơn để tìm ước số chung lớn nhất, gọi là thuật toán Euclide. Thuật toán này đã biết từ thời cổ đại. Nó mang tên nhà toán học cổ Hy lạp Euclide, ng ười đã mô tả thuật toán này trong cuốn sách “Những yếu tố” nổi tiếng của ông. Thuật toán Euclide dựa vào 2 mệnh đề sau đây.
Mệnh đề 1 (Thuật toán chia): Cho a và b là hai số nguy ên và b 0. Khi đó tồn tại duy nhất hai số nguyên q và r sao cho a = bq+r, 0 r < |b|.
Trong đẳng thức trên, b được gọi là số chia, a được gọi là số bị chia, q được gọi là thương s ố và r được gọi là số dư.
Khi b là nguyên dương, ta ký hiệu số dư r trong phép chia a cho b là a mod b. Mệnh đề 2: Cho a = bq+r, trong đó a, b, q, r là các số nguyên. Khi đó
UCLN(a,b) = UCLN(b,r).(Ở đây UCLN(a,b) để chỉ ước chung lớn nhất của a và b.)
Giả sử a và b là hai s ố nguy ên d ương với a b. Đặt r0= a và r1 = b. Bằng cách áp dụng liên tiếp thuật toán chia, ta tìm được:
r0= r1q1+ r2
0 r2< r1 r1= r2q2+ r3 0 r3< r2
..................
rn-2= rn-1qn-1+ rn
0 <= rn< rn-1rn-1= rn qn.
Cuối cùng, số dư 0 sẽ xuất hiện trong dãy các phép chia liên tiếp, vì dãy các số d ư
a = r0> r1> r2>... >= 0
không thể chứa quá a số hạng được. Hơn nữa, từ Mệnh đề 2 ở trên ta suy ra:
UCLN(a,b) = UCLN(r0,r1) = UCLN(r1,r2) = ... = UCLN(rn-2, rn-1) = UCLN(rn-1,rn) = rn.
Do đó, ước chung lớn nhất là số dư khác không cuối cùng trong dãy các phép chia.
Thí dụ 6: Dùng thuật toán Euclide tìm UCLN(414, 662).
662 = 441.1 + 248
414 = 248.1 + 166
248 = 166.1+ 82
166 = 82.2 + 2
82 = 2.41.
Do đó, UCLN(414, 662) = 2.
Thuật toán Euclide được viết dưới dạng giả mã như sau:
..................
rn-2= rn-1qn-1+ rn
0 <= rn< rn-1rn-1= rn qn.
Cuối cùng, số dư 0 sẽ xuất hiện trong dãy các phép chia liên tiếp, vì dãy các số d ư
a = r0> r1> r2>... >= 0
không thể chứa quá a số hạng được. Hơn nữa, từ Mệnh đề 2 ở trên ta suy ra:
UCLN(a,b) = UCLN(r0,r1) = UCLN(r1,r2) = ... = UCLN(rn-2, rn-1) = UCLN(rn-1,rn) = rn.
Do đó, ước chung lớn nhất là số dư khác không cuối cùng trong dãy các phép chia.
Thí dụ 6: Dùng thuật toán Euclide tìm UCLN(414, 662).
662 = 441.1 + 248
414 = 248.1 + 166
248 = 166.1+ 82
166 = 82.2 + 2
82 = 2.41.
Do đó, UCLN(414, 662) = 2.
Thuật toán Euclide được viết dưới dạng giả mã như sau:
procedure ƯCLN (a,b: positive integers)
x := a
y := b
while y <= 0
begin
r := x mod y
x := y
y := r
end
{UCLN (a,b) là x}
Trong thuật toán tr ên, các giá trị ban đầu của x và y tương ứng là a và b. Ở mỗi giai đoạn của thủ tục, x được thay bằng y và y được thay bằng x mod y. Quá trình này được lặp lại chừng nào y <= 0. Thuật toán sẽ ngừng khi y = 0 v à giá trị của x ở điểm n ày, đó là số dư khác không cuối cùng trong thủ tục, cũng chính là ước chung lớn nhất của a và b.
1.4.2. Biểu diễn các số nguyên:
Mệnh đề 3: Cho b là một số nguyên dương lớn hơn 1. Khi đó nếu n là một số nguyên dương, nó có thể được biểu diễn một cách duy nhất dưới dạng:
n = ak bk+ ak-1bk-1+ ... + a1b + a0.
Ở đây k là một số tự nhiên, a0, a1,..., ak là các số tự nhiên nhỏ hơn b và ak<= 0.
Biểu diễn của n được cho trong Mệnh đề 3 được gọi là khai triển của n theo cơ số b, ký hiệu là (akak-1... a1a0)b.
1.4.2. Biểu diễn các số nguyên:
Mệnh đề 3: Cho b là một số nguyên dương lớn hơn 1. Khi đó nếu n là một số nguyên dương, nó có thể được biểu diễn một cách duy nhất dưới dạng:
n = ak bk+ ak-1bk-1+ ... + a1b + a0.
Ở đây k là một số tự nhiên, a0, a1,..., ak là các số tự nhiên nhỏ hơn b và ak<= 0.
Biểu diễn của n được cho trong Mệnh đề 3 được gọi là khai triển của n theo cơ số b, ký hiệu là (akak-1... a1a0)b.
Bây giờ ta sẽ mô tả thuật toán xây dựng khai triển cơ số b của số nguyên n bất kỳ. Tr ước hết ta chia n cho b để được thương và số dư, tức là
n = bq0+ a0, 0 <= a0< b.
Số dư a0 chính là chữ số đứng bên phải cùng trong khai triển c ơ số b c ủa n. Tiếp theo chia q0 cho b, ta được:
q0= bq1+ a1, 0 <= a1< b.
Số dư a1 chính là chữ số thứ hai tính từ bên ph ải trong khai triển c ơ số b của n. Tiếp tục quá trình này, bằng cách liên tiếp chia các thương cho b ta sẽ được các chữ số tiếp theo trong khai triển cơ số b của n là các số d ư tương ứng. Quá trình này sẽ kết thúc khi ta nhận được một thương bằng 0.
Thí dụ 7: Tìm khai triển cơ số 8 của (12345)10.
12345 = 8.1543 + 1
1543 = 8.192 + 7
192 = 8.24 + 0
n = bq0+ a0, 0 <= a0< b.
Số dư a0 chính là chữ số đứng bên phải cùng trong khai triển c ơ số b c ủa n. Tiếp theo chia q0 cho b, ta được:
q0= bq1+ a1, 0 <= a1< b.
Số dư a1 chính là chữ số thứ hai tính từ bên ph ải trong khai triển c ơ số b của n. Tiếp tục quá trình này, bằng cách liên tiếp chia các thương cho b ta sẽ được các chữ số tiếp theo trong khai triển cơ số b của n là các số d ư tương ứng. Quá trình này sẽ kết thúc khi ta nhận được một thương bằng 0.
Thí dụ 7: Tìm khai triển cơ số 8 của (12345)10.
12345 = 8.1543 + 1
1543 = 8.192 + 7
192 = 8.24 + 0
24 = 8.3 + 0
3 = 8.0 + 3.
Do đó, (12345)10= (30071)8.
Đoạn giả mã sau biểu diễn thuật toán tìm khai triển cơ số b của số nguyên n.
Do đó, (12345)10= (30071)8.
Đoạn giả mã sau biểu diễn thuật toán tìm khai triển cơ số b của số nguyên n.
procedure khai triển theo c ơ số b (n: positive integer)
q := n
k := 0
while q <= 0
begin
ak:= q mod b
q := [qb]
k := k + 1
end
1.4.3. Thuật toán cho các phép tính số nguyên:
Các thuật toán thực hiện các phép tính với những số nguyên khi dùng các khai triển nhị phân của chúng là cực kỳ quan trọng trong số học của máy tính. Ta sẽ mô tả ở
đây các thuật toán cộng và nhân hai số nguyên trong biểu diễn nhị phân. Ta cũng sẽ phân tích đ ộ phức tạp tính toán của các thuật toán này thông qua số các phép toán bit thực sự được dùng. Giả sử khai triển nhị phân của hai số nguyên dương a và b là:
a = (an-1an-2... a1a0)2
và b = (bn-1bn-2... b1b0)2
sao cho a và b đều có n bit (đặt các bit 0 ở đầu mỗi khai triển đó, nếu cần).
1) Phép cộng: Xét bài toán cộng hai số nguy ên viết ở dạng nhị phân. Thủ tục thực hiện phép cộng có thể dựa trên phương pháp thông thường là cộng cặp chữ số nhị phân với nhau (có nhớ) để tính tổng của hai số nguyên.
Để cộng a và b, trư ớc hết cộng hai bit ở phải cùng của chúng, tức là:
a0+ b0= c0.2 + s0.
Ở đây s0 là bit phải c ùng trong khai triển nhị phân của a+b, c0 là số nhớ, nó có thể bằng 0 hoặc 1. Sau đó ta cộng hai bit tiếp theo và số nhớ
a1+ b1+ c0= c1.2 + s1.
Ở đây s1 là bit tiếp theo (tính từ bên phải) trong khai triển nhị phân của a+b và c1 là số nhớ. Tiếp tục quá trình này b ằng cách cộng các bit tương ứng trong hai khai triển nhị phân và số nhớ để xác định bit tiếp sau tính từ bên phải trong khai triển nhị phân của tổng a+b. Ở giai đoạn cuối cùng, c ộng an-1, bn-1
và cn-2 để nhận được cn-1.2+sn-1. Bit đứngđầu của tổng là sn=cn-1.
Các thuật toán thực hiện các phép tính với những số nguyên khi dùng các khai triển nhị phân của chúng là cực kỳ quan trọng trong số học của máy tính. Ta sẽ mô tả ở
đây các thuật toán cộng và nhân hai số nguyên trong biểu diễn nhị phân. Ta cũng sẽ phân tích đ ộ phức tạp tính toán của các thuật toán này thông qua số các phép toán bit thực sự được dùng. Giả sử khai triển nhị phân của hai số nguyên dương a và b là:
a = (an-1an-2... a1a0)2
và b = (bn-1bn-2... b1b0)2
sao cho a và b đều có n bit (đặt các bit 0 ở đầu mỗi khai triển đó, nếu cần).
1) Phép cộng: Xét bài toán cộng hai số nguy ên viết ở dạng nhị phân. Thủ tục thực hiện phép cộng có thể dựa trên phương pháp thông thường là cộng cặp chữ số nhị phân với nhau (có nhớ) để tính tổng của hai số nguyên.
Để cộng a và b, trư ớc hết cộng hai bit ở phải cùng của chúng, tức là:
a0+ b0= c0.2 + s0.
Ở đây s0 là bit phải c ùng trong khai triển nhị phân của a+b, c0 là số nhớ, nó có thể bằng 0 hoặc 1. Sau đó ta cộng hai bit tiếp theo và số nhớ
a1+ b1+ c0= c1.2 + s1.
Ở đây s1 là bit tiếp theo (tính từ bên phải) trong khai triển nhị phân của a+b và c1 là số nhớ. Tiếp tục quá trình này b ằng cách cộng các bit tương ứng trong hai khai triển nhị phân và số nhớ để xác định bit tiếp sau tính từ bên phải trong khai triển nhị phân của tổng a+b. Ở giai đoạn cuối cùng, c ộng an-1, bn-1
và cn-2 để nhận được cn-1.2+sn-1. Bit đứngđầu của tổng là sn=cn-1.
Kết quả, thủ tục này tạo ra được khai triển nhị phân của tổng, cụ thể là a+b = (sn.sn-1sn-2... s1s0)2.
Thí dụ 8: Tìm tổng của a = (11011)2và b = (10110)2.
Thí dụ 8: Tìm tổng của a = (11011)2và b = (10110)2.
a0+ b0= 1 + 0 = 0.2 + 1 (c0= 0, s0= 1),
a1+ b1+ c0= 1 + 1 + 0 = 1.2 + 0 (c1= 1,s1= 0),
a2+ b2+c1= 0 + 1 + 1 = 1.2 + 0 (c2= 1, s2= 0),
a3+ b3+ c2= 1 + 0 + 1 = 1.2 +0 (c3= 1, s3= 0),
a4+ b4+c3= 1 + 1 + 1 = 1.2 + 1 (s5= c4=1, s4= 1).
Do đó, a + b = (110001)2.
Thuật toán cộng có thể được mô tả bằng cách dùng đoạn giả mã như sau.
Do đó, a + b = (110001)2.
Thuật toán cộng có thể được mô tả bằng cách dùng đoạn giả mã như sau.
procedure cộng (a,b: positive integers)
c := 0
for j := 0 to n-1
begin
d:= (aj+bj+c)/2
sj:= aj+ bj+ c - 2d
c := d
end
sn:= c
{khai triển nhị phân của tổng là (snsn-1...s1s0)2}
Tổng hai số nguyên đư ợc tính bằng cách cộng liên tiếp các cặp bit và khi cần
phải cộng cả số nhớ nữa. Cộng một cặp bit và số nhớ đòi ba hoặc ít hơn phép c ộng các
bit. Như vậy, tổng số các phép cộng bit được sử dụng nhỏ hơn ba lần số bit trong khai
triển nhị phân. Do đó, độ phức tạp của thuật toán này là O(n).
2) Phép nhân: Xét bài toán nhân hai số nguyên vi ết ở dạng nhị phân. Thuật toán thông
thường tiến hành như sau. Dùng luật phân phối, ta có:
phải cộng cả số nhớ nữa. Cộng một cặp bit và số nhớ đòi ba hoặc ít hơn phép c ộng các
bit. Như vậy, tổng số các phép cộng bit được sử dụng nhỏ hơn ba lần số bit trong khai
triển nhị phân. Do đó, độ phức tạp của thuật toán này là O(n).
2) Phép nhân: Xét bài toán nhân hai số nguyên vi ết ở dạng nhị phân. Thuật toán thông
thường tiến hành như sau. Dùng luật phân phối, ta có:
Ta có thể tính ab bằng cách dùng phương trình trên. Trước hết, ta thấy rằng abj=a nếubj=1 và abj=0 nếu bj=0. Mỗi lần ta nhân một số hạng với 2 là ta d ịch khai triển nhị phân của nó một chỗ về phía trái bằng cách thêm m ột số không vào cuối khai triển nhị phân của nó. Do đó, ta có thể nhận được (abj)2j
bằng cách dịch khai triển nhị phân của abj đi j chỗ về phía trái, tức là thêm j số không vào cuối khai triển nhị phân của nó. Cuối cùng, ta sẽ nhận được tích ab bằng cách cộng n số nguyên abj.2jvới j=0, 1, ..., n-1.
Thí dụ 9: Tìm tích của a = (110)2và b = (101)2.
Ta có ab0.2^0= (110)2.1.2^0= (110)2, ab1.2^1= (110)2.0.2^1= (0000)2, ab2.2^2=(110)2.1.2^2= (11000)2. Để tìm tích, hãy cộng (110)2, (0000)2và (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)
Ta có ab0.2^0= (110)2.1.2^0= (110)2, ab1.2^1= (110)2.0.2^1= (0000)2, ab2.2^2=(110)2.1.2^2= (11000)2. Để tìm tích, hãy cộng (110)2, (0000)2và (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-1là 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 b
j=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 b
j=0 thì không cần có dịch chuyển nào vì c
j=0. Do đó, để tìm tất cả n số nguyên abj.2j
với j=0, 1, ..., n-1, đòi hỏi tối đa là 0 + 1 + 2 + ... + n-1 = n (n-1) /2 phép dịch chỗ.
j=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 b
j=0 thì không cần có dịch chuyển nào vì c
j=0. Do đó, để tìm tất cả n số nguyên abj.2j
với j=0, 1, ..., n-1, đòi hỏi tối đa là 0 + 1 + 2 + ... + n-1 = n (n-1) /2 phép dịch chỗ.
Vì vậy, số các dịch chuyển chỗ đòi h ỏi l à O(n2).
Để cộng các số nguy n a b j từ j=0 đến n1, đò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).
Để cộng các số nguy n a b j từ j=0 đến n1, đò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).