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

Ta dùng mảng a lưu trữ các sai khác về chỉ số hàng của các ô trên so với x và dùng mảng b lưu trữ caùc sai khác về chỉ số cột của các ô trên so với y thì mảng a và mảng b sẽ được khởi tạo như sau:

Mảng a:

Mảng b:

a[0] = 2;

a[1] = 1;

a[2] = -1;

a[3] = -2;

a[4] = -2;

a[5] = -1;

a[6] = 1;

a[7] = 2;

b[0] = 1;

b[1] = 2;

b[2] = 2;

b[3] = 1;

b[4] = -1;

b[5] = -2;

b[6] = -2;

b[7] = -1;

Dùng một biến chỉ số k để đánh số các bước đi tiếp theo có thể thì việc duyệt các bước đi tiếp theo có thể được diễn tả là:

for(k = 0; k <= 7; k++) u = x + a[k];

v = y + b[k];

Điều kiện <chấp nhận được> có thể được biểu diễn như kết hợp của các điều

kiện :

Ô mới phải thuộc bàn cờ (1 ≤ u ≤ n và 1 ≤ v ≤ n) và ngựa chưa đi qua ô đó,

nghĩa là h[u,v] = 0;

* Để ghi nhận nước đi hợp lệ ở bước i, ta gán h[u][v] = i (ghi nhận trạng

thái); và để hủy một nước đi thì ta gán h[u][v] = 0 (hoàn trả trạng thái).

* Ma trận h ghi nhận kết quả nghiệm. Nếu có <x,y> sao cho h<x,y> = 0 thì không có đường đi , còn ngược là h chứa đường đi của ngựa.

Thuật toán có thể mô tả như sau :

Input n, //Kích thước bàn cờ

x, y;//Toạ độ xuất phát ở bước i Output h;

Try(i, x, y)

