Thiết kế và đánh giá thuật toán

= O(log2n)

2.2.4. Nh©n c¸c sè nguyªn lín.

1) Bài toán

Cho hai số nguyên X và Y, mỗi số gồm n chữ số. Tính tích của hai số nguyên đó.

2) Ý tưởng

Biểu diễn X và Y dưới dạng X = A10n/2 + B và Y = C10n/2 + D

Trong đó A, B, C, D là các số có n/2 chữ số. Chẳng hạn với X = 1234 thì A = 12 và B = 34 vì 12*102 + 34 = 1234 = X

Với cách biểu diễn này thì XY = AC10n + (AD + BC)10n/2 + BD (*)

Thay vì nhân trực tiếp 2 số có n chữ số, ta phân tích bài toán ban đầu thành một số bài toán nhân 2 số có n/2 chữ số. Sau đó, ta kết hợp các kết quả trung gian theo công thức (*).

Việc phân chia này sẽ dẫn đến các bài toán nhân 2 số có 1 chữ số. Đây là bài toán cơ sở. Tóm lại:

- Kích thước bài toán: số chữ số của X, Y

- Phân tích: Chia bài toán ban đầu thành các bài toán nhân các số có n/2 chữ số. Quá trình phân chia dừng lại khi kích thước bài toán bằng 1.

- Tổng hợp: Tổng hợp kết quả theo công thức (*).

Chú ý: Với những số có một số lẻ chữ số ta thêm số 0 vào đầu để được số có một số chẵn chữ số.

3) Thiết kế thuật toán

Theo công thức (*) ở trên việc nhân 2 số nguyên có n chữ số được phân chia thành 4 phép nhân các số nguyên có n/2 chữ số, 3 phép cộng và 2 phép nhân với 10n và 10n/2. Phép cộng các số cần O(n). Phép nhân với 10n tốn O(n). Gọi T(n) là thời gian nhân 2 số có n chữ số ta có phương trình truy hồi sau:

C1 nếu n =1

T(n)=

4T( 2 ) + C2n nếu n >1

Khi đó độ phức tạp tính toán sẽ được xác định như sau: Ta có với n>1:

T(n) = 4T( n )+c2n

n n n 4 n

= 4(4T( )+c2 ) + c2n = 16T( ) + 3c2n = 2 T( ) + 3c2n

4 2 4 2 2

= 16( 4T( n )+c2 n ) + 3c2n = 64T( n ) + 7c2n = 26T( n ) + 7c2n

8 4 8 23

.....

= 22iT(

n ) + (2i - 1)c2n

Quá trình sẽ dừng khi

n =1

Khi đó T(n) =

 n =2i

 i = log2n

22 log2nT( 1) ( 2log2n1)C n

= C1n2 + C2(n-1)n Và T(n) = O(n2)

Như vậy ta không cải tiến được gì với giải thuật nhân thông thường. Ta biến đổi công thức (*) lại như sau:

XY = AC10n + [(A -B)(D-C) + AC + BD]10n/2 + BD (**)

Theo công thức này, ta chỉ cần 3 phép nhân các số nguyên có n/2 chữ số, 6 phép cộng trừ và 2 phép nhân với 10n, 10n/2.

Ví dụ 2.2.

Ta minh hoạ quá trình này bằng việc nhân 981 với 1234. Trước tiên chúng ta điền thêm vào toán hạng ngắn hơn một số không vô nghĩa để làm cho hai toán hạng có cùng độ dài, vậy là 981 trở thành 0981. Sau đó tách từng toán hạng thành hai nửa:

0981 tách thành w = 09 và x = 81 1234 tách thành y = 12 và z = 34

Lưu ý rằng 981 = 102w + x và 1234 = 102y + z. Do đó, tích cần tìm có thể tính

được là:

981 x 1234 = (102w + x)( 102y + z)

= 104wy + 102(wz + xy) + xz

= 1080000 + 127800 + 2754

= 1210554

