nhungvisaotronglongtoi
New Member
Link tải luận văn miễn phí cho ae Kết Nối
MỤC LỤC
MỤC LỤC 2
THUẬT TOÁN CHIA ĐỂ TRỊ 3
(Divide to Conquer) 3
1) Khái niệm: 3
2) Sơ đồ chung: 3
3) Thuật toán β: 3
4) Sơ đồ thuật toán chia để trị: 4
5) Một số ví dụ 5
5.1) Bài toán tháp Hà Nội 5
5.2) Bài toán nhân các số tự nhiên lớn 6
5.3) Bài toán tạo lịch thi đấu Tennis 7
5.6) Giải và cài đặt bài toán Mảng con lớn nhất 8
5.6.1) Thuật toán chia để trị tìm mảng con lớn nhất gồm các thao tác: 8
5.6.2) Thuật toán chia để trị tìm mảng con lớn nhất 8
5.6.3) Thuật toán MaxVector(a, i, j): 9
5.6.4) Cài đặt chương trình 9
5.6.5) Phân tích hiệu quả của thuật toán: 13
THUẬT TOÁN CHIA ĐỂ TRỊ
(Divide to Conquer)
Có lẽ thuật toán được sử dụng nhiều nhất, quan trọng nhất là kỹ thuật ″Chia để Trị″. Kỹ thuật này sẽ chia bài toán hiện thời thành N bài toán nhỏ hơn, thực hiện lời giải cho từng bài toán nhỏ này và từ đó xây dựng thuật toán cho bài toán lớn tổng hợp. Ví dụ cho các thuật toán này là Sắp xếp Trộn(1) hay Tìm kiếm Nhị phân(2).
1) Khái niệm:
Chia để trị là một trong những phương pháp thiết kế giải thuật cơ bản bao gồm các thao tác:
Chia: Chia bài toán cần giải thành một loạt các bài toán con độc lập.
Trị: Đòi hỏi việc giải các bài toán con thu được.
Tổng hợp: Thực hiện việc xây dựng lời giải của bài toán đặt ra từ các lời giải của bài toán con.
2) Sơ đồ chung:
Sơ đồ chung của thuật toán chia để trị (Divide and Conquer) gồm 3 thành phần:
- Chia (Divide): Chia bài toán cần giải S ra thành các bài toán con S1, S2, S3, ...
- Trị (Conquer): Giải các bài toán con một cách đệ quy.
- Tổng hợp (Combine): Tổng hợp lời giải của bài toán S1, S2, S3, ... thành lời giải của bài toán S.
Để phân tích độ phức tạp của thuật toán có thể sử dụng công thứ đệ quy.
Vấn đề đặt ra là cần giải các bài toán con độc lập bằng cách nào? Đó là vấn đề trung tâm của bài toán.
3) Thuật toán β:
Giả sử chúng ta có thuật toán α để giải bài toán kích thước dữ liệu vào n với thời gian bị chặn bởi cn2 (c: hằng số). Xét thuật giải β để giải chính bài toán đó bằng cách:
- Bước 1: Chia bài toán cần giải thành 3 bài toán con với kích thước n/2.
- Bước 2: Giải 3 bài toán bằng thuật toán α.
- Bước 3 Tổng hợp lời giải của 3 bài toán con để thu được lời giải của bài toán.
* Tính đúng đắn của thuật toán β
Giả sử bước 3 đòi hỏi thời gian dn(d: hằng số).
Gọi:
T α(n) = thời gian của thuật toán α.
T β(n) = thời gian của thuật toán β.
Ta có:
T α(n) = cn2 (theo giả thuyết)
T β(n) = 3.T α(n/2) + dn = ¾.cn2 + dn.
Nếu:
dn < c.n2/4 hay n > 4. d/c thì thuật toán β nhanh hơn thuật toán α.
Do 4.d/c là hằng số nên với n đủ lớn ta luôn có n > 4. d/c.
Điều đó cho thấy việc sử dụng thuật toán β để giải bài toán đặt ra bằng cách chia nó thành các bài toán con có kích thước càng ngày càng nhỏ đến khi thu được bài toán con kích thước n0 < 4.d/c sẽ thu được hiệu quả cao.
4) Sơ đồ thuật toán chia để trị:
procedure Divide_and_Conquer(n);
begin
if n ≤ n0 then
Giải bài toán một cách trực tiếp;
else
begin
Chia bài toán thành r bài toán con có kích thước n/k;
for (mỗi bài toán trong r bài toán con) do
Divide_and_Conquer(n/k);
Tổng hợp lời giải của r bài toán con để thu được lời giải của bài toán;
end;
end;
5) Một số ví dụ
5.1) Bài toán tháp Hà Nội
Để minh họa rõ hơn cho kỹ thuật này chúng ta hãy xét một ví dụ quen thuộc đó là bài toán ″Tháp Hà Nội″. Giả sử có 3 cọc A, B, C. Ban đầu tại A đặt một số đĩa với thứ tự trên nhỏ dưới to như hình vẽ.
Yêu cầu của bài toán là chuyển toàn bộ số đĩa trên sang cọc B, trong quá trình chuyển được phép sử dụng đĩa C, mỗi lần chuyển đúng 01 đĩa và luôn bảo đảm nguyên tắc đĩa nhỏ nằm trên đĩa to trong suốt quá trình chuyển.
Bài toán
Tháp Hà Nội trên có thể giải với thuật toán ″thông minh″ sau: Giả sử ta đặt 3 cọc trên tại các đỉnh của một tam giác đều. Tại bước với số lượt là lẻ, ta chuyển đĩa nhỏ nhất sang cọc bên cạnh theo chiều kim đồng hồ, tại bước đi với số lượt là chẵn, ta thực hiện một thao tác bất kỳ nhưng không đụng đến cái đĩa nhỏ nhất. các bạn dễ dàng kiểm tra rằng đó là một thuật toán đúng, tuy nhiên nó rất khó hiểu, khó tổng quát sang các trường hợp khác.
Ta hãy thử vận dụng tư duy của thuật toán ″Chia để Trị″ đối với bài toán Tháp Hà Nội này. Bài toán chuyển N đĩa từ A sang B có thể chia thành 2 bài toán nhỏ hơn với kích thước N-1 như sau: (a) Chuyển N-1 đĩa đầu tiên từ A sang C (giữ nguyên trạng thái của đĩa thứ N tại A). (b) Chuyển đĩa thứ N từ A sang B và chuyển N-1 đĩa từ C sang B. Chú ý rằng khi thực hiện bài toán (b) phần chuyển N-1 đĩa từ C sang B ta có thể dùng lại hoàn toàn thuật toán của bài (a) nhưng với vị trí thay đổi giữa A và C và tất nhiên bỏ qua sự có mặt của đĩa thứ N trong A hay B. Với cách tư duy như vậy, việc mô phỏng thuật toán sẽ tương đối khó do nó phải gọi đệ qui đến chính nó nhưng cách làm trên thật là dễ hiểu và cho phép chúng ta áp dụng cho nhiều lớp bài toán khác. Chúng ta hãy xét một vài ví dụ.
5.2) Bài toán nhân các số tự nhiên lớn
Xét bài toán nhân 2 số tự nhiên n-bit X và Y. Bài toán nhân 2 số tự nhiên n-bit (n chữ số) đã được dạy trong nhà trường phổ thông với độ phức tạp O(n2)(3). Bây giờ chúng ta sẽ xét lại bài toán này với kỹ thuật Chia để Trị. Ta phân tách mỗi số X, Y thành 2 phần, mỗi phần n/2 bit. Để cho đơn giản ta sẽ luôn xét n là lũy thừa của 2. X, Y sẽ được phân tích thành 2 phần n/2-bit như sau:
X = A | B (X = A2n/2 + B)
Y = C | D
(Y = C2n/2 + D)
Khi đó tích XY sẽ có dạng:
XY = AC2n + (AD+BC)2n/2 + BD (1)
Dựa trên công thức (1) ta có thể suy luận đơn giản như sau cho việc tính tích XY: chúng ta sẽ tính 4 phép nhân với các số n/2-bit là AC, AD, BC và BD, sau đó thực hiện 3 phép cộng với các số 2n-bit, cuối cùng là 2 phép chuyển chữ số (2 phép nhân với lũy thừa của 2) Các phép cộng và phép chuyển chữ số đều được thực hiện với thời gian O(n), do đó ta thu được công thức tính độ phức tạp của phép toán trên T(n) là:
T(1) = 1
T(n) = 4T(n/2) + C.n (C-const)
(2) Công thức (2) cho ta T(n) = O(n2) và như vậy ta chưa thu được kết quả gì mới so với phương pháp tính từ nhà trường phổ thông.
Bây giờ ta biến đổi công thức (1) dưới dạng:
XY = AC2n + ((A-B)(D-C) + AC + BD)2n/2 + BD
(2) Công thức (2) mặc dù phức tạp hơn (1) nhưng chúng có thể được tính bởi:
- 3 phép nhân n/2-bit: AC, BD và (A-B)(D-C).
- 6 phép +,- các số n/2-bit.
- 2 phép chuyển chữ số (nhân với lũy thừa của 2).
Do vậy với cách tính trên ta có công thức sau tính độ phức tạp của thuật toán này:
T(1) = 1
T(n) = 3T(n/2) + C.n (C-const)
(3) Công thức (3) cho ta
chuyển N-1 đĩa từ C sang B. Chú ý rằng khi thực hiện bài toán (b) phần chuyển N-1 đĩa từ C sang B ta có thể dùng lại hoàn toàn thuật toán của bài (a) nhưng với vị trí thay đổi giữa A và C và tất nhiên bỏ qua sự có mặt của đĩa thứ N trong A hay B. Với cách tư duy như vậy, việc mô phỏng thuật toán sẽ tương đối khó do nó phải gọi đệ qui đến chính nó nhưng cách làm trên thật là dễ hiểu và cho phép chúng ta áp dụng cho nhiều lớp bài toán khác. Chúng ta hãy xét một vài ví dụ.
5.2) Bài toán nhân các số tự nhiên lớn
Xét bài toán nhân 2 số tự nhiên n-bit X và Y. Bài toán nhân 2 số tự nhiên n-bit (n chữ số) đã được dạy trong nhà trường phổ thông với độ phức tạp O(n2)(3). Bây giờ chúng ta sẽ xét lại bài toán này với kỹ thuật Chia để Trị. Ta phân tách mỗi số X, Y thành 2 phần, mỗi phần n/2 bit. Để cho đơn giản ta sẽ luôn xét n là lũy thừa của 2. X, Y sẽ được phân tích thành 2 phần n/2-bit như sau:
X = A | B (X = A2n/2 + B)
Y = C | D
(Y = C2n/2 + D)
Khi đó tích XY sẽ có dạng:
XY = AC2n + (AD+BC)2n/2 + BD (1)
Dựa trên công thức (1) ta có thể suy luận đơn giản như sau cho việc tính tích XY: chúng ta sẽ tính 4 phép nhân với các số n/2-bit là AC, AD, BC và BD, sau đó thực hiện 3 phép cộng với các số 2n-bit, cuối cùng là 2 phép chuyển chữ số (2 phép nhân với lũy thừa của 2) Các phép cộng và phép chuyển chữ số đều được thực hiện với thời gian O(n), do đó ta thu được công thức tính độ phức tạp của phép toán trên T(n) là:
T(1) = 1
T(n) = 4T(n/2) + C.n (C-const)
(2) Công thức (2) cho ta T(n) = O(n2) và như vậy ta chưa thu được kết quả gì mới so với phương pháp tính từ nhà trường phổ thông.
Bây giờ ta biến đổi công thức (1) dưới dạng:
XY = AC2n + ((A-B)(D-C) + AC + BD)2n/2 + BD
(2) Công thức (2) mặc dù phức tạp hơn (1) nhưng chúng có thể được tính bởi:
- 3 phép nhân n/2-bit: AC, BD và (A-B)(D-C).
- 6 phép +,- các số n/2-bit.
- 2 phép chuyển chữ số (nhân với lũy thừa của 2).
Do vậy với cách tính trên ta có công thức sau tính độ phức tạp của thuật toán này:
T(1) = 1
T(n) = 3T(n/2) + C.n (C-const)
(3) Công thức (3) cho ta
Như vậy ta đã thu được một kết quả mới cho việc thực hiện phép nhân 2 số tự nhiên n-bit với thuật toán mạnh hơn phép nhân bình thường đã học trong nhà trường (4).
5.3) Bài toán tạo lịch thi đấu Tennis
Giả sử cần lập một lịch thi đấu Tennis cho n = 2k vận động viên (VĐV). Mỗi vận động viên phải thi đấu với lần lượt n-1 vận động viên khác, mỗi ngày thi đấu 1 trận. Như vậy n-1 là số ngày thi đấu tối thiểu phải có. Chúng ta cần lập lịch thi đấu bằng cách thiết lập ma trận có n hàng, n-1 cột. Giá trị số tại vị trí (i,j) (hàng i, cột j) chỉ ra vận động viên cần thi đấu với vận động viên i trong ngày thứ j.
Sử dụng kỹ thuật Chia để Trị, chúng ta hãy lập lịch thi đấu cho nửa (n/2) số vận động viên đầu tiên. Bằng việc sử dụng lời gọi đệ qui chúng ta đưa bài toán về trường hợp chỉ có 2 VĐV.
Chúng ta minh họa bằng trường hợp n=8. Lịch thi đấu cho 4 người đầu tiên của danh sách chiếm nửa trái trên của ma trận (4 hàng, 3 cột). Phần nửa trái dưới (4 hàng, 3 cột) của ma trận là lịch thi đấu của 4 VĐV còn lại (từ 5 đến 8). Phần này thu được từ nửa trái trên bằng cách cộng 4 vào mỗi phần tử tương ứng của ma
Như vậy ta đã thu được một kết quả mới cho việc thực hiện phép nhân 2 số tự nhiên n-bit với thuật toán mạnh hơn phép nhân bình thường đã học trong nhà trường (4).
5.3) Bài toán tạo lịch thi đấu Tennis
Giả sử cần lập một lịch thi đấu Tennis cho n = 2k vận động viên (VĐV). Mỗi vận động viên phải thi đấu với lần lượt n-1 vận động viên khác, mỗi ngày thi đấu 1 trận. Như vậy n-1 là số ngày thi đấu tối thiểu phải có. Chúng ta cần lập lịch thi đấu bằng cách thiết lập ma trận có n hàng, n-1 cột. Giá trị số tại vị trí (i,j) (hàng i, cột j) chỉ ra vận động viên cần thi đấu với vận động viên i trong ngày thứ j.
Sử dụng kỹ thuật Chia để Trị, chúng ta hãy lập lịch thi đấu cho nửa (n/2) số vận động viên đầu tiên. Bằng việc sử dụng lời gọi đệ qui chúng ta đưa bài toán về trường hợp chỉ có 2 VĐV.
Chúng ta minh họa bằng trường hợp n=8. Lịch thi đấu cho 4 người đầu tiên của danh sách chiếm nửa trái trên của ma trận (4 hàng, 3 cột). Phần nửa trái dưới (4 hàng, 3 cột) của ma trận là lịch thi đấu của 4 VĐV còn lại (từ 5 đến 8). Phần này
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
MỤC LỤC
MỤC LỤC 2
THUẬT TOÁN CHIA ĐỂ TRỊ 3
(Divide to Conquer) 3
1) Khái niệm: 3
2) Sơ đồ chung: 3
3) Thuật toán β: 3
4) Sơ đồ thuật toán chia để trị: 4
5) Một số ví dụ 5
5.1) Bài toán tháp Hà Nội 5
5.2) Bài toán nhân các số tự nhiên lớn 6
5.3) Bài toán tạo lịch thi đấu Tennis 7
5.6) Giải và cài đặt bài toán Mảng con lớn nhất 8
5.6.1) Thuật toán chia để trị tìm mảng con lớn nhất gồm các thao tác: 8
5.6.2) Thuật toán chia để trị tìm mảng con lớn nhất 8
5.6.3) Thuật toán MaxVector(a, i, j): 9
5.6.4) Cài đặt chương trình 9
5.6.5) Phân tích hiệu quả của thuật toán: 13
THUẬT TOÁN CHIA ĐỂ TRỊ
(Divide to Conquer)
Có lẽ thuật toán được sử dụng nhiều nhất, quan trọng nhất là kỹ thuật ″Chia để Trị″. Kỹ thuật này sẽ chia bài toán hiện thời thành N bài toán nhỏ hơn, thực hiện lời giải cho từng bài toán nhỏ này và từ đó xây dựng thuật toán cho bài toán lớn tổng hợp. Ví dụ cho các thuật toán này là Sắp xếp Trộn(1) hay Tìm kiếm Nhị phân(2).
1) Khái niệm:
Chia để trị là một trong những phương pháp thiết kế giải thuật cơ bản bao gồm các thao tác:
Chia: Chia bài toán cần giải thành một loạt các bài toán con độc lập.
Trị: Đòi hỏi việc giải các bài toán con thu được.
Tổng hợp: Thực hiện việc xây dựng lời giải của bài toán đặt ra từ các lời giải của bài toán con.
2) Sơ đồ chung:
Sơ đồ chung của thuật toán chia để trị (Divide and Conquer) gồm 3 thành phần:
- Chia (Divide): Chia bài toán cần giải S ra thành các bài toán con S1, S2, S3, ...
- Trị (Conquer): Giải các bài toán con một cách đệ quy.
- Tổng hợp (Combine): Tổng hợp lời giải của bài toán S1, S2, S3, ... thành lời giải của bài toán S.
Để phân tích độ phức tạp của thuật toán có thể sử dụng công thứ đệ quy.
Vấn đề đặt ra là cần giải các bài toán con độc lập bằng cách nào? Đó là vấn đề trung tâm của bài toán.
3) Thuật toán β:
Giả sử chúng ta có thuật toán α để giải bài toán kích thước dữ liệu vào n với thời gian bị chặn bởi cn2 (c: hằng số). Xét thuật giải β để giải chính bài toán đó bằng cách:
- Bước 1: Chia bài toán cần giải thành 3 bài toán con với kích thước n/2.
- Bước 2: Giải 3 bài toán bằng thuật toán α.
- Bước 3 Tổng hợp lời giải của 3 bài toán con để thu được lời giải của bài toán.
* Tính đúng đắn của thuật toán β
Giả sử bước 3 đòi hỏi thời gian dn(d: hằng số).
Gọi:
T α(n) = thời gian của thuật toán α.
T β(n) = thời gian của thuật toán β.
Ta có:
T α(n) = cn2 (theo giả thuyết)
T β(n) = 3.T α(n/2) + dn = ¾.cn2 + dn.
Nếu:
dn < c.n2/4 hay n > 4. d/c thì thuật toán β nhanh hơn thuật toán α.
Do 4.d/c là hằng số nên với n đủ lớn ta luôn có n > 4. d/c.
Điều đó cho thấy việc sử dụng thuật toán β để giải bài toán đặt ra bằng cách chia nó thành các bài toán con có kích thước càng ngày càng nhỏ đến khi thu được bài toán con kích thước n0 < 4.d/c sẽ thu được hiệu quả cao.
4) Sơ đồ thuật toán chia để trị:
procedure Divide_and_Conquer(n);
begin
if n ≤ n0 then
Giải bài toán một cách trực tiếp;
else
begin
Chia bài toán thành r bài toán con có kích thước n/k;
for (mỗi bài toán trong r bài toán con) do
Divide_and_Conquer(n/k);
Tổng hợp lời giải của r bài toán con để thu được lời giải của bài toán;
end;
end;
5) Một số ví dụ
5.1) Bài toán tháp Hà Nội
Để minh họa rõ hơn cho kỹ thuật này chúng ta hãy xét một ví dụ quen thuộc đó là bài toán ″Tháp Hà Nội″. Giả sử có 3 cọc A, B, C. Ban đầu tại A đặt một số đĩa với thứ tự trên nhỏ dưới to như hình vẽ.
Yêu cầu của bài toán là chuyển toàn bộ số đĩa trên sang cọc B, trong quá trình chuyển được phép sử dụng đĩa C, mỗi lần chuyển đúng 01 đĩa và luôn bảo đảm nguyên tắc đĩa nhỏ nằm trên đĩa to trong suốt quá trình chuyển.
Bài toán
Tháp Hà Nội trên có thể giải với thuật toán ″thông minh″ sau: Giả sử ta đặt 3 cọc trên tại các đỉnh của một tam giác đều. Tại bước với số lượt là lẻ, ta chuyển đĩa nhỏ nhất sang cọc bên cạnh theo chiều kim đồng hồ, tại bước đi với số lượt là chẵn, ta thực hiện một thao tác bất kỳ nhưng không đụng đến cái đĩa nhỏ nhất. các bạn dễ dàng kiểm tra rằng đó là một thuật toán đúng, tuy nhiên nó rất khó hiểu, khó tổng quát sang các trường hợp khác.
Ta hãy thử vận dụng tư duy của thuật toán ″Chia để Trị″ đối với bài toán Tháp Hà Nội này. Bài toán chuyển N đĩa từ A sang B có thể chia thành 2 bài toán nhỏ hơn với kích thước N-1 như sau: (a) Chuyển N-1 đĩa đầu tiên từ A sang C (giữ nguyên trạng thái của đĩa thứ N tại A). (b) Chuyển đĩa thứ N từ A sang B và chuyển N-1 đĩa từ C sang B. Chú ý rằng khi thực hiện bài toán (b) phần chuyển N-1 đĩa từ C sang B ta có thể dùng lại hoàn toàn thuật toán của bài (a) nhưng với vị trí thay đổi giữa A và C và tất nhiên bỏ qua sự có mặt của đĩa thứ N trong A hay B. Với cách tư duy như vậy, việc mô phỏng thuật toán sẽ tương đối khó do nó phải gọi đệ qui đến chính nó nhưng cách làm trên thật là dễ hiểu và cho phép chúng ta áp dụng cho nhiều lớp bài toán khác. Chúng ta hãy xét một vài ví dụ.
5.2) Bài toán nhân các số tự nhiên lớn
Xét bài toán nhân 2 số tự nhiên n-bit X và Y. Bài toán nhân 2 số tự nhiên n-bit (n chữ số) đã được dạy trong nhà trường phổ thông với độ phức tạp O(n2)(3). Bây giờ chúng ta sẽ xét lại bài toán này với kỹ thuật Chia để Trị. Ta phân tách mỗi số X, Y thành 2 phần, mỗi phần n/2 bit. Để cho đơn giản ta sẽ luôn xét n là lũy thừa của 2. X, Y sẽ được phân tích thành 2 phần n/2-bit như sau:
X = A | B (X = A2n/2 + B)
Y = C | D
(Y = C2n/2 + D)
Khi đó tích XY sẽ có dạng:
XY = AC2n + (AD+BC)2n/2 + BD (1)
Dựa trên công thức (1) ta có thể suy luận đơn giản như sau cho việc tính tích XY: chúng ta sẽ tính 4 phép nhân với các số n/2-bit là AC, AD, BC và BD, sau đó thực hiện 3 phép cộng với các số 2n-bit, cuối cùng là 2 phép chuyển chữ số (2 phép nhân với lũy thừa của 2) Các phép cộng và phép chuyển chữ số đều được thực hiện với thời gian O(n), do đó ta thu được công thức tính độ phức tạp của phép toán trên T(n) là:
T(1) = 1
T(n) = 4T(n/2) + C.n (C-const)
(2) Công thức (2) cho ta T(n) = O(n2) và như vậy ta chưa thu được kết quả gì mới so với phương pháp tính từ nhà trường phổ thông.
Bây giờ ta biến đổi công thức (1) dưới dạng:
XY = AC2n + ((A-B)(D-C) + AC + BD)2n/2 + BD
(2) Công thức (2) mặc dù phức tạp hơn (1) nhưng chúng có thể được tính bởi:
- 3 phép nhân n/2-bit: AC, BD và (A-B)(D-C).
- 6 phép +,- các số n/2-bit.
- 2 phép chuyển chữ số (nhân với lũy thừa của 2).
Do vậy với cách tính trên ta có công thức sau tính độ phức tạp của thuật toán này:
T(1) = 1
T(n) = 3T(n/2) + C.n (C-const)
(3) Công thức (3) cho ta
chuyển N-1 đĩa từ C sang B. Chú ý rằng khi thực hiện bài toán (b) phần chuyển N-1 đĩa từ C sang B ta có thể dùng lại hoàn toàn thuật toán của bài (a) nhưng với vị trí thay đổi giữa A và C và tất nhiên bỏ qua sự có mặt của đĩa thứ N trong A hay B. Với cách tư duy như vậy, việc mô phỏng thuật toán sẽ tương đối khó do nó phải gọi đệ qui đến chính nó nhưng cách làm trên thật là dễ hiểu và cho phép chúng ta áp dụng cho nhiều lớp bài toán khác. Chúng ta hãy xét một vài ví dụ.
5.2) Bài toán nhân các số tự nhiên lớn
Xét bài toán nhân 2 số tự nhiên n-bit X và Y. Bài toán nhân 2 số tự nhiên n-bit (n chữ số) đã được dạy trong nhà trường phổ thông với độ phức tạp O(n2)(3). Bây giờ chúng ta sẽ xét lại bài toán này với kỹ thuật Chia để Trị. Ta phân tách mỗi số X, Y thành 2 phần, mỗi phần n/2 bit. Để cho đơn giản ta sẽ luôn xét n là lũy thừa của 2. X, Y sẽ được phân tích thành 2 phần n/2-bit như sau:
X = A | B (X = A2n/2 + B)
Y = C | D
(Y = C2n/2 + D)
Khi đó tích XY sẽ có dạng:
XY = AC2n + (AD+BC)2n/2 + BD (1)
Dựa trên công thức (1) ta có thể suy luận đơn giản như sau cho việc tính tích XY: chúng ta sẽ tính 4 phép nhân với các số n/2-bit là AC, AD, BC và BD, sau đó thực hiện 3 phép cộng với các số 2n-bit, cuối cùng là 2 phép chuyển chữ số (2 phép nhân với lũy thừa của 2) Các phép cộng và phép chuyển chữ số đều được thực hiện với thời gian O(n), do đó ta thu được công thức tính độ phức tạp của phép toán trên T(n) là:
T(1) = 1
T(n) = 4T(n/2) + C.n (C-const)
(2) Công thức (2) cho ta T(n) = O(n2) và như vậy ta chưa thu được kết quả gì mới so với phương pháp tính từ nhà trường phổ thông.
Bây giờ ta biến đổi công thức (1) dưới dạng:
XY = AC2n + ((A-B)(D-C) + AC + BD)2n/2 + BD
(2) Công thức (2) mặc dù phức tạp hơn (1) nhưng chúng có thể được tính bởi:
- 3 phép nhân n/2-bit: AC, BD và (A-B)(D-C).
- 6 phép +,- các số n/2-bit.
- 2 phép chuyển chữ số (nhân với lũy thừa của 2).
Do vậy với cách tính trên ta có công thức sau tính độ phức tạp của thuật toán này:
T(1) = 1
T(n) = 3T(n/2) + C.n (C-const)
(3) Công thức (3) cho ta
Như vậy ta đã thu được một kết quả mới cho việc thực hiện phép nhân 2 số tự nhiên n-bit với thuật toán mạnh hơn phép nhân bình thường đã học trong nhà trường (4).
5.3) Bài toán tạo lịch thi đấu Tennis
Giả sử cần lập một lịch thi đấu Tennis cho n = 2k vận động viên (VĐV). Mỗi vận động viên phải thi đấu với lần lượt n-1 vận động viên khác, mỗi ngày thi đấu 1 trận. Như vậy n-1 là số ngày thi đấu tối thiểu phải có. Chúng ta cần lập lịch thi đấu bằng cách thiết lập ma trận có n hàng, n-1 cột. Giá trị số tại vị trí (i,j) (hàng i, cột j) chỉ ra vận động viên cần thi đấu với vận động viên i trong ngày thứ j.
Sử dụng kỹ thuật Chia để Trị, chúng ta hãy lập lịch thi đấu cho nửa (n/2) số vận động viên đầu tiên. Bằng việc sử dụng lời gọi đệ qui chúng ta đưa bài toán về trường hợp chỉ có 2 VĐV.
Chúng ta minh họa bằng trường hợp n=8. Lịch thi đấu cho 4 người đầu tiên của danh sách chiếm nửa trái trên của ma trận (4 hàng, 3 cột). Phần nửa trái dưới (4 hàng, 3 cột) của ma trận là lịch thi đấu của 4 VĐV còn lại (từ 5 đến 8). Phần này thu được từ nửa trái trên bằng cách cộng 4 vào mỗi phần tử tương ứng của ma
Như vậy ta đã thu được một kết quả mới cho việc thực hiện phép nhân 2 số tự nhiên n-bit với thuật toán mạnh hơn phép nhân bình thường đã học trong nhà trường (4).
5.3) Bài toán tạo lịch thi đấu Tennis
Giả sử cần lập một lịch thi đấu Tennis cho n = 2k vận động viên (VĐV). Mỗi vận động viên phải thi đấu với lần lượt n-1 vận động viên khác, mỗi ngày thi đấu 1 trận. Như vậy n-1 là số ngày thi đấu tối thiểu phải có. Chúng ta cần lập lịch thi đấu bằng cách thiết lập ma trận có n hàng, n-1 cột. Giá trị số tại vị trí (i,j) (hàng i, cột j) chỉ ra vận động viên cần thi đấu với vận động viên i trong ngày thứ j.
Sử dụng kỹ thuật Chia để Trị, chúng ta hãy lập lịch thi đấu cho nửa (n/2) số vận động viên đầu tiên. Bằng việc sử dụng lời gọi đệ qui chúng ta đưa bài toán về trường hợp chỉ có 2 VĐV.
Chúng ta minh họa bằng trường hợp n=8. Lịch thi đấu cho 4 người đầu tiên của danh sách chiếm nửa trái trên của ma trận (4 hàng, 3 cột). Phần nửa trái dưới (4 hàng, 3 cột) của ma trận là lịch thi đấu của 4 VĐV còn lại (từ 5 đến 8). Phần này
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links
Last edited by a moderator: