最近遇到的一道笔试题

Question

在3×3个方格的方阵中要填入数字1到N（N≥10）内的某9个数字，每个方格填一个整数，使的所有相邻两个方格内的两个整数之和为质数。试求出所有满足这个要求的各种数字填法。

Answer 1

#include<stdio.h>
#define N 12void write(int a[])
{
        int i,j;
       for(i=0;i<3;i++){
            for(j=0;j<3;j++)
     printf("%3d",a[3*i+j]);
printf("\n");
}
scanf("% * c");
}int b[N+1];
int a[10];
int isPrime(int m)
{
int i;
int primes[]={2,3,5,7,11,13,17,19,23,29,-1};if(m==1||m%2==0) return 0;
for(i=0;primes[i]>0;i++)
if(m==primes[i]) return 1;for(i=3;i*i<=m;){
if(m%i==0) return 0;
i+=2;
}
return 1;
}int checkMatrix[][3]={
{-1},{0,-1},{1,-1},
{0,-1},{1,3,-1},{2,4,-1},
{3,-1},{4,6,-1},
{5,7,-1}};int selectNum(int start)
{
int j;
for(j=start;j<=N;j++)
if(b[j]) return j;
return 0;
}int check(int pos)
{
int i,j;
if(pos<0) return 0;
for(i=0;(j=checkMatrix[pos][i])>=0;i++)
if(!isPrime(a[pos]+a[i])) return 0;
return 1;
}int extend(int pos)
{
a[++pos]=selectNum(1);
b[a[pos]]=0;
return pos;
}int change(int pos)
{
int j;while(pos>=0 && (j=selectNum(a[pos]+1))==0)
b[a[pos--]]=1;
if(pos<0) return -1;b[a[pos]]=1;
a[pos]=j;
b[j]=0;return pos;
}void find()
{
int ok=1,pos=0;
a[pos]=1;
b[a[pos]]=0;
do
{
if(ok)
if(pos==8){
write(a);
pos=change(pos);
}else pos=extend(pos);
else pos=change(pos);
ok=check(pos);
}while(pos>=0);
}void main(){int i;
for(i=1;i<=N;i++)
b[i]=1;
find();} 收起
布的天才白痴 | 浏览 734 次 |举报
我有更好的答案
1条回答
/*
在9（3*3）个方格的方阵中填入数字1到N(N>=10)内的某9个数字每个方格填一个整数，
要求相邻两个方格的两个整数之和为质数。 试求所有的解
*/
#include<stdio.h>
#define N 12
void write(int a[])
{int i,j;
for(i=0;i<3;i++){
for(j=0;j<3;j++)
printf("%3d",a[3*i+j]);
printf("\n");
}
scanf("% * c");
}
int b[N+1];
int a[10];
int isPrime(int m)
{
int i;
int primes[]={2,3,5,7,11,13,17,19,23,29,-1};
if(m==1||m%2==0) return 0;
for(i=0;primes[i]>0;i++)
if(m==primes[i]) return 1;
for(i=3;i*i<=m;){
if(m%i==0) return 0;
i+=2;
}
return 1;
}
int checkMatrix[][3]={
{-1},{0,-1},{1,-1},
{0,-1},{1,3,-1},{2,4,-1},
{3,-1},{4,6,-1},
{5,7,-1}};
int selectNum(int start)
{
int j;
for(j=start;j<=N;j++)
if(b[j]) return j;
return 0;
}
int check(int pos)
{
int i,j;
if(pos<0) return 0;
for(i=0;(j=checkMatrix[pos][i])>=0;i++)
if(!isPrime(a[pos]+a[i])) return 0;
return 1;
}
int extend(int pos)
{
a[++pos]=selectNum(1);
b[a[pos]]=0;
return pos;
}
int change(int pos)
{
int j;
while(pos>=0 && (j=selectNum(a[pos]+1))==0)
b[a[pos--]]=1;
if(pos<0) return -1;
b[a[pos]]=1;
a[pos]=j;
b[j]=0;
return pos;
}
void find()
{
int ok=1,pos=0;
a[pos]=1;
b[a[pos]]=0;
do
{
if(ok)
if(pos==8){
write(a);
pos=change(pos);
}
else pos=extend(pos);
else pos=change(pos);
ok=check(pos);
}while(pos>=0);
}
void main(){
int i;
for(i=1;i<=N;i++)
b[i]=1;
find();
}

Answer 2

我是学JAVA的，谁能用JAVA语言写一下