Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Bai Bao Cao Ma Di Tuan

No description
by

Duy Trần Nhật

on 21 May 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Bai Bao Cao Ma Di Tuan

Báo Cáo
Về Bài Toán Mã Đi Tuần Và Thuật Toán Giải

Kết Thúc
Bài toán Mã Đi Tuần
Mã đi tuần (hay hành trình của quân mã) là bài toán về việc di chuyển một quân mã trên bàn cờ vua (kích thước n x n). Quân mã được đặt ở một ô tùy ý trên một bàn cờ trống.
Yêu cầu:
Nó phải di chuyển theo quy tắc của cờ vua để đi qua mỗi ô trên bàn cờ đúng một lần.
Nhóm 1 - 13DTH01
Đại Học Công Nghệ TP. HCM -HUTECH

Cách Di chuyển Của
Quân Mã Trên Bàn Cờ Vua
Mã có thể di chuyển tới ô còn trống hay ô bị quân đối phương chiếm giữ (ăn quân) theo dạng hình chữ L. Quân Mã trong cờ Vua không bị cản như trong cờ tướng
Phân tích - Ý tưởng
- Các vấn đề cần giải quyết lúc này :
+ Biểu diễn bàn cờ bằng ngôn ngữ lập trình
+ Các khả năng lựa chọn ô kế tiếp quân mã có thể bước
+ Cách ghi nhận nghiệm và đánh dấu trạng thái quân mã đã đi qua
+ Thuật toán phù hợp để giải bài toán
...
- Ý tưởng giải bài toán :
Từ vị trí ô bắt đầu của quân mã, tìm vị trí ô kế tiếp quân mã có thể đi thỏa điều kiện quân mã chưa từng bước qua ô kế tiếp đó. Lặp lại công việc trên cho đến khi quân mã đi qua tất cả các ô (ghi nhận nghiệm) hoặc không còn khả năng chọn ô kế tiếp nào khác (chưa đi đến đích).
Biễu diễn bàn cờ
Ta biểu diễn bàn cờ vua bằng một ma trận vuông cấp n (n > 4), ta sử dụng một mảng hai chiều :
int banco[n][n];
Mỗi phần tử của mảng là một số nguyên thể hiện trạng thái của bàn cờ.
Ta quy ước các trạng thái của bàn cờ như sau:
-
banco[x][y] = 0
: tại ô có vị trí (x,y) quân mã chưa đi qua, quân mã có thể bước tiếp được.
-
banco[x][y] = i
: tại ô có vị trí (x,y) quân mã đã đi qua ở bước
i
rồi, nên quân mã không thể bước tiếp được nữa.
Các khả năng lựa chọn ô kế tiếp
để bước của quân mã
Khi quân mã đang đứng ở ô có vị trí (x,y) thì có tất cả 8 ô mà quân mã có khả năng bước tiếp được (như hình vẽ).
Tọa độ của các ô có thể bước tiếp
Để tính được tọa độ của các ô này, ta cần một mảng 2 chiều int m[8][2] để lưu trữ sai biệt về tọa độ giữa ô đang đứng và ô có thể bước tiếp (giá trị của mảng có thể tham khảo hình bên). Khi đó, tọa độ của ô kế tiếp có thể bước được tính như sau:
Xke = x + m[i][1];
Yke = y + m[i][2];
(Với i là các lựa chọn và 0 <= i < 8)
Điều kiện để chấp nhận ô mà quân mã
có thể bước tiếp
Cảm ơn cô và các bạn đã tham dự
Cài đặt chương trình giải bài toán
Mã đi tuần
Thuật toán phù hợp để giải bài toán
Sơ lược về thuật toán quay lui
- Các ô mà quân mã có thể bước tiếp phải nằm trong bàn cờ. Khi quân mã đang đứng ở vị trí gần vị trí biên thì tọa độ ô kế tiếp có thể bước phải không được vượt qua vị trí biên.
(Tức là:
0 <= Xke < n

0 <= Yke < n
).
- Các ô mà quân mã có thể bước tiếp phải là ô mà quân mã chưa đi qua lần nào. Khi đó, các ô đó có trạng thái trên bàn cờ là:
banco[x][y] == 0;

Ý tưởng giải quyết các vấn đề
Cách Ghi Nhận Nghiệm
Nghiệm của bài toán là giá trị của mảng 2 chiều
banco[n][n]
khi và chỉ khi:
+ Tất cả các phần tử trong mảng đều có giá trị từ 1 -> n*n.
(Ta nên dùng thêm 1 biến
buoc
để lưu số bước đi hiện tại mà quân mã đã bước qua. Khi đó biến bước có giá trị
buoc == n*n
)
+ Không có phần tử nào trong mảng bằng 0.
Khi thỏa mãn các điều kiện trên, ta sẽ xuất ra màn hình các nghiệm trên và tạo thành một tập nghiệm của bài toán.
Ngược lại, khi không có nghiệm nào chương trình sẽ không hiển thị gì trên màn hình.
Ở đây, chúng ta sẽ dùng thuật toán quay lui (Backtracking) để giải bài toán này.
Thuật toán Quay lui (Backtracking) dùng để giải các bài toán liệt kê các cấu hình. Mỗi cấu hình được xây dựng bằng cách xây dựng từng phần tử, mỗi phần tử được chọn bằng cách thử tất cả các khả năng. Với thuật toán này cho phép chúng ta giải quyết một số bài toán kinh điển một cách dễ dàng như: Bài toán người giao hàng, bài toán 8 hậu, bài toán tìm đường trong mê cung, bài toán mã đi tuần...

Thuật ngữ Quay lui (Backtrack) lần đầu tiên đề ra bởi nhà toán học người Mỹ D. H. Lehmer vào những năm 1950.
Phương pháp quay lui
Giả sử cấu hình cần liệt kê có dạng (x1, x2, x3, ... , xn). Khi đó thuật toán quay lui thực hiện qua các bước sau:
1) Xét tất cả các giá trị x1 có thể nhận, thử cho x1 nhận lần lượt các giá trị đó. Với mỗi giá trị thử cho x1 ta sẽ:
2) Xét tất cả các giá trị x2 có thể nhận, lại thử cho x2 nhận lần lượt các giá trị đó. Với mỗi giá trị thử gán cho x2 lại xét tiếp các khả năng chọn x3... cứ tiếp tục như vậy đến bước:
n) Xét tất cả các giá trị xn có thể nhận, thử cho xn nhận lần lượt các giá trị đó, thông báo cấu hình tìm được (x1, x2,..., xn).
Mô tả thuật toán quay lui
// Hàm này thử cho Xi nhận lần lượt các giá trị mà nó có thể nhận
void Try( int i ){
for( mọi giá trị có thể gán cho Xi ){
< Thử cho Xi = v >;
if( Xi là phần tử cuối cùng trong cấu hình )
< Thông báo cấu hình tìm được >;
else {
< Ghi nhận việc cho Xi nhận giá trị v (Nếu cần) >;
Try( i+1 ); // Gọi đệ quy để chọn tiếp X(i+1)
< Nếu cần, bỏ ghi nhận việc thử Xi = v , để thử giá trị khác >;
}
}
}
Thuật toán quay lui được mô tả bằng đoạn mã giả (Pseudocode) sau:
Biễu diễn lời gọi hàm Try(1) bằng cây tìm kiếm
Dựa trên mô hình thuật toán quay lui và ý tưởng đã có, ta cài đặt chương trình giải bài toán Mã đi tuần như sau:
Hàm Chuẩn Bị
Dùng để biễu diễn bàn cờ bằng ngôn ngữ lập trình C và đánh dấu vị trí xuất phát của quân mã.
void chuanbi(int banco[MAX][MAX], int n, int x = 0, int y = 0){
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
banco[i][j] = 0;
banco[x][y] = 1;
}
Hàm In Kết Quả
Dùng để xuất ra màn hình một ma trận cấp n là một nghiệm của bài toán.
void inKQ(int banco[MAX][MAX], int n){
for(int i = 0; i < n; i++){
for(int j = 0; j<n; j++)
printf("%4d",banco[i][j]);
printf("\n");
}
}
Hàm Thử
Dùng phương pháp quay lui để tìm ra tất cả các nghiệm có thể có của bài toán.
void thu(int banco[MAX][MAX], int n, int x, int y, int buoc){
int m[8][2] = {{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2}};
for(int i = 0; i < 8; i++){
int Xke = x + m[i][0];
int Yke = y + m[i][1];
if(buoc == n*n){
inKQ(banco,n);
printf("\n");
break;
} else {
if(Xke >= 0 && Xke < n && Yke >= 0 && Yke < n && banco[Xke][Yke] == 0){
banco[Xke][Yke] = buoc + 1;
thu(banco,n,Xke,Yke, buoc+1);
banco[Xke][Yke] = 0;
}
}
}
}
Hàm Main
int main(){
int banco[MAX][MAX];
int n, x, y;
do {
printf("Nhap vao kich thuoc cua ban co (nxn): ");
scanf("%d",&n);
if(n < 3)
printf("Ban nhap sai. Vui long nhap lai. \n");
} while(n < 3);
do {
printf("Nhap vao toa do xuat phat cua quan ma (x , y): ");
scanf("%d%d", &x, &y);
if( x < 0 || x >= n || y < 0 || y >= n)
printf("Ban nhap sai. Vui long nhap lai. \n");
} while( x < 0 || x >= n || y < 0 || y >= n);
chuanbi(banco,n,x,y);
thu(banco,n,x,y);
return 0;
}
Code đầy đủ
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>

#define MAX 100

void chuanbi(int banco[MAX][MAX], int n, int x, int y);
void inKQ(int banco[MAX][MAX], int n);
void thu(int banco[MAX][MAX], int n, int x, int y, int buoc = 1);

int main(){
int banco[MAX][MAX];
int n, x, y;
do {
printf("Nhap vao kich thuoc cua ban co (nxn): ");
scanf("%d",&n);
if(n < 3)
printf("Ban nhap sai. Vui long nhap lai. \n");
} while(n < 3);
do {
printf("Nhap vao toa do xuat phat cua quan ma (x , y): ");
scanf("%d%d", &x, &y);
if( x < 0 || x >= n || y < 0 || y >= n)
printf("Ban nhap sai. Vui long nhap lai. \n");
} while( x < 0 || x >= n || y < 0 || y >= n);
chuanbi(banco,n,x,y);
thu(banco,n,x,y);
return 0;
}

void chuanbi(int banco[MAX][MAX], int n, int x = 0, int y = 0){
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
banco[i][j] = 0;
banco[x][y] = 1;
}

void inKQ(int banco[MAX][MAX], int n){
for(int i = 0; i < n; i++){
for(int j = 0; j<n; j++)
printf("%4d",banco[i][j]);
printf("\n");
}
}

void thu(int banco[MAX][MAX], int n, int x, int y, int buoc){
int m[8][2] = {{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2}};
for(int i = 0; i < 8; i++){
int Xke = x + m[i][0];
int Yke = y + m[i][1];
if(buoc == n*n){
inKQ(banco,n);
printf("\n");
break;
} else {
if(Xke >= 0 && Xke < n && Yke >= 0 && Yke < n && banco[Xke][Yke] == 0){
banco[Xke][Yke] = buoc + 1;
thu(banco,n,Xke,Yke, buoc+1);
banco[Xke][Yke] = 0;
}
}
}
}
Full transcript