一道关于数论的奥赛题,大家过来看看啊.
应用递归法解决有关数论的问题
在N*N的棋盘上（1 <=N <=10）填入1,2…N*N共N*N个数，使得任意两个相邻的数之和为素数。例如，N=2时有
12
43
其相邻的和为素数的有：1+2,1+4,4+3,2+3
当N=4时，一种可以填写的方案如下：
121112
1615 85
134914
67103
约定：左上角的格子里必须放数字1，程序要求：
输入：N
输出：若有多种解，则需输出第一行、第一列之和均为最小的排列方案；若无解，则输出“NO!”
欢迎大家给出自己的思路.
[解决办法]
这题目，我想了半天也没想出搜索之外的办法来。
用个回溯搜索可以把所有解搜索出来，但是数据量惊人。
要“输出第一行、第一列之和均为最小的排列方案”，看来还得在回溯条件上做改动。
/*
将1-N^2这N^2个数添如N*N的方格中，每个方格填一个整数，使所有相邻两个方格内的两个整数之和为质数。
例如N=3时如下，无解。N=4时，2992解？N=5时，917848解？算了半个小时
A0 A1 A2
A3 A4 A5
A6 A7 A8
PRIME(A0+A1)
PRIME(A0+A3)
PRIME(A1+A2)
PRIME(A1+A4)
PRIME(A2+A5)
PRIME(A3+A4)
PRIME(A3+A6)
PRIME(A4+A5)
PRIME(A4+A7)
PRIME(A5+A8)
PRIME(A6+A7)
PRIME(A7+A8)
*/
#include <stdio.h>
#include <math.h>
#include <windows.h>
#define MAX_NUM 30
#define _PRINT_ 0
unsigned long Result[MAX_NUM * MAX_NUM], ResultNum, Used[MAX_NUM * MAX_NUM]={0};
bool PrimeTable[MAX_NUM * MAX_NUM * 2]={ false };
unsigned long N, QN;
/* */
void CreatePrimeTable(void)
{
PrimeTable[0]=false;
PrimeTable[1]=false;
PrimeTable[2]=true;
PrimeTable[3]=true;
for(unsigned long j=5; j <= MAX_NUM * MAX_NUM * 2; j+=2)
{
PrimeTable[j]=true;
for(unsigned long i=3; i <= sqrt((double)j); i+=2)
{
if(j % i == 0)
{
PrimeTable[j]=false;
break;
}
}
}
}
/* */
inline bool IsPrime(unsigned long n)
{
return PrimeTable[n];
}
/* */
bool CheckIt(unsigned long Deep)
{
if(Deep == 0)
{
return true;
}
else if(Deep < N)
{
return IsPrime(Result[Deep] + Result[Deep - 1]);
}
else if(Deep % N == 0)
{
return IsPrime(Result[Deep] + Result[Deep - N]);
}
else
{
return(IsPrime(Result[Deep] + Result[Deep - 1]) && IsPrime(Result[Deep] + Result[Deep - N]));
}
}
/* */
void go(unsigned long Deep)
{
if(Deep == QN)
{
ResultNum++;
#if (_PRINT_)
printf( "Find it! No.%lu\n ", ResultNum);
for(unsigned long i=0; i < QN; i++)
{
printf( "%lu\t ", Result[i]);
if(i % N == N - 1)
{
printf( "\n ");
}
}
#else
printf( "\rFind:%lu ", ResultNum);
#endif
}
else
{
for(unsigned long i=1; i <= QN; ++i)
{
if(!Used[i])
{
Result[Deep]=i;
if(CheckIt(Deep))
{
Used[i]=1;
go(Deep + 1);
Used[i]=0;
}
}
}
}
}
/* */
int main(void)
{
DWORD tim;
ResultNum=0;
printf( "Input N: ");
scanf( "%lu ", &N);
QN=N * N;
tim=GetTickCount();
CreatePrimeTable();
go(0);
printf( "\n\nN=%lu\n ", N);
printf( "Total=%lu\n ", ResultNum);
printf( "Time=%lu\n ", GetTickCount() - tim);
return 0;
}
[解决办法]
我用java重建了NowCan的程序，结果一样。
NowCan,你的程序有个小问题啊，used数组大小是不是应该：MAX_NUM*MAX_NUM+1？否则这里会溢出：
for(unsigned long i=1; i <= QN; ++i)
{
if(!Used[i])
....
因为你其实不用used[0]的。我想是因为你用C编译器，我的JAVA就会报错了。8)
程序有点难读，也许deep从1开始计数会清楚些。
[解决办法]
这里有个该问题的代码(不是偶写的):
#include <stdio.h>
#include <memory.h>
int table[] =
{
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163,
167, 173, 179, 181, 191, 193, 197, 199
};
char isPrime[] =
{
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, 1, 0, 0, 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, 0, 1,
0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0,
1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0,
0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0,
0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0,
0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1
};
int find(int N, int* pos, int curr_pos)
{
int a, b, i, j, temp;
int curr_value = 1, start;
int stack[100], sp = 1;
stack[0] = 0;
start = 0;
while(1){
a = curr_pos / N; b = curr_pos % N;
for(i = start; i < 46; i++){
if(b == 0){
if(a == 0) temp = curr_value;
else temp = table[i] - pos[(a-1)*N];
}else if(a == 0){
temp = table[i] - pos[curr_pos-1];
}else{
temp = table[i] - pos[(a-1)*N+b];
if(temp + pos[curr_pos-1] > 200 ||
!isPrime[temp + pos[curr_pos-1]]) continue;
}
if(temp < 1) continue;
if(temp > N*N) break;
for(j = 0; j < curr_pos; j++)
if(temp == pos[j]) break;
if(j == curr_pos) break;
}
if(i != 46 && temp <= N*N){
pos[curr_pos++] = temp;
if(curr_pos == N*N) return 1;
stack[sp++] = i;
start = 0;
}else{
curr_pos--;
if(curr_pos < 0) return 0;
sp--;
start = stack[sp]+1;
}
}
}
int main(int argc, char* argv[])
{
int pos[10 * 10];
int N, count, i, j, k;
scanf( "%d ", &count);
for(k = 0; k < count; k++){
scanf( "%d ", &N);
if(find(N, pos, 0)){
for(i = 0; i < N; i++){
for(j = 0; j < N; j++){
if(j == 0) printf( "%d ", pos[i*N+j]);
else printf( " %d ", pos[i*N+j]);
}
putchar( '\n ');
}
}else puts( "NO ");
}
return 0;
}
