题解 搜索回溯（一）

搜索回溯，走尽迷宫

#include//1——20相邻数字和素数   
using namespace std;
int a[21]= {0},total=0;//数组a规定素数环，total表示素数环个数  
bool b[21]= {0};//数组b判定数字出现 

bool pd(int m,int n) {//判定素数函数  
	int k=2;
	while(k<=sqrt(m+n)&&(m+n)%k!=0) {//因数则停  
		k++;
	}
	if(k>sqrt(m+n)) {//无因数结果  
		return 1;
	} else {
		return 0;
	}
}

int print() {//输出函数 
	total++;
	printf("<%d>",total);
	for(int i=1; i<=20; i++) {
		printf("%d ",a[i]);
	}
	printf("n");
}

int search(int t) {//搜索函数，t为字符串中数字位置   
	for(int i=1; i<=20; i++) {//i表示数字可能性 
		if(pd(a[t-1],i)&&(!b[i])) {//符合素数和且没有出现过 
			a[t]=i;
			b[i]=1;//表示出现过  
			if(t==20) {//字符串结束 
				if(pd(a[20],a[1])) {//头尾相接 
					print();
				}
			} else {
				search(t+1);//继续搜索 
			}
			b[i]=0;//回溯 
		}
	}
}

int main() {
	search(1);//第一位开始 
	printf("%d",total);
}

#include//大整数拆分小整数 
using namespace std;

int n,a[10001]= {1},total;//a为拆分出的数字，total即拆分方案 

int print(int t) {//输出函数 
	printf("%d=%d",n,a[1]);
	for(int i=2; i<=t; i++) {
		printf("+%d",a[i]);
	}
	printf("n");
	total++;
}

int search(int s,int t) {//搜索函数，s为被拆分数，t为拆分起始数 
	for(int i=a[t-1]; i<=s; i++) {//保证大小顺序，搜索下一个拆分数 
		if(i 
 
//2.0版本，网状 
void dfs(int x,int y,int z) {//1，0，1开始 
	if(y>n) {//y为拆分数之和 
		return;
	}
	if(y==n) {//恰好拆分数和与被拆分数相等 
		for(int i=1; i1) {
				printf("+");
			}
			printf("%d",a[i]);
		}
		printf("n");
		return;//结束 
	}
	for(int i=x; i 
 
 

 
#include//从总数字中排序组合输出  
using namespace std； 

int m,n,t,a[10001]= {0};//a含目标字符串 

void dfs(int x,int y) {
	if(y>m) {//y为数字个数  
		t++;
		for(int i=1; i<=3; i++) {
			printf("%3d",a[i]);//空格 
		}
		printf("n");
		return;
	}
	for(int i=x; i<=n; i++) {//x为字符串起始数字 
		a[y]=i;
		dfs(i+1,y+1);//搜索，从i+1这个数开始，此时个数y+1个 
	}
}

int main() {
	scanf("%d%d",&n,&m);//n为总个数，m为所需个数 
	dfs(1,1);//从1开始，有1个数字 
	printf("%d",t); 
}
 
search大同小异
 

拔河函数，要求相对公平
 
void dfs(int x,int y,int z) {//从1，0，0开始，第一人，归另一队  
	if(y==n/2) {//n为人数，y为该队人数，z为总体重 
		res=min(res,abs(z*2-sum));//比大小，留更小 
		return;
	}
	if(x>n)return;//x为队员所在位置 
	dfs(x+1,y,z);//不计该名队员，计算下一队员 
	dfs(x+1,y+1,z+a[x]);//计该名队员与下一队员 
}
 
 

草率版本over
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5711942.html