kasperskyvn
New Member
Download miễn phí Niên luận bài toán mê cung
MỤC LỤC
Nhận xét của giáo viên 1
Mẫu chấm niên luận 2
Mục lục 3
I. GIỚI THIỆU 4
1. Lời mở đầu 4
2. Đặc tả đề tài 4
II. GIẢI QUYẾT VẤN ĐỀ 4
1- Tạo dữ liệu nguồn 4
2- Nhập 5
3- Thuật toán tìm kiếm theo chiều sâu (dfs) 6
4- int ok 7
5- void chuan bi 8
6- void tim 9
7- void xuly 10
8- void xuat 11
9- void main 12
III. KẾT LUẬN – ĐÁNH GIÁ 13
1- Ưu điểm 13
2- Nhược điểm 13
3- Hướng phát triển 13
IV. PHỤ LỤC 13
1- Hướng dẫn chạy demo 13
2- Tài liệu tham khảo 15
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
MỤC LỤCNhận xét của giáo viên 1
Mẫu chấm niên luận 2
Mục lục 3
I. GIỚI THIỆU 4
1. Lời mở đầu 4
2. Đặc tả đề tài 4
II. GIẢI QUYẾT VẤN ĐỀ 4
1- Tạo dữ liệu nguồn 4
2- Nhập 5
3- Thuật toán tìm kiếm theo chiều sâu (dfs) 6
4- int ok 7
5- void chuan bi 8
6- void tim 9
7- void xuly 10
8- void xuat 11
9- void main 12
III. KẾT LUẬN – ĐÁNH GIÁ 13
1- Ưu điểm 13
2- Nhược điểm 13
3- Hướng phát triển 13
IV. PHỤ LỤC 13
1- Hướng dẫn chạy demo 13
2- Tài liệu tham khảo 15
I. GIỚI THIỆU
1- Lời mở đầu
Trong cuộc sống có nhiều vấn đề bộc ta phải lựa chọn hay tìm ra những phương án để giải quyết được vấn đề. Trong toán học cũng thế để giải một bài toán đòi hỏi ta phải chọn được phương án giải được bài toán một cách tối ưu để thu được kết quả mong muốn. Trong lập trình cũng thế ta phải tìm ra được giải thuật đúng để làm nền tảng xây dựng chương trình chạy đúng kết quả bài toán hay đề tài của người yêu cầu đặt ra. Chẳng hạn như bài toán mê cung, đòi hỏi ta phải xây dựng thuật toán tìm được lối đi từ cửa vào để đến được lối ra. Trong khi đó, có thể đứng trước nhiều ngã rẽ và phải tìm được lối đi cho đến khi thoát khỏi mê cung.
2- Đặc tả đề tài
a- Yêu cầu
- Chương trình phải đọc mê cung từ ma trận kề trên tập tin văn bản.
- Nhập cửa vào, cửa ra.
b- Mục tiêu đạt được
- Tìm được đường đi đến cửa ra.
c- Môi trường làm việc.
- Ngôn ngữ lập trình C.
II. GIẢI QUYẾT VẤN ĐỀ
Tinh thần giải thuật:
Khởi tạo lối đi đầu tiên tại cửa vào, sau đó dùng thuật toán dfs (duyệt theo chiều sâu ) để tìm lối đi. Trong khi tìm lối đi, lối đi có thể đi được nếu không phải là tường ( giá trị 0 trong ma trận kề ). Ngược lại là tường buộc phải quay lui. Trong lúc đi, tại những điểm đi qua đều được đánh dấu. Khi khhong thể đi được nên phải quay lui tại điểm vừa đi qua và cứ như thế cho đến khi đi đến cửa ra. Chương trình được viết như sau:
#include
#include
#define inp "inp.txt"
#define out "out.txt"
int inx,iny,outx,outy;
int x[2500],y[2500],a[50][50],c[50][50],
dx[5]={0,0,1,0,-1},
dy[5]={0,-1,0,1,0};
int m,n,i,j,d,s;
FILE *f;
void nhap()
{
f=fopen(inp,"r");
fscanf(f,"%d %d",&m,&n);
fscanf(f,"%d %d %d %d",&inx,&iny,&outx,&outy);
for (i=0;i
fclose(f);
}
int ok(int i,int j)
{
if ((i=m)||(j=n)) return 0;
if ((a[j]!=0)||(c[j]!=0)) return 0;
return 1;
}
void dfs(int i,int j)
{
if ((i==outx-1)&&(j==outy-1)) d=1;
else
{
int k;
for (k=1;k<=4;++k)
if (ok(i+dx[k],j+dy[k]))
{
c[i+dx[k]][j+dy[k]]=k;
dfs(i+dx[k],j+dy[k]);
}
}
}
void chuanbi()
{
for (i=0;i
c[0][0]=-1;
d=0;
}
void tim()
{
s=0;
x[0]=outx-1;
y[0]=outy-1;
i=outx-1;
j=outy-1;
int k;
while (c[j]!=-1)
{
k=c[j];
i=i-dx[k];
j=j-dy[k];
s++;
x
y
}
}
void xuly()
{
chuanbi();
dfs(inx-1,iny-1);
if (d==1) tim();
}
void xuat()
{
FILE *f;
f=fopen(out,"w");
if (d != 1)fprintf(f,"Noresult");
if (d==1)
{
/*for (i=0;i
for (j=0;j
fprintf(f,"\n");
}*/
fprintf(f,"%d\n",s);
for (i=s;i>=0;i--) fprintf(f,"%4d%4d\n",x,y);
// for (i=s;i>=0;i--) fprintf(f,"%d\n",y);
}
fclose(f);
}
int main()
{
nhap();
xuly();
xuat();
return 0;
}
Tác dụng từng chương trình con được diễn giải như sau:
1- Tạo dữ liệu nguồn.
Tạo dữ liệu nguồn là ma trận kề được viết trên tập tin văn bản là file “inp.txt” để tạo thành mê cung trong đó 0 là lối đi được và 1 là tường nên không đi được và buộc phải quay lui. Và thiết lập lối ra để thoát khỏi mê cung với file “out.txt”
Inp.txt
10 10
1 1 10 10
0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 0 1
1 0 0 0 0 0 0 0 0 1
1 0 1 1 1 1 1 1 0 1
1 0 0 0 0 0 1 0 1 1
1 1 1 0 1 0 1 0 1 1
1 0 0 0 0 0 1 0 0 1
1 0 1 1 1 1 1 1 0 1
0 0 0 0 0 0 0 0 1 0
0 1 1 1 1 1 1 0 0 0
Out.txt
36
0 0 2 4 8 2
0 1 2 3 8 3
0 2 2 2 8 4
0 3 2 1 8 5
0 4 3 1 8 6
0 5 4 1 8 7
0 6 4 2 9 7
0 7 4 3 9 8
0 8 5 3 9 9
1 8 6 3
2 8 6 2
2 7 6 1
2 6 7 1
2 5 8 1
Trong đó lệnh FILE *f dùng để gọi tập tin văn bản vào chương trình:
- Gán f = fopen (inp,”r”).
- Inp là đường dẫn đến tập tin ta cần gọi ( ví dụ: (“f:\inp.txt”,”r”)).
- fclose ( f ) là lệnh đóng tập tin vừa gọi.
2- Nhập
Sau khi đọc ma trận kề và chuyển từ ma trận kề sang mê cung được minh họa bởi đoạn code và sơ đồ khối sau:
void nhap()
{
f=fopen(inp,"r");
fscanf(f,"%d %d",&m,&n);
fscanf(f,"%d %d %d %d",&inx,&iny,&outx,&outy);
for (i=0;i
fclose(f);
}
f = fopen (inp,”r”)
i<001
end
j<01
i ++
a[j]
j ++
Begin
3- Thuật toán tìm kiếm theo chiều sâu ( dfs )
Để tìm được đường đi đến lối ra trong mê cung thì phải biết tìm đường đi trong mê cung. Điều quan trọng là khi đứng trước nhiều ngã rẽ hay khi đi đến đường cùng phải biết quay lui để tìm lối đi khác. Và để tránh đi lại lối đi cũ thì phải đánh dấu lối đi đã đi qua. Cho nên để giải quyết vấn đề này em đã sử dụng giải thuật tìm kiếm theo chiều sâu (dfs ). Thuật toán được mô tả thông qua đoạn code và lưu đồ khối sau:
(i = = m-1)&&(j = = n-1)
K=1
K<= 4
Ok ( i + dx[k], j + dy[k] )
Begin
dfs(i + dx[k], j + dy[k])
End
C++
void dfs(int i,int j)
{
if ((i= =outx-1)&&(j= =outy-1)) d=1;
else
{
int k;
for (k =1;k<= 4;++k)
if (ok(i+dx[k],j+dy[k]))
{
c[i+dx[k]][j+dy[k]]=k;
dfs(i+dx[k],j+dy[k]);
}
}
}
4- int ok
Là đoạn chương trình dùng để nhận biết lối đi được và tường thể hiện qua đoạn code và lưu đồ sau:
Begin
(im)||(j=n)
a [j]!=0||c[j]=0
0
End
1
0
int ok(int i,int j)
{
if ((i= m)||(j= n)) return 0; // lối đi
if ((a[j]!=0)||(c[j]!=0)) return 0; // lối đi
return 1; // tường
}
5- void chuanbi
Hàm được gọi khi không thể đi được và bắt buộc phải quay lui. Khi gặp tường chắn nên không thể đi được buộc phải quay lui lại điểm vừa đi qua để tiếp tục tìm đường đi tiếp. Đồng thời đánh dấu lối vừa đi để tránh việc lặp lại.
void chuanbi()
{
for (i = 0 ; i
c[0][0] = -1; // lui lại điểm vừa đi qua
d = 0; // đánh dấu nơi đã đi qua
}
i = 0; j =0
i < m
j < n
i ++
d =0
End
c[j] = 0; c[0][0] = -1
j ++
Begin
6- void tim
Đoạn chương trình này dùng để tìm đường đi đến cửa ra được đặc tả như sau:
void tim()
{
s=0;
x[0]=outx-1;
y[0]=outy-1; khi lối đi không thể đi được và phải quay lui
i=outx-1;
j=outy-1;
int k;
while (c[j]!=-1)
{
k=c[j];
i=i-dx[k]; khi lối đi còn đi được và không phải quay lui
j=j-dy[k];
s++;
x
S = 0; x[0] = m-1; y[0] = n-1; j = n-1; i = m-1
C[j] != -1
End
K= c[j]; i = i – dx[k]; j = j – dy[k]
S++
x
y
Begin
y
}
}
7- void xuly
Chương trình con void xuly dùng để gọi các chương trình con khác để tìm đường đi trong mê cung nếu gặp đường đã đi qua thì gọi chương trình con void tim để tiếp tục đi đến lối ra.
void xuly()
{
chuanbi();
dfs(inx-1,iny-1);
if (d= =1) tim();
}
S = 0; x[0] = m-1; y[0] = n-1; j = n-1; i = m-1
C[j] != -1
End
K= c[j]; i = i – dx[k]; j = j – dy[k]
S++
x
y
Begin
8- void xuat
Chương trình con void xuat dùng để truy xuất kết quả ra màn hình và trả kết quả là Noseult nếu không tìm thấy cửa ra. Chương trình được đặc tả như sau:
Begin
f = fopen(out,”w”);
d !=1
Noresult
i = s
i >=0
f, “%d\n”,y[j]
i--
Fclose(f)
End
void xuat()
{
FILE *f;
f=fopen(out,"w");
if (d != 1)fprintf(f,...