Thuật toán chia để trị
- 12 trang
- file .doc
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) hoặc 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:
2
- 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;
3
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ỏ
4
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.
5
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
6
trận. Để điền nốt các phần còn lại của ma trận chúng ta chỉ cần xác định lịch thi
đấu giữa các VĐV với số thấp (≤n/2) với các VĐV với số cao (≥n/2). Để làm việc
này chúng ta xếp các VĐV từ 1 đến n/2 đấu lần lượt với các VĐV số cao vào ngày
4. Các ngày còn lại thu được từ ngày 4 bằng cách hoán vị vòng quanh các VĐV
với số thứ tự cao. Quá trình điền số được mô tả trong hình 2. Các bạn có thể tổng
quát quá trình này cho trường hợp tổng quát n=2k bất kỳ.
5.6) Giải và cài đặt bài toán Mảng con lớn nhất
Bài toán mảng con lớn nhất: Mảng a’ = {ap, ..., aq} với 1<=p,q<=n được gọi là
mảng con của a.
Ta gọi trọng lượng của mảng con là tổng các phần tử của nó.
Cho mảng số a = {a1, a2, ..., an}.
Vấn đề đặt ra là trong số các mảng con của a hãy tìm mảng con có trọng lượng lớn
nhất. Mảng như vậy gọi là mảng con lớn nhất.
Để đơn giản chỉ xét bài toán trọng lượng của mảng con lớn nhất (không cần tìm vị
trí của p và q).
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:
– Chia: Chia mảng a thành 2 mảng con với chênh lệch độ dài là ít nhất, ký hiệu
là aL và aR.
– Trị: Tính mảng con lớn nhất của mỗi nửa một cách đệ quy.
Gọi wL và wR là trọng lượng của các mảng con lớn nhất của aL và aR tương
ứng.
– Tổng hợp: Thoạt tiên có thể nghĩ đến kết quả cần tìm là max(wL,wR). Tuy
nhiên phải tính đến tình huống mảng con lớn nhất nằm đè nên điểm chia.
5.6.2) Thuật toán chia để trị tìm mảng con lớn nhất
function MaxSubVector(a, i, j);
begin
if i=j then MaxSubVector := a[i]
else
begin
m := (i+j)/2;
wL := MaxSubVector(a, i, m);
wR := MaxSubVector(a,m+1,j);
wM := MaxVector(a, i, m) + MaxVector(a, m+1, j);
MaxS
7
ubVector := max(wL, wR, wM);
end;
end;
5.6.3) Thuật toán MaxVector(a, i, j):
function MaxVector(a, i, j);
begin
maxsum := -∞; sum := 0;
for k:=j downto i do
begin
sum := sum + a[k];
maxsum := max(sum, maxsum);
end;
MaxVector := maxsum;
end;
5.6.4) Cài đặt chương trình
#include
#include
#include
/*nhập dữ liệu*/
void nhap(int n,int *a)
{
int i;
printf("nhap cac phan tu");
for(i=0;i<=n-1;i++)
{
printf("a[%d]=",i);
scanf("%d",&a[i]);
}
}
/*Hiển thị dữ liệu đã nhập */
void hienthi(int n,int *a)
{
int i;
for(i=0;i<=n-1;i++)
{
8
printf("a[%d]=%d",i,a[i]);
printf("\n");
}
}
/*Hàm mảng con lớn nhất để đưa ra mảng con có giá trị lớn nhất
bằng bao nhiêu*/
int mangconlonnhat(int n,int *a)
{
int i,j,k,max,s;
max=a[0];
for(i=0;i<=n-1;i++)
for(j=0;j<=n-1;j++)
{
s=0;
for(k=i;k<=j;k++)
s=s+a[k];
if(s>max) max=s;
else
max=max;
}
return max;
}
main()
{
int n ,a[5];
printf("nhap so phan tu can nhap");
scanf("%d",&n);
nhap(n,a);
hienthi(n,a);
printf("gia tri lon nhat la %d",mangconlonnhat(n,a));
getch();
}
*Sử dụng thuật toán chia để trị
#include
#include
#include
9
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) hoặc 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:
2
- 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;
3
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ỏ
4
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.
5
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
6
trận. Để điền nốt các phần còn lại của ma trận chúng ta chỉ cần xác định lịch thi
đấu giữa các VĐV với số thấp (≤n/2) với các VĐV với số cao (≥n/2). Để làm việc
này chúng ta xếp các VĐV từ 1 đến n/2 đấu lần lượt với các VĐV số cao vào ngày
4. Các ngày còn lại thu được từ ngày 4 bằng cách hoán vị vòng quanh các VĐV
với số thứ tự cao. Quá trình điền số được mô tả trong hình 2. Các bạn có thể tổng
quát quá trình này cho trường hợp tổng quát n=2k bất kỳ.
5.6) Giải và cài đặt bài toán Mảng con lớn nhất
Bài toán mảng con lớn nhất: Mảng a’ = {ap, ..., aq} với 1<=p,q<=n được gọi là
mảng con của a.
Ta gọi trọng lượng của mảng con là tổng các phần tử của nó.
Cho mảng số a = {a1, a2, ..., an}.
Vấn đề đặt ra là trong số các mảng con của a hãy tìm mảng con có trọng lượng lớn
nhất. Mảng như vậy gọi là mảng con lớn nhất.
Để đơn giản chỉ xét bài toán trọng lượng của mảng con lớn nhất (không cần tìm vị
trí của p và q).
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:
– Chia: Chia mảng a thành 2 mảng con với chênh lệch độ dài là ít nhất, ký hiệu
là aL và aR.
– Trị: Tính mảng con lớn nhất của mỗi nửa một cách đệ quy.
Gọi wL và wR là trọng lượng của các mảng con lớn nhất của aL và aR tương
ứng.
– Tổng hợp: Thoạt tiên có thể nghĩ đến kết quả cần tìm là max(wL,wR). Tuy
nhiên phải tính đến tình huống mảng con lớn nhất nằm đè nên điểm chia.
5.6.2) Thuật toán chia để trị tìm mảng con lớn nhất
function MaxSubVector(a, i, j);
begin
if i=j then MaxSubVector := a[i]
else
begin
m := (i+j)/2;
wL := MaxSubVector(a, i, m);
wR := MaxSubVector(a,m+1,j);
wM := MaxVector(a, i, m) + MaxVector(a, m+1, j);
MaxS
7
ubVector := max(wL, wR, wM);
end;
end;
5.6.3) Thuật toán MaxVector(a, i, j):
function MaxVector(a, i, j);
begin
maxsum := -∞; sum := 0;
for k:=j downto i do
begin
sum := sum + a[k];
maxsum := max(sum, maxsum);
end;
MaxVector := maxsum;
end;
5.6.4) Cài đặt chương trình
#include
#include
#include
/*nhập dữ liệu*/
void nhap(int n,int *a)
{
int i;
printf("nhap cac phan tu");
for(i=0;i<=n-1;i++)
{
printf("a[%d]=",i);
scanf("%d",&a[i]);
}
}
/*Hiển thị dữ liệu đã nhập */
void hienthi(int n,int *a)
{
int i;
for(i=0;i<=n-1;i++)
{
8
printf("a[%d]=%d",i,a[i]);
printf("\n");
}
}
/*Hàm mảng con lớn nhất để đưa ra mảng con có giá trị lớn nhất
bằng bao nhiêu*/
int mangconlonnhat(int n,int *a)
{
int i,j,k,max,s;
max=a[0];
for(i=0;i<=n-1;i++)
for(j=0;j<=n-1;j++)
{
s=0;
for(k=i;k<=j;k++)
s=s+a[k];
if(s>max) max=s;
else
max=max;
}
return max;
}
main()
{
int n ,a[5];
printf("nhap so phan tu can nhap");
scanf("%d",&n);
nhap(n,a);
hienthi(n,a);
printf("gia tri lon nhat la %d",mangconlonnhat(n,a));
getch();
}
*Sử dụng thuật toán chia để trị
#include
#include
#include
9