Thủ tục trên đến bốn phép nhân hai nửa: wy, wz, xy và xz.

Để ý điểm mấu chốt ở đây là thực ra thì không cần tính cả wz lẫn xy, mà là tổng của hai số hạng này. Liệu có thể thu được wz + xy với chi phí của một phép nhân mà thôi hay không? Điều này có vẻ như không thể được cho đến khi chúng ta nhớ ra rằng mình cũng cần những giá trị wy và xz để đưa vào công thức trên. Lưu ý về điểm này, hãy xét tích:

r = (w + x)(y+z) = wy + (wz + xy) + xz

Chỉ sau một phép nhân, chúng ta thu được tổng của tất cả ba số hạng cần thiết để tính được tích mình mong muốn. Điều này gợi ý một cách tiến hành như sau:

p = wy = 09 * 12 = 108

q = xz = 81 * 34 = 2754

r = (w + x)(y+z) = 90 * 46 = 4140

và cuối cùng

981 x 1234 = 104p + 102(r – p – q) + q

= 1080000 + 127800 + 2754 = 1210554.

Như vậy tích của 981 và 1234 có thể rút gọn về ba phép nhân của hai số có hai chữ số (09 với 12, 81 với 34 và 90 với 46) cùng với một số nào đó phép dịch chuyển (nhân với luỹ thừa của 10), phép cộng và phép trừ.

Từ đó ta đưa ra thuật toán nhân số nguyên lớn là Nhan(x,y,n)

{

if (n == 1) Return x[0]*y[0]; Else

{

a = x[n-1]. . . x[n/2];

b = x[n/2-1] . . . x[0];

c = y[n-1]. . . y[n/2];

d = y[n/2-1] . . . y[0];

U = Nhan(a,c,n/2);

V = Nhan(b,d,n/2);

W = Nhan(a+b,c+d,n/2);

Return U*10n + (W-U-V)*10n/2 + V

}

4) Đánh giá độ phức tạp tính toán của thuật toán

Ta có phương trình đệ quy sau: T(1) = 1

T(n) = 3T(n/2) + cn

Giải phương trình ta được T(n) = O(nlog3) = O(n1.59). Rò ràng cải tiến hơn giải thuật cũ rất nhiều. thuật toán này có thể nhân hai số nguyên lớn nhanh hơn rất nhiều so với thuật toán nhân cổ điển và n càng lớn thì sự cải thiện này càng đáng giá.

Bµi tËp ch•¬ng 2

1. Hãy đưa ra hai thuật toán được thiết kế theo kỹ thuật chia để trị.

2. Dùng kỹ thuật chia để trị thiết kế thuật toán giải bài toán sau:

Tính tổng: 1 + 1/2 + 1/3 + ... + 1/n với n là một số nguyên dương.

3. Dùng kỹ thuật chia để trị thiết kế thuật toán giải bài toán sau: Tìm ước số chung lớn nhất của hai số nguyên dương.

4. Bài toán tháp Hà nội

Có n chiếc đĩa với đường kính khác nhau được đặt chồng lên nhau ở vị trí A, đĩa bé ở trên đĩa to. Cần chuyển chồng đĩa sang vị trí B được lấy vị trí C làm trung chuyển với điều kiện: Mỗi lần chỉ được chuyển một đĩa và trong quá trình chuyển không bao giờ được đặt đĩa to ở trên đĩa bé.

Hướng dẫn:

Vận dụng kỹ thuật chia để trị:

Bài toán chuyển N đĩa từ A sang B có thể chia thành các bài toán nhỏ hơn như sau:

(a) Chuyển N-1 đĩa ở trên từ A sang C

(b) Chuyển một đĩa từ A sang B

Như vậy bài toán đã được chuyển thành các bài toán tương tự với kích thước nhỏ hơn. Công việc được tiếp tục với (n-1) đĩa và cứ như thế cho đến khi chỉ còn một đĩa.

5. Bài toán hoán đổi hai phần trong dãy

Cho a[1..n] là một mảng gồm n phần tử. Ta cần chuyển m phần tử đầu tiên của mảng với phần còn lại của mảng (n-m phân tử) mà không dùng một mảng phụ .

Chẳng hạn, với n = 8, a[8] = (1, 2, 3, 4, 5, 6, 7, 8)

Nếu m = 3, thì kết quả là : ( 4, 5, 6, 7, 8, 1, 2, 3)

Nếu m = 5, thì kết quả là : ( 6, 7, 8, 1, 2, 3, 4, 5)

Nếu m = 4, thì kết quả là : ( 5, 6, 7, 8, 1, 2, 3, 4) Hướng dẫn:

- Nếu m = n – m: Hoán đổi các phần tử của 2 nửa mảng có độ dài bằng nhau

- Nếu m n–m

+ Nếu m < n – m : hoán đổi m phần tử đầu với m phân tử cuối của phần còn lại. Sau đó trong mảng a[1..n-m] ta chỉ cần hoán đổi m phần tử đầu với phần còn lại.

+ Nếu m > n – m : hoán đổi n-m phần tử đầu tiên với n-m phần tử của phần sau. Sau đó trong mảng a[n-m+1 . . n] ta hoán đổi n-m phần tử cuối mảng với các phần tử của phần đầu.

Như vậy, bằng cách áp dụng phương pháp chia để trị, ta chia bài toán thành 2 bài toán con :

- Bài toán thứ nhất là hoán đổi hai mảng con có độ dài bằng nhau, cụ thể là hoán đổi nửa số phần tử đầu và cuối của mảng cho nhau bằng cách đổi chỗ từng cặp phần tử tương ứng.

- Bài toán thứ hai cùng dạng với bài toán đã cho nhưng kích thước nhỏ hơn, nên có thể gọi thuật toán đệ qui để giải và quá trình gọi đệ qui sẽ dừng khi đạt tới sự hoán đổi 2 phần có độ dài bằng nhau

Vậy mấu chốt của thuật toán là thực hiện thao tác hoán đổi 2 nhóm phần tử, lặp lại thao tác này trong khi số lượng phần tử của 2 nhóm còn khác nhau. Vì vậy ta sẽ thay thuật toán đệ qui bằng thuật toán lặp.

// Hoán đổi m phần tử đầu của mảng với phần còn lại. Input : a[1..n], m. (m ≤n)

Output : a[1..n] với tính chất m phần tử đầu mảng a (mảng nhập ) nằm cuối mảng kết quả, n-m phần tử cuối mảng nhập nằm ở đầu mảng kết quả.

Mô tả thuật toán : Transpose(a,n,m)

{

i = m; j = n-m; m = m+1; Khi ( i != j)

Nếu ( i > j)

{

Exchange(a,m-i,m,j); i = i – j;

}

Ngược lại

{

j = j – i;

Exchange(a,m-i,m+j,i);

}

Exchange(a,m-i,m,i);

}

Hàm exchange : input a,

i,j, //vị trí

m; // Số phần tử cần hoán đổi output a

Exchange(a,i,j,m)

{

Với mọi p = 0 -> m-1

Đổichỗ (a[i+p], a[j+p]);

}

6. Lập lịch thi đấu thể thao

Có n = 2k đối thủ thi đấu với nhau theo thể thức vòng tròn một lượt: Mỗi đấu thủ phải đấu với các đấu thủ khác 1 trận. Mỗi đấu thủ chỉ đấu nhiều nhất một trận mỗi ngày. Hãy xếp lịch thi đấu sao cho số ngày thi đấu là ít nhất.

Hướng dẫn:

Vì thể thức thi đấu là vòng tròn một lượt nên mỗi đấu thủ phải thi đấu đúng n-1 trận. Ta dễ dàng thấy rằng vì n là một số chẵn nên ta có thể sắp nhiều nhất là n/2 cặp thi đấu trong một ngày và do đó cần ít nhất n-1 ngày. Ta sẽ tìm cách xây dựng lịch để số ngày thi đấu là n-1.

