Posted on 2006-09-13 23:13
chenger 阅读(968)
评论(0) 编辑 收藏 引用 所属分类:
Programming Stuff
问题是这样的：3*3的方格，填入1-10（比10更大也可以），要求相邻两数之和为素数。
这个题目除了回溯似乎没有别的方法了。一开始还想遍历所有可能的排列，然后一个一个检查。把排列的算法写出来之后就是一个递归算法（不是效率最高的，应该说是效率最差的），但有个好处，可以在里头插入检查是否满足问题约束的代码，这样就减少了搜索的数量，也就是剪枝。希望有算法大牛来看看我这个解法对不对，心里还有些没底。
#include <cstdio>
#include <algorithm>
using std::printf;
const int N = 3;
const int Max = N*N + 1;
const int MaxSum = 2*Max - 1;
bool used[Max];
int square[N][N];
bool prime[MaxSum];
void GetAllPrimes()
{
std::fill(prime,prime + MaxSum,true);
prime[0] = prime[1] = false;
for(int i = 2;i < MaxSum;++i)
if(prime[i])
for(int j = i*i;j < MaxSum;j += i)
prime[j] = false;
}
void Print()
{
for(int i = 0;i < N;++i)
{
for(int j = 0;j < N;++j)
printf("%d\t",square[i][j]);
printf("\n");
}
}
void Search(int line,int col)
{
if(line == N)
{
Print();
printf("\n");
return;
}
if(col == N)
{
Search(line + 1,0);
return;
}
for(int n = 0;n < Max;++n)
{
if(!used[n])
{
if((col > 0 && !prime[n + 1 + square[line][col - 1]])
||
(line > 0 && !prime[n + 1 + square[line - 1][col]]))
continue;
square[line][col] = n + 1;
used[n] = true;
Search(line,col + 1);
used[n] = false;
square[line][col] = 0;
}
}
}
int main()
{
GetAllPrimes();
Search(0,0);
return 0;
}