素数环问题
把从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。请问如何用回溯法排列树搜索的思想编写这个题目的具体算法？
用回溯法搜索排列树的算法框架可描述如下：
void backtrack(int t)
{
if(t>n)
output(x)
else
for(int i=t;i<=n;i++)
{
swap(x[t],x[i]);
if(constraint(t)&&bound(t)) backtrack(t+1);
swap(x[t],x[i]);
}
}
用回溯法搜索子集树，本人已经会了，具体算法如下：
main()
{ int a[20],k;
for(k=1;k<=20;k++)
a[k]=0;
a[1]=1;
try(2);
}
try(int i)
{
int k
for(k=2;k<=20;k++)
if(check1(k,i)==1 and check3(k,i)==1)//判断与前面的数不相同、与前面相邻的数据的和是一个素数；两个函数不打了
{
a[i]=k;
if(i=20)
output();//输出符合要求的素数环
else
{
try(i+1);
a[i]=0;
}
}
[解决办法]
UP
[解决办法]
学习！
[解决办法]
所谓的环，无非增加一个1＋20是不是素数的判断而已
其他相邻两个数，挨个求和并判断素数而已
最大19＋20＝39，最小3，总共也就20组数
[解决办法]
这个题感觉不用那么麻烦吧
解个方程就可以出来吧
设n个数一圈，而且设这n个数依次为a1,a2,...,an
相邻两个的和为质数，一共有n个，不妨设这n个素数分别为x1,x2,...,xn
那么依据题意，应该满足
a1 + a2 = x1
a2 + a3 = x2
:
:
an + a1 = xn
把这个方程变形为
RA=X，其中A=[a1,a2,...,an]T，X=[x1,x2,...,xn]T
R为系数矩阵，从上面的方程可以直接写出来（这里不好排版，我就不写了）
然后可得A=(R^-1)X
其中R已知，R^-1（R的逆矩阵）也容易求出来，只要找n个素数，构造一个X就行了，
这样就可以得到一个A
[解决办法]
直接写了个递归的算法，不知对不对，好像有无数个组合
#include <cmath>
#include<iostream>
using namespace std;
#define COUNT 20
int data[2*COUNT];
int num[COUNT + 1];
int Count = 0;
void InitPrimeNum()
{
int i, j;
memset(data, 0, 2*COUNT);
int iUpLimit = (int)sqrt(2.0*COUNT);
for(i = 2; i <= iUpLimit; i++)
if(!data[i])
for(j = i * 2; j <= 2*COUNT; j += i)
data[j] = 1;
}
bool inline IsPrimeNum(int iNum)
{
if (data[iNum] == 0)
{
return true;
}
else
{
return false;
}
}
bool inline IsDiffren(int iCurOrder, int iCurNum)
{
for(int i = 1; i < iCurOrder; i++ )
if (num[i] == iCurNum)
{
return false;
}
return true;
}
void Print()
{
for(int i = 1; i <= COUNT; i++)
cout<<num[i]<<" ";
cout<<endl;
}
void SumOfBorderUponIsPrimeNum(int iCurOrder)
{
if (iCurOrder == COUNT + 1)
{
if(IsPrimeNum(num[COUNT] + num[1]))
{
Print();
Count++;
}
return;
}
for(int i = 1; i <= COUNT; i++)
{
num[iCurOrder] = i;
if (iCurOrder == 1)
{
SumOfBorderUponIsPrimeNum(iCurOrder + 1);
}
else if(IsDiffren(iCurOrder, i) && IsPrimeNum(i + num[iCurOrder - 1]))
{
SumOfBorderUponIsPrimeNum(iCurOrder + 1);
}
}
}
void InitNum()
{
memset(num, 0 , COUNT + 1);
}
void main()
{
InitPrimeNum();
InitNum();
SumOfBorderUponIsPrimeNum(1);
cout<<Count<<endl;
getchar();
}
------解决方案--------------------
- C/C++ code
#include <iostream>#include <iterator>#include <windows.h>using namespace std;int Prime[]={0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1, 0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0};void PrimeRing( int n ){ int *a=new int[n+1], *l=new int[n+1], *u=new int[n+1]; int k, p, q; for( k=0; k<n; ++k ) l[k]=k+1; l[n]=0; k=1;X2: p=0; q=l[0];X3: a[k]=q; if( a[1]>1 ) goto X7; if( !( k==1 || Prime[a[k-1]+a[k]] ) ) goto X5; else if( k==n && Prime[a[1]+a[n]] ){ copy( a+1, a+n+1, ostream_iterator<int>(cout," ") ),cout<<endl; goto X6; } u[k]=p; l[p]=l[q]; ++k; goto X2;X5: p=q; q=l[p]; if( q!=0 ) goto X3;X6: --k; if( k==0 ) return; p=u[k], q=a[k], l[p]=q; goto X5;X7: delete []a; delete []u; delete []l;}int main( ){ PrimeRing( 20 ); system("PAUSE"); return EXIT_SUCCESS;}
[解决办法]
总共有6309300个解。
如果全部打印输出的话，要很久。
[解决办法]
没看出什么大问题。
1. 你的check3(int i)的时候：
- C/C++ code
if(i <20)return(check2(a[i]+a[i-1]));