开发者社区> eddie小英俊> 正文

ACM:回溯,八皇后问题,素数环

简介:
+关注继续查看

(一)八皇后问题
(1)回溯

#include <iostream>
#include <string>

#define MAXN 100

using namespace std;

int tot = 0, n = 8;
int C[MAXN];

void search(int cur) {
	if(cur == n) ++tot;       //递归边界,仅仅要走到了这里。全部皇后必定不冲突
	else for(int i = 0; i < n; ++i) {
		int ok = 1;
		C[cur] = i;     //尝试把第cur行的皇后放在第i列
		for(int j = 0; j < cur; ++j) {     //检查是否和前面的皇后冲突
			if(C[cur] == C[j] || cur-C[cur] == j-C[j] || cur+C[cur] == j+C[j]) {
				ok = 0;
				break;
			}
		}
		if(ok)  search(cur+1);     //假设合法,则继续递归
	}
}

int main() {
	search(0);
	cout << tot << endl;
	return 0;
}



(2)利用二维数组优化的回溯法

#include <iostream>
#include <string>

#define MAXN 100

using namespace std;

int tot = 0, n = 8;
int vis[3][MAXN], C[MAXN];    

void search(int cur) {
	if(cur == n) ++tot;
	else for(int i = 0; i < n; ++i) {
		if(!vis[0][i] && !vis[1][cur+i] && !vis[2][cur-i+n]) {    //利用二维数组直接推断
			C[cur] = i;
			vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 1;   //改动全局变量
			search(cur+1);
			vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 0;   //这里一定要改回来!
		}
	}
}

int main() {
	memset(vis, 0, sizeof(vis));
	search(0);
	cout << tot << endl;
	return 0;
}

在上面的程序中,vis数组表示已经放置的皇后占领了哪些列、主对角线和副对角线。

一般的在回溯法中,假设改动了全局变量vis数组,那么递归调用结束后一定要改动回来!由于在解答树中,假设下一层不满足条件,那么就须要回溯。那么就要把改动过的vis给改回来,那样,才干继续进行下一次的推断!!!


(二)素数环

题目:输入正整数n,把整数1。2,3,...,n组成一个环。使得相邻两个整数之和均为素数。

输出时从整数1開始逆时针排列。

同一个环应该恰好输出一次。

典型的回溯法,代码例如以下:

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1000;
int isp[MAXN], vis[MAXN], A[MAXN], n;

int is_prime(int x) {    //推断一个数是否为素数
	for(int i = 2; i*i <= x; ++i) {
		if(x % i == 0) return 0;
	}
	return 1;
}

void dfs(int cur) {
	if(cur == n && isp[A[0] + A[n-1]]) {
		for(int i = 0; i < n; ++i) cout << A[i] << " ";
		cout << endl;
	}else {
		for(int i = 2; i <= n; ++i) {
			if(!vis[i] && isp[i + A[cur-1]]) {
				A[cur] = i;   //数字i满足条件,所以第cur个位置能够放数字i
				vis[i] = 1;
				dfs(cur+1);
				vis[i] = 0;   //跟上题一样。一定不能忘记把vis的值改回来,原因见上一题的代码凝视
			}
		}
	}
}

int main() {
	memset(vis, 0, sizeof(vis));   //递归调用之前,一定要把vis函数清0
	cin >> n;
	for(int i = 2; i <= 2*n; ++i) isp[i] = is_prime(i);   //推断一个数不是质数。为了方便后推断
	A[0] = 1;   //从标题中的规定的第一个数字1开始
	dfs(1);     //所以递归调用位置的1开始,而不是从位置0开始,因为数字第一位置已被确定是1
	return 0;
}




本文转自mfrbuaa博客园博客,原文链接:http://www.cnblogs.com/mfrbuaa/p/5037127.html,如需转载请自行联系原作者


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
给大一ACM队员的四个问题答复
(一位亲弟子的问题,我的回复在【】内)   今天实验室开了个小晚会送各位大三的学长。他们都讲了讲各自的想法。有讲大学生活怎么度过的,有讲未来工作的。让我有了很多想法。所以我也有了新的疑问。希望老师帮我解答一下吧…    【问题一】   我现在加入ACM实验室了,刚作为参观队参加了今年的省赛。恩,我的目标是省赛金牌,有点不可思议,但我觉着还是有希望的。所以我必然要拿出
1878 0
马的遍历问题-回溯法应用-ACM
马的遍历问题  在n*m的棋盘中,马只能走“日” 字。马从位置(x,y)处出发,把棋盘的每一格都走一次,且只走一次。找出所有路径。     问题解的搜索空间? 棋盘的规模是n*m,是指行有n条边,列有m条边。
1226 0
矩形嵌套问题-ACM集训
参考 http://blog.csdn.net/xujinsmile/article/details/7861412 有n个矩形,每个矩形可以用a,b来描述,表示长和宽。矩形X(a,b)可以嵌套在矩形Y(c,d)中当且仅当a
908 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
20369 0
阿里云服务器安全组设置内网互通的方法
虽然0.0.0.0/0使用非常方便,但是发现很多同学使用它来做内网互通,这是有安全风险的,实例有可能会在经典网络被内网IP访问到。下面介绍一下四种安全的内网互联设置方法。 购买前请先:领取阿里云幸运券,有很多优惠,可到下文中领取。
22267 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,大概有三种登录方式:
13288 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
28493 0
925
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载