Đưa Ra Các Hoán Vị Của N Số Nguyên

được kết quả (số ngày ít nhất cần tổ chức thi ).

4. Bài toán trả tiền của máy rút tiền tự động ATM.

Trong máy rút tiền tự động ATM, ngân hàng đã chuẩn bị sẵn các loại tiền có mệnh giá 100.000 đồng, 50.000 đồng, 20.000 đồng và 10.000 đồng. Giả sử mỗi loại tiền đều có số lượng không hạn chế. Khi có một khách hàng cần rút một số tiền n đồng (tính chẵn đến 10.000 đồng, tức là n chia hết cho 10000). Hãy dùng kỹ thuật tham lam xây dựng thuật toán tìm phương án trả tiền sao cho trả đủ n đồng và số tờ giấy bạc phải trả càng ít càng tốt. Đánh giá độ phức tạp tính toán của thuật toán.

Hướng dẫn:

Gọi X = (X1, X2, X3, X4) là một phương án trả tiền, trong đó X1 là số tờ giấy bạc mệnh giá 100.000 đồng, X2 là số tờ giấy bạc mệnh giá 50.000 đồng, X3 là số tờ giấy bạc mệnh giá 20.000 đồng và X4 là số tờ giấy bạc mệnh giá 10.000 đồng. Theo yêu cầu ta phải có X1 + X2 + X3 + X4 nhỏ nhất và X1 * 100.000 + X2 * 50.000 + X3 * 20.000 + X4 * 10.000 = n.

Áp dụng kĩ thuật tham lam để giải bài toán này là: để có số tờ giấy bạc phải trả (X1 + X2 + X3 + X4) nhỏ nhất thì các tờ giấy bạc mệnh giá lớn phải được chọn nhiều nhất.

Trước hết ta chọn tối đa các tờ giấy bạc mệnh giá 100.000 đồng, nghĩa là X1 là số nguyên lớn nhất sao cho X1 * 100.000 ≤ n. Tức là X1 = n DIV 100.000.

Chảng hạn khách hàng cần rút 1.290.000 đồng (n = 1290000), phương án trả tiền như sau:

X1 = 1290000 DIV 100000 = 12.

Số tiền cần rút còn lại là 1290000 – 12 * 100000 = 90000. X2 = 90000 DIV 50000 = 1.

Số tiền cần rút còn lại là 90000 – 1 * 50000 = 40000. X3 = 40000 DIV 20000 = 2.

Số tiền cần rút còn lại là 40000 – 2 * 20000 = 0. X4 = 0 DIV 10000 = 0.

Ta có X = (12, 1, 2, 0), tức là máy ATM sẽ trả cho khách hàng 12 tờ 100.000 đồng, 1 tờ 50.000 đồng và 2 tờ 20.000 đồng.

5. Chỉ ra việc sử dụng kỹ thuật tham lam trong thuật toán Kruskal giải bài toán cây khung nhỏ nhất và đánh giá độ phức tạp tính toán của thuật toán.

4.1. Nội dung kỹ thuật

Chương 4

KỸ THUẬT QUAY LUI

Nét đặc trưng của kỹ thuật quay lui là các bước hướng tới lời giải hoàn toàn được làm thử. Tại mỗi bước, nếu có một lựa chọn được chấp nhận thì ghi nhận lựa chọn này và tiến hành các bước thử tiếp theo. Ngược lại nếu không có lựa chọn nào thích hợp thì làm lại bước trước, xoá bỏ sự ghi nhận và quay về chu trình thử các lựa chọn còn lại.

Hµnh ®éng nµy ®•îc gäi lµ quay lui, thuật toán sử dụng kỹ thuật này là thuật toán quay lui.

Lời giải của bài toán thường được biểu diễn bằng một bộ gồm n thành phần x

= (x1,.., xn ) phải thoả mãn các điều kiện nào đó. Để chỉ ra lời giải x, ta phải xây dựng dần các thành phần xi.

Nhu vậy nội dung chính của kỹ thuật này là việc xây dựng dần các thành phần xi bằng cách thử tất các khả năng. Giả sử đã xác định được i -1 thành phần x1, x2,…, xi-1 (mà ta sẽ gọi là lời giải bộ phận cấp i- 1), bây giờ ta xác định thành phần xi bằng cách duyệt tất cả các khả năng có thể đề cử cho nó (đánh số các khả năng từ 1 đến ni ). Với mỗi khả năng j, kiểm tra xem j có chấp nhận được không. Xảy ra hai trường hợp:

- Nếu chấp nhận j thì xác định xi theo j. Sau đó nếu i = n thì ta được một cấu hình, còn trái lại ta tiến hành xác định xi+1.

- Nếu thử tất cả các khả năng mà không có khả năng nào chấp nhận được thì quay lại bước trước để xác định lại xi-1.

Điểm quan trọng của thuật toán là phải ghi nhớ tại mỗi bước đã đi qua những khả năng nào đã thử để tránh trùng lặp. Rò ràng những thông tin này cần được lưu trữ theo cơ cấu ngăn xếp (Stack- Vào sau ra trước). Vì thế kỹ thuật này rất phù hợp với việc lập trình trên một ngôn ngữ cho phép gọi đệ qui. Bước xác định xi có thể diễn tả qua hàm được tổ chức đệ qui dưới đây:

Try(i)

