这道题很简单,就是n个数排成一圈,相邻两个数加起来必须是质数。第一个一定是1。直接深度搜索。
因为n<20,所以加起来的最大的质数为37。可以直接用一个大小为40或41的(这个由自己决定)bool数组标记就行了。不用再去写个循环判断是否是质数。
另外还需要一个大小为20的数组标记其中的数是否已经被使用过。
AC代码如下:
-
#include <iostream>
-
using namespace std;
-
bool isPrime[41] = {false,
-
false, true, true, false, true, false, true, false, false, false,
-
true, false, true, false, false, false, true, false, true, false,
-
false, false, true, false, false, false, false, false, true, false,
-
true, false, false, false, false, false, true, false, false, false}; //0、1和质数为false。
-
-
bool isUsed[20] = {true, true, false, false, false, false, false, false, false, false,
-
false, false, false, false, false, false, false, false, false, false}; //0和1都标记为用过
-
-
int N, answer[20] = {0, 1};
-
-
void showAnswer(void)
-
{
-
for(int i = 1; i < N; ++i)
-
cout << answer[i] << " ";
-
cout << answer[N] << endl;
-
}
-
-
void dfs(int depth)
-
{
-
if(isPrime[answer[N] + 1] && depth == N + 1)
-
{
-
showAnswer();
-
return;
-
}
-
for(int i = 2; i <= N; ++i)
-
{
-
if(isUsed[i] || !isPrime[answer[depth - 1] + i])
-
continue;
-
isUsed[i] = true; //标记为用过
-
answer[depth] = i;
-
dfs(depth + 1);
-
isUsed[i] = false; //取消标记
-
}
-
}
-
-
int main()
-
{
-
int ct = 1;
-
while(cin >> N)
-
{
-
cout << "Case " << ct++ << ":\n";
-
dfs(2); //第一个肯定是1,直接从2开始
-
cout << endl;
-
}
-
return 0;
-
}
阅读(624) | 评论(0) | 转发(0) |