[ACM实验四]ACM程序设计基础(2)

蓝飞 蓝飞 | 时间:2012-04-12, Thu | 11,871 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;
}
如需转载请注明出处:蓝飞技术部落格

2 条评论 »

  1. yue yue

    第一题要最优,不完全递归完。怎么做,请指教 [奋斗]

    1. 这两天没空,看到了一直没回你= =。。
      代码写出来了,在上面的剪枝部分。