{

for(j=1;j<ni;j++) if (<chấp nhận j>)

{

<Xác định xi theo j>

if (i == n) <ghi nhận một cấu hình>; else try(i+1);

}

Phần quan trọng nhất trong hàm trên là việc đưa ra một danh sách các khả năng đề cử và việc xác định giá trị biểu thức <Chấp nhận j> thông thường giá trị này, ngoài việc phụ thuộc j, còn phụ thuộc vào việc đã chọn các khả năng tại i -1 bước trước. Trong những trường hợp như vậy, cần ghi nhớ trạng thái mới của quá trình tìm kiếm sau khi <xác định xi theo j> và trả lại trạng thái cũ sau lời gọi Try(i+1). Các trạng thái này được ghi nhận nhờ một số biến tổng thể, gọi là biến trạng thái.

Sau khi xây dựng thủ tục đệ qui Try, đoạn chương trình chính giải bài toán liệt kê có dạng:

main()

{

Init;

Try(1);

}

trong đó Init là hàm khởi tạo các giá trị ban đầu (nhập các giá trị tham số, của bài toán, khởi gán các biến trạng thái, biến đếm, ...

Người ta đã chứng tỏ được rằng độ phức tạp tính toán của các thuật toán quay lui thường là hàm mũ. Ta công nhận điều này và trong các ví dụ áp dụng ta sẽ không đặt vấn đề xác định độ phức tạp tính toán của các thuật toán.

Kỹ thuật quay lui thường được áp dụng cho các bài toán liệt kê tổ hợp.

4.2. Các ví dụ áp dụng

4.2.1. Đưa ra các dãy nhị phân độ dài n

1) Bài toán

Cho một số nguyên dương n. Hãy đưa ra các dãy nhị phân độ dài n

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

Biểu diễn dãy nhị phân dưới dạng (b1, b2,…, bn), trong đó bi{0,1}.

Mỗi thành phần bi có các giá trị đề cử là 0 và 1. Các giá trị này mặc nhiên được chấp nhận mà không phải thoả mãn điều kiện gì.

Mảng b lưu trữ dãy nhị phân xây dựng được.

Hàm Try(i) xác định thành phần thứ i và hàm Result() đưa ra dãy tìm được. result()

{

printf("n"); for(i=1;i<=n;i++) printf(b[i]);

}

Try(i)

{

for(j=0;j<=1;j++)

{

b[i]:=j;

if(i==n) result(); else try(i+1);

}

main()

{

scanf(n);

try(1);

getch();

}

4.2.2. Đưa ra các hoán vị của n số nguyên

1) Bài toán

Cho X = { x1, x2, ..., xn}, trong đó xi (i=1, 2, ...,n) là các số nguyên Hãy đưa ra tất cả các hoán vị của X.

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

Ta nhận thấy rằng mỗi một hoán vị của tập X tương đương với một hoán vị của tập chỉ số {1, 2, ..., n}

Biểu diễn hoán vị tập chỉ số dưới dạng a1, a2, …, an trong đó ai nhận giá trị từ 1 đến n và ai  aj với i  j. Các giá trị từ 1 đến n được lần lượt đề cử cho ai, trong đó giá trị j được chấp nhận nếu nó chưa được dùng. Vì thế cần phải ghi nhớ đối với mỗi giá trị j xem nó đã được dùng hay chưa. Điều này được thực hiện nhờ một dãy biến bj, trong đó bj bằng 1 nếu j chưa được dùng. Sau khi xác định ai theo j cần gán giá trị 0 cho bj. Khi thực hiện xong Result hay Try(i+1) cần phải gán lại giá trị 1 cho bj.

Tổ chức dữ liệu:

- Mảng x: dãy số nguyên đã cho

- Mảng a: lưu trữ một hoán vị của tập chỉ số {1, 2, ..., n}

- Mảng b: lưu trữ trạng thái các phần tử của x với b[j]=1 thì x[j] đã được dùng, b[j]=0 thì x[j] chưa được dùng.

Các hàm

- Hàm init(): nhập n và khởi tạo

- Hàm result(): đưa ra hoán vị vừa tìm được

- Hàm Try(i): xác định thành phần thứ i của hoán vị. init()

{

scanf(n); for(i=1;i<=n;i++) b[i]=1; end;

result()

{

for(i=1;i<=n;i++) printf(x[a[i]]);

}

Try(i)

{

for(i=1;i<=n;i++)

if(b[j]==1)

{

a[i]=j;

b[j]=0;

if(i==n) result(); else try(i+1); b[j]:=true;

}

main()

{

init();

try(1);

getch();

}

4.2.3. Đưa ra các tập con của tập gồm n số nguyên

1) Bài toán

Cho X = {x1, x2, ..., xn}, trong đó xi (i=1, 2, ...,n) là các số nguyên. Hãy đưa ra tất cả các tập con gồm m (m<=n) phần tử của X .

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

Mỗi tập con của X gồm m phần tử tương đương với một tập con gồm m phần tử của tập chỉ số {1, 2, ..., n}

Mỗi tập con gồm m phần tử của tập chỉ số {1, 2, ..., n} có thể biểu diễn bởi bộ có thứ tự gồm m thành phần a = (a1, a2, ... , am) thỏa mãn

1 a1 < a2 < .... <am  n

Trên tập các tập con gồm m phần tử của tập chỉ số {1, 2, ..., n} ta xác định một thứ tự như sau:

Ta nói tập con a = (a1, a2, ... , am) đi trước tập con a’ = (a1’, a2’, ... , am’) nếu tìm được chỉ số k (1 k  m) sao cho:

a1 = a’1

a2= a’2

ak-1 = a’k-1 ak < a’k.

Chẳng hạn X = {1, 2, 3, 4, 5} thì các tập con gồm 3 phần tử của X được liệt kê theo thứ tự từ điển như sau:

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