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 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 hoặc 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<m;++i) for (j=0;j<n;++j) fscanf(f,"%d",&a[i][j]); fclose(f); } int ok(int i,int j) { if ((i=m)||(j=n)) return 0; if ((a[i][j]!=0)||(c[i][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<m;++i) for (j=0;j<n;++j) c[i][j]=0; 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[i][j]!=-1) { k=c[i][j]; i=i-dx[k]; j=j-dy[k]; s++; x[s]=i; y[s]=j; } } 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<m;++i) { for (j=0;j<n;++j) if (c[i][j]!=0) fprintf(f,"1 ");else fprintf(f,"0 "); fprintf(f,"\n"); }*/ fprintf(f,"%d\n",s); for (i=s;i>=0;i--) fprintf(f,"%4d%4d\n",x[i],y[i]); // for (i=s;i>=0;i--) fprintf(f,"%d\n",y[i]); } 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<m;++i) for (j=0;j<n;++j) fscanf(f,"%d",&a[i][j]); fclose(f); } f = fopen (inp,”r”) i<001 end j<01 i ++ a[i][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 [i][j]!=0||c[i][j]=0 0 End 1 0 int ok(int i,int j) { if ((i= m)||(j= n)) return 0; // lối đi if ((a[i][j]!=0)||(c[i][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<m ; ++i) for (j = 0 ; j<n ; ++j) c[i][j] = 0; 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[i][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[i][j]!=-1) { k=c[i][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]=i; S = 0; x[0] = m-1; y[0] = n-1; j = n-1; i = m-1 C[i][j] != -1 End K= c[i][j]; i = i – dx[k]; j = j – dy[k] S++ x[s] = i y[s] = j Begin y[s]=j; } } 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[i][j] != -1 End K= c[i][j]; i = i – dx[k]; j = j – dy[k] S++ x[s] = i y[s] = j 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,"Noresult"); if (d= =1) { /*for (i=0;i<m;++i) { for (j=0;j<n;++j) if (c[i][j]!=0) fprintf(f,"1 ");else fprintf(f,"0 "); fprintf(f,"\n"); }*/ fprintf(f,"%d\n",s); for (i=s;i>=0;i--) fprintf(f,"%4d%4d\n",x[i],y[i]); // for (i=s;i>=0;i--) fprintf(f,"%d\n",y[i]); } fclose(f); } 9- Void main Chương trình chính void main dùng để gọi các chương trình con thực hiện các công việc được đặc ta như sau: int main() { nhap(); xuly(); xuat(); return 0; } Begin nhap Xu ly Xuat End III. KẾT LUẬN – ĐÁNH GIÁ 1- Ưu điểm Giải thuật ngắn gọn, dễ hiểu. 2- Nhược điểm Chưa giải quyết được nhiều vấn đề: Cửa vào và cửa ra chưa được nhập tự do. Chưa xuất được kết quả của từng cửa đã đi qua. 3- Hướng phát triển Do thời gian thực hiện niên luận 1 là có hạn nên không đủ thời gian để thiết kế giải thuật được tối ưu hơn nên chương trình còn đơn giản. Trong tương lai, đề tài phát triển theo các hướng sau: Cửa vào và cửa ra được nhập tự do. Cho nhập mê cung trực tiếp trong khi chạy chương trình. Giao diện đồ họa đẹp hơn, gõ gàn và dễ nhìn hơn. Chương trình được hướng đến những trò chơi game mang tính trí tuệ. IV. PHỤ LỤC 1- Hướng dẫn chạy demo - Copy file inp.txt và file out.txt vào ổ đĩa f - Copy phần mềm lập trình C vào ổ đĩa C - Khi mở file demo lên trang giới thiệu sẽ được hiển thị: Ấn phím bất kỳ và kết quả được hiển thị như sau: Và cuối ấn phím bất kỳ chương trình sẽ kết thúc. 2- Tài liệu tham khảo - [1] Ngô Đức Lưu, Huỳnh Huy Tuấn. Bài giảng tin lập trình căn bản. Khoa Công nghệ thông tin – Trường Đại Học Bạc Liêu - [2] Nguyễn Xuân Huy. Lập trình song ngữ Pascal & C cho đồ họa máy tính. Nhà xuất bản khoa học và kỹ thuật. Hà Nội, năm 2000. - [3] Nguyễn Văn Linh, Lâm Hoài Bảo. Bài giảng lập trình căn bản. Khoa Công nghệ thông tin và Truyền thông – Trường Đại Học Cần Thơ, năm 2003. - [4] Hoàng Đức Hải, Huỳnh Tấn Dũng. Bài tập ngôn ngữ C từ A đến Z. Nhà xuất bản Lao động – Xã hội, năm 2005. - [5] Tuần tin Echip - [6] Học liệu mở Việt Nam - [7] Diễn đàn CLB Tin học Bách Khoa 3- Lời cảm ơn Trong thời gian làm niên luận em gặp không ít khó khăn khi chưa biết hướng giải quyết bài toán, trong khi thời gian xây dựng giải thuật hay khi viết chương trình . Nhưng được sự hướng dẫn của thầy Huỳnh Huy Tuấn nên em đã giải quyết được các vấn đề từ nhỏ đến lớn đến khi hoàn thành được yêu cầu của đề tài. Bên cạnh đó cùng với sự giúp đỡ của bạn bè nên học hỏi được nhiều kinh nghiệm. Cuối lời em xin chân thành cảm ơn thầy Huỳnh Huy Tuấn đã hướng dẫn em cùng với sự giúp đỡ của các thầy trong Khoa Công Nghệ Thông Tin trong thời gian em làm niên luận. Xin chân thành cảm ơn!