Posted on 2006-09-13 23:13
chenger 閱讀(985)
評論(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;
}