[ACM实验四]ACM程序设计基础(2)
杰拉斯 | 时间:2012-04-12, Thu | 20,330 views编程算法
实验项目:ACM程序设计基础(2)
实验目的:掌握C++程序设计基础。
实验要求:使用VC++6.0实现实验要求。
实验内容:
1.上地理课时,四个学生回答我国四大淡水湖的大小时说:
- 甲:洞庭湖最大,洪泽湖最小,鄱阳湖第三。{1, 4, 3, 2}
- 乙:洪泽湖最大,洞庭湖最小,鄱阳湖第二,太湖第三。{2, 3, 4, 1}
- 丙:鄱阳湖最小,洞庭湖第三。{0, 0, 1, 3}
- 丁:鄱阳湖最大,太湖最小,洪泽湖第二,洞庭湖第三。{3, 2, 1, 4}
对于每个湖的大小,每人仅答对了一个。请判断四个湖的大小。请用递归算法编写程序实现。
2.以一个m*n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论,如果有通道,请输出最短路径的通道。例如:
9 8 1 1 9 8 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0
1.判断湖的大小
为每个湖编号(1.洞庭 2.洪泽 3.潘阳 4.太湖),则每位同学所说的顺序都可作为一个4位的数组,如上粗体所示。只要找出所有情况中每位同学都只对一个的情况,即是本题的解。代码如下:
#include<stdio.h> #include<iostream> using namespace std; //编号:1洞庭 2洪泽 3潘阳 4太湖 int ans[4][4] = {1, 4, 3, 2, 2, 3, 4, 1, 0, 0, 1, 3, 3, 2, 1, 4}; //四位学生的说法 void BackTrake(int n, int m, int a[]){ int i; if(m == n - 1){ for(i = 0; i < 4; ++i){ //循环判断四位学生的说法 int num = 0; for(int j = 0; j < n; ++j){ //所有湖中 if(ans[i][j] == a[j]){ //如果有一个正确 ++num; //则正确数加1 } } if(num > 1 || num == 0) //若正确数为0或大于1 return; //则不输出 } printf("%d%d%d%d\n", a[0], a[1], a[2], a[3]); //输出 return; } for(i = m; i < n; ++i){ //全排列 swap(a[m], a[i]); BackTrake(n, m + 1, a); swap(a[m], a[i]); } } int main(){ int a[4] = {1, 2, 3, 4}; BackTrake(4, 0, a); return 0; }
剪枝,最简单的就是把判断部分加到下层递归前面即可:
#include<stdio.h> #include<iostream> using namespace std; //编号:1洞庭 2洪泽 3潘阳 4太湖 int ans[4][4] = {1, 4, 3, 2, 2, 3, 4, 1, 0, 0, 1, 3, 3, 2, 1, 4}; //四位学生的说法 void BackTrake(int n, int m, int a[]){ int i; if(m == n - 1){ for(i = 0; i < 4; ++i){ //循环判断四位学生的说法 int num = 0; for(int j = 0; j < n; ++j){ //所有湖中 if(ans[i][j] == a[j]){ //如果有一个正确 ++num; //则正确数加1 } } if(num > 1 || num == 0) //若正确数为0或大于1 return; //则不输出 } printf("%d%d%d%d\n", a[0], a[1], a[2], a[3]); //输出 return; } for(i = m; i < n; ++i){ //全排列 swap(a[m], a[i]); int flag = 1; for(int j = 0; j < 4 && flag; ++j){ //循环判断四位学生的说法 int num = 0; for(int k = 0; k < m; ++k){ if(ans[j][k] == a[k]){ //如果有一个正确 ++num; //则正确数加1 } } if(num > 1){ //若正确数大于1 flag = 0; //则不继续搜索 break; } } if(flag) BackTrake(n, m + 1, a); swap(a[m], a[i]); } } int main(){ int a[4] = {1, 2, 3, 4}; BackTrake(4, 0, a); return 0; }
2.迷宫
#include<stdio.h> #include<queue> using namespace std; struct pos{ int row; //行 int col; //列 int step; //到达该点的步数 pos(int row = 0, int col = 0, int step = 0):row(row),col(col),step(step){}; }; int main(){ int a[102][102]; int offset[4][2] = {-1, 0, 0, 1, 1, 0, 0, -1}; //四个方向 int m, n, i, j, k, row, col, flag = 0; pos start; pos end; scanf("%d%d", &m, &n); scanf("%d%d", &end.row, &end.col); //从终点往起点找,倒序输出即是起点到终点的路径 scanf("%d%d", &start.row, &start.col); for(i = 1; i <= m; ++i){ for(j = 1; j <= n; ++j){ scanf("%d", &a[i][j]); } } for(i = 0; i <= m+1; ++i){ //下面两个循环为迷宫加外墙 a[i][0] = 1; a[i][n + 1] = 1; } for(i = 1; i <= n; ++i){ a[0][i] = 1; a[m + 1][i] = 1; } queue<pos> q; q.push(start); a[start.row][start.col] = -1; //printf("%d %d\n", end.row, end.col); while(!q.empty()){ //当队列不为空时,不断寻找四周可以走的点,并放入队列中 pos front = q.front(); //printf("%d %d\n", front.row, front.col); q.pop(); for(i = 0; i < 4; ++i){ //向四个方向遍历 row = front.row + offset[i][0]; col = front.col + offset[i][1]; if(a[row][col] != 0) //该点为墙或已走过 continue; a[row][col] = front.row * (n + 2) + front.col; //保存上一点位置,因为加了墙,所以加2 if(row == end.row && col == end.col){ //若达到终点 end.step = front.step + 1; k = a[row][col]; //保存终点来源位置 flag = 1; //标记已找到路径 break; } pos nbr(row, col, front.step + 1); //printf("%d %d %d %d %d\n", front.row, front.col, row, col, front.step + 1); q.push(nbr); } if(flag){ //若已找到路径 printf("(%d, %d)", end.row, end.col); //输出终点 while(k > 0){ row = k / (n + 2); //找到上一位置的坐标 col = k % (n + 2); k = a[row][col]; printf("→(%d, %d)", row, col); //输出该点 } printf("\n%d steps.\n", end.step); //输出总步数 break; } } if(!flag) printf("Not Found!\n"); return 0; for(i = 0; i <= m + 1; ++i){ for(j = 0; j <= n + 1; ++j){ printf("%2d ", a[i][j]); } printf("\n"); } return 0; }
实现图案输出:
#include<stdio.h> #include<queue> #include<string> using namespace std; struct pos{ int row; //行 int col; //列 int step; //到达该点的步数 pos(int row = 0, int col = 0, int step = 0):row(row),col(col),step(step){}; }; int main(){ int a[102][102]; string s[102][102]; int offset[4][2] = {-1, 0, 0, 1, 1, 0, 0, -1}; //四个方向 int m, n, i, j, k, row, col, flag = 0; pos start; pos end; scanf("%d%d", &m, &n); scanf("%d%d", &end.row, &end.col); //从终点往起点找,倒序输出即是起点到终点的路径 scanf("%d%d", &start.row, &start.col); for(i = 1; i <= m; ++i){ for(j = 1; j <= n; ++j){ scanf("%d", &a[i][j]); s[i][j] = a[i][j] == 0?" ":"■"; } } for(i = 0; i <= m+1; ++i){ //下面两个循环为迷宫加外墙 a[i][0] = 1; a[i][n + 1] = 1; s[i][0] = "■"; s[i][n + 1] = "■"; } for(i = 1; i <= n; ++i){ a[0][i] = 1; a[m + 1][i] = 1; s[0][i] = "■"; s[m + 1][i] = "■"; } queue<pos> q; q.push(start); a[start.row][start.col] = -1; //printf("%d %d\n", end.row, end.col); while(!q.empty()){ //当队列不为空时,不断寻找四周可以走的点,并放入队列中 pos front = q.front(); //printf("%d %d\n", front.row, front.col); q.pop(); for(i = 0; i < 4; ++i){ //向四个方向遍历 row = front.row + offset[i][0]; col = front.col + offset[i][1]; if(a[row][col] != 0) //该点为墙或已走过 continue; a[row][col] = front.row * (n + 2) + front.col; //保存上一点位置 if(row == end.row && col == end.col){ //若达到终点 end.step = front.step + 1; k = a[row][col]; //保存终点来源位置 flag = 1; //标记已找到路径 break; } pos nbr(row, col, front.step + 1); //printf("%d %d %d %d %d\n", front.row, front.col, row, col, front.step + 1); q.push(nbr); } if(flag){ //若已找到路径 printf("(%d, %d)", end.row, end.col); //输出终点 while(k > 0){ row = k / (n + 2); //找到上一位置的坐标 col = k % (n + 2); if(k > a[row][col]){ s[row][col] = k - a[row][col] == 1?"←":"↑"; }else{ s[row][col] = a[row][col] - k == 1?"→":"↓"; } k = a[row][col]; printf("→(%d, %d)", row, col); //输出该点 } printf("\n"); s[start.row][start.col] = "★"; s[end.row][end.col] = "☆"; for(i = 0; i <= m + 1; ++i){ for(j = 0; j <= n + 1; ++j){ printf("%s", s[i][j].c_str()); } printf("\n"); } printf("%d steps.\n", end.step); //输出总步数 break; } } if(!flag) printf("Not Found!\n"); return 0; }
如需转载请注明出处:杰拉斯的博客
第一题要最优,不完全递归完。怎么做,请指教 [奋斗]
这两天没空,看到了一直没回你= =。。
代码写出来了,在上面的剪枝部分。