主要内容 #
- 问题描述
- 计算方法
- 参考代码
1. 问题描述 #
把整数{1,2,3,…,20}填到一个环中,要求每个整数只填写一次,并且相邻的两个整数之和是一个素数。例如,下图所示就是{1,2,3,4}对应的一个素数环。
2. 计算方法 #
算法分析
非常明显,只是一道回溯题目。从1开始,每个空位有20种可能,只要填进去的数合法;与之前的数不同;与左边相邻的数是一个素数;第20个数还要判断和第一个数的和是否是素数。
在填写第k个位置时,如果满足上述约束条件,则继续填写第k+1个位置;如果1~20都无法填写到第k个位置,则取消第k个位置的填写,回溯到第k-1个位置。
以四个数字的素数环为例,使用回溯法的解答树解答如下图所示:
算法流程
输入:要填写到环中的整数个数n输出:素数环的元素a【n】 1.将存储素数环的数组a】中所以元素初始化为0 2.将a【0】初始化为1,k初始化为1 3.while(k>=1) 3.1a[k]=a[k]+1 3.2 while(a[k]<=n) 3.2.1如果a[k]满足约束条件,结束循环 3.2.2如果a[k]不满足约束条件,a[k]=a[k]+1 3.3如果a[k]=n,且k=n-1,输出素数环,结束程序 3.4如果a[k]<=n,且k<n-1,k=k+1 3.5否则,a[k]=0,k=k-1,即回溯。
3. 参考代码 #
#include < iostream > #include < math.h > using namespace std; bool isPrime(int x) //判断整数x是否是素数 { int n = (int)sqrt(x); for(int i=2; i < =n; i++) if(x%i == 0) return false; return true; } bool isLegal(int k, int n, int a[]) //判断位置k填写是否满足约束条件 { for(int i=0; i < k; i++) //判断即将填写的值是否与填写过的重复 if(a[i] == a[k]) return false; if(!isPrime(a[k]+a[k-1])) return false; //判断相邻数之和是否为素数 if(k==n-1 && !isPrime(a[k]+a[0])) return false; //判断第一个和最后一个之和是否为素数 return true; } void primeCircle(int n) { int a[n]; //用数组a[]来存储素数环 for(int i=0; i < n; i++) //将数组所有元素都初始化为0 a[i] = 0; a[0] = 1; int k = 1; while(k > =1) { a[k] = a[k]+1; while(a[k] < =n) { if(isLegal(k,n,a)) break; //位置k可以填写整数a[k] else a[k] = a[k]+1; //试探下一个数 } if(a[k] < =n && k==n-1) //求解完毕,输出素数环 { for(int i=0; i < n; i++) cout << a[i] << " "; cout << endl; return; } if(a[k]<=n && k<n-1) k++; //填写下一个 else a[k--] = 0; //回溯 } } int main() { primeCircle(4); return 0; }