{

for(k = 0; k <= 7; k++)

{

u = x + a[k];

v = y + b[k];

if (1 <= u ,v <= n &&h[u][v] == 0)

{

h[u][v] = i; if (i < n*n)

Try(i+1,u,v);

else

in(); // In ma trận h

h[u][v] = 0;

}

có)

Hàm in(): hàm này sẽ in hành trình của ngựa được lưu trong ma trận h (nếu

Hàm init(): nhập n, khởi tạo giá trị 0 cho tất cả các phần tử của mảng h. Khi đó ta có chương trình chính:

main()

{

init();

h[x0 ][y0 ] = 1;

try(2,x0 , y0);

}

Với n=5 và x0=1, y0=1 thì thuật toán cho một trong các lời giải là:

6	15	10	21
14	9	20	5	16
19	2	7	22	11
8	13	24	17	4
25	18	3	12	23

Có thể bạn quan tâm!

Xem toàn bộ 205 trang tài liệu này.

Hình 4.2. Một lời giải

Nếu chọn ô xuất phát chẳng hạn là (2,3) thì bài toán không có lời giải.

BÀI TẬP CHƯƠNG 4

1.Cho một dãy số nguyên a1, a2, ..., an và một số nguyên S. Liệt kê tất cả các cách phân tích S = ai1 + ai2 + ... + aik (ai1, ai2, ..., aik là các số của dãy đã cho)

Hướng dẫn:

Với mỗi giá trị k từ 1 đến n ta xây dựng các tập con gồm k phần tử của dãy số nguyên a1, a2, ..., an. Với mỗi tập con này ta tính tổng các phần tử của nó, nếu tổng bằng S thì hiển thị tổng đó ra.

Ta áp dụng thuật toán quay lui để liệt kê các cách phân tích S = ai1 + ai2 + ...

+ aik

Sử dụng :

- Mảng a để lưu trữ n số nguyên a1, a2, ..., an

- Mảng b với các phần tử b[i] dùng để ghi nhận chỉ số của phần tử của mảng

a. Phần tử có chỉ số này của mảng a được gán cho c[i].

- Mảng c dùng để lưu trữ tập con gồm k phần tử xây dựng được.

- Hàm khoitao để nhập n, nhập S, nhập n số nguyên a1, a2, ..., an

- Hàm Try để xây dựng các tập con gồm k phần tử.

- Hàm ht để hiển thị ra tổng thoả mãn điều kiện. Với mỗi tập con gồm k phần tử lấy từ n số nguyên a1, a2, ..., an, hàm ht sẽ kiểm tra xem tổng của k phần tử này có bằng S không? Nếu bằng thì hiển thị tổng đó ra.

try(int i)

{int j;

for(j=b[i-1]+1;j<=n-k+i;j++)

{ b[i]=j;

c[i]=a[j];

if(i==k) ht(c); else try(i+1);

}

main()

{

khoitao();

for(k=1;k<=n;k++) try(1);

getch();

2. Cho một dãy gồm n số nguyên a1, a2, ..., an. Hãy đưa ra các tổng đại số thành lập được từ dãy này mà có tổng bằng 0.

Ví dụ: Cho các số nguyên 1, 2, 3, 4, 5, 6, 7 thì một tổng đại số bằng 0 thành lập được là:

- 1 + 2 - 3 -4 + 5 - 6 + 7 =0

Hướng dẫn:

Ta phải điền các dấu + hoặc - vào các số từ a1 đến an. Áp dụng thuật toán quay lui để giải quyết bài toán này, ta sẽ dùng hàm đệ quy Try(i). Giả sử ta đã điền các dấu’+’ và ’-’ vào các số từ a1 đến ai, bây giờ cần điền dấu cho ai + 1. Ta có thể chọn một trong hai khả năng: hoặc là điền dấu ’+’, hoặc là điền dấu ’-’ bằng cách gọi đệ quy Try(i+1). Ta sẽ lần lượt duyệt tất cả các khả năng đó để tìm tất cả các nghiệm của bài toán.

Nếu i=n ta được một tổng đại số, khi đó kiểm tra xem tổng đại số đó có kết quả bằng 0 hay không. Nếu bằng 0 thì đưa ra tổng đó, ngược lại thì không đưa ra. Ta dùng hàm in() để thực hiện điều này

Dùng mảng b mà phần tử bi lưu trữ dấu của số nguyên ai. Qui ước chẳng hạn 0 ứng với dấu + và 1 ứng với dấu - tức là:

Nếu bi =0 thì dấu của ai là +

Nếu bi =1 thì dấu của ai là - Try(i)

{

}

in()

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

{

b[i]:=j;

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

}

{

s=0;

for(i=1;i<=n;i++) if(b[i]==0)

s=s+a[i]; else

s= s-a[i];

if(s==0) // hiển thị tổng đại số for(i=1;i<=n;i++)

if((i==1)&&(b[i]==0))// phần tử đầu dấu + không cần đưa ra dấu printf(a[i]);

else

if(b[i]==0)

printf("+",a[i]); else

printf("-",a[i]);

}

3. Liệt kê các số có 6 chữ số với các chữ số khác nhau sao cho trong các số đó thì tổng 3 chữ số đầu bằng tổng 3 chữ số cuối.

Hướng dẫn:

Các số có 6 chữ số có dạng

a1a2 a3 a4 a5 a6

trong đó a1 nhận một trong các

giá trị từ 1 đến 9, các chữ số a2, a3, a4, a5, a6 mỗi chữ số có thể nhận một trong các giá trị từ 0 đến 9. Ta dùng thuật toán quay lui thực hiện liệt kê các số thoả mãn điều kiện.

- Mảng a để lưu trữ số có 6 chữ số khác nhau tìm được (ở đây ta chấp nhận cả số mà chữ số đầu tiên bằng 0, khi hiển thị ta không quan tâm tới những số này)

- Mảng b mỗi phần tử dùng để ghi nhận một chữ số đã được dùng hay chưa.

Nếu b[j]=0 thì chữ số j chưa được dùng, nếu b[j]=1 thì chữ số j đã được dùng

- Hàm khoitao: khởi tạo giá trị các phần tử mảng b và biến d (biến d dùng để dếm các số thoả mãn điều kiện)

ra.

- Hàm ht kiểm tra số vừa tìm được, nếu thoả mãn điều kiện thì hiển thị số đó

- Hàm try để xây dựng các số có 6 chữ số khác nhau.

main()

{

khoitao(); try(1);

getch();

}

khoitao()

{for(i=0;i<=9;i++)b[i]=0; d=0;

}

ht(x)

{

if((x[1]!=0)&&(x[1]+x[2]+x[3]==x[4]+x[5]+x[6]))

{ d++;

printf("n%d: ",d); for(i=1;i<=6;i++)printf("%d",x[i]);

}

try(i)

{

for(j=0;j<=9;j++) if(b[j]==0)

{

a[i]=j;

b[j]=1;

if(i==6) ht(a);

else

try(i+1);

b[j]=0;

}

4. Liệt kê các chỉnh hợp không lặp chập k của n số nguyên a1, a2, ..., an (k  n).

Hướng dẫn:

Ta áp dụng thuật toán quay lui để liệt kê các chỉnh hợp không lặp chập k của tập n số nguyên a1, a2, ..., an.

- Mảng a để lưu trữ n số nguyên a1, a2, ..., an

- Mảng b với các phần tử b[i] dùng để ghi nhận số nguyên tương ứng a[i] đã được dùng chưa. Nếu b[i]= 0 thì số nguyên a[i] chưa được dùng, nếu b[i]= 1 thì số nguyên a[i] đã được dùng. Đầu tiên b[i] = 0 với mọi i.

- Mảng c dùng để lưu trữ chỉnh hợp không lặp chập k của tập n số nguyên a1, a2, ..., an xây dựng được.

- Biến d để đếm số chỉnh hợp không lặp chập k của tập n số nguyên a1, a2, ...,

an.

- Hàm khoitao để nhập n, nhập k, khởi tạo biến đếm d, khởi tạo giá trị cho

các phần tử của mảng b.

- Hàm nhap để nhập các số nguyên.

- Hàm Try để xây dựng các chỉnh hợp không lặp chập k của tập n số nguyên a1, a2, ..., an.

- Hàm ht để hiển thị ra chỉnh hợp không lặp chập k của tập n số nguyên a1, a2, ..., an vừa xây dựng được.

main()

{

khoitao(); nhap();

try(1);

getch();

}