Lịch thi đấu là một bảng n dòng và n-1 cột. Các dòng được đánh số từ 1 đến n và các cột được đánh số từ 1 đến n-1, trong đó dòng i biểu diễn cho đấu thủ i, cột j biểu diễn cho ngày thi đấu j và ô(i, j) ghi đấu thủ phải thi đấu với đấu thủ i trong ngày j.

Kỹ thuật chia để trị được áp dụng để xây dựng lịch thi đấu như sau: Ðể sắp lịch cho n đấu thủ, ta sẽ sắp lịch cho n/2 đấu thủ, để sắp lịch cho n/2 đấu thủ, ta sẽ sắp lịch cho n/4 đấu thủ...

Quá trình này sẽ dẫn đến bài toán cơ sở là sắp lịch thi đấu cho 2 đấu thủ. Hai đấu thủ này sẽ thi đấu một trận trong một ngày, lịch thi đấu cho họ thật dễ sắp. Khó khăn chính là ở chỗ từ các lịch thi đấu cho hai đấu thủ, ta tổng hợp lại để được lịch

thi đấu của 4 đấu thủ, 8 cấu thủ, ...

Góc trên bên trái của bảng chính là lịch thi đấu của n/2 đấu thủ từ 1 đến n/2 trong các ngày từ ngày 1 đến ngày [(n-1)/2], từ đó ta có góc dưới bên trái là lịch thi đấu trong các ngày này của các đấu thủ từ n/2+1 đến n: nó sẽ bằng các phần tử ở góc trên bên trái cộng thêm n/2. Góc dưới bên phải của bảng chính là góc trên bên trái và góc trên bên phải chính là góc dưới bên trái. Còn với cột [(n-1)/2] +1 thì n/2 đấu thủ đầu sẽ lần lượt đấu với n/2 đấu thủ sau và ngược lại.

Chẳng hạn: Xuất phát từ lịch thi đấu cho hai đấu thủ ta có thể xây dựng lịch thi đấu cho 4 đấu thủ như sau: Lịch thi đấu cho 4 đấu thủ sẽ là một bảng 4 dòng, 3 cột. Lịch thi đấu cho 2 đấu thủ 1 và 2 trong ngày thứ 1 chính là lịch thi đấu của hai đấu thủ (bài toán cơ sở). Như vậy ta có Ô(1,1) = “2” và Ô(2,1) = “1”. Tương tự ta có lịch thi đấu cho 2 đấu thủ 3 và 4 trong ngày thứ 1. Nghĩa là Ô(3,1) =“4” và Ô(4,1) = “3”. (Ta cố thể thấy rằng Ô(3,1) = Ô(1,1) + 2 và Ô(4,1) = Ô(2,1) + 2 ). Ta

lấy góc trên bên trái của bảng lắp vào cho góc dưới bên phải và lấy góc dưới bên trái lắp cho góc trên bên phải. Bây giờ để hoàn thành lịch thi đấu cho 4 đấu thủ ta điền nốt cột 2.

Lịch thi đấu cho 8 đấu thủ là một bảng gồm 8 dòng, 7 cột. Góc trên bên trái chính là ch thi đấu trong 3 ngày đầu của 4 đấu thủ từ 1 đến 4. Các ô của góc dưới bên trái sẽ bằng các ô tương ứng của góc trên bên trái cộng với 4. Ðây chính là lịch thi đấu cho 4 đấu thủ 5, 6, 7 và 8 trong 3 ngày đầu. Bây giờ chúng ta hoàn thành việc sắp lịch bằng cách lấp đầy góc dưới bên phải bởi góc trên bên trái và góc trên bên phải bởi góc dưới bên trái và điền nốt cột 4.

Dưới đây là các bảng xếp lịch thi đấu cho 2 đấu thủ, 4 đấu thủ và 8 đấu thủ theo cách xây dựng trên:

2 đấu thủ

4 đấu thủ

2	3	4
1	4	3
4	1	2
3	2	1