题目内容
阅读下列C程序和程序说明,将应填入(n)处的字句写在对应栏内。
【说明】
本程序在3×3方格中填入1~N(N≥10)内的某9个互不相同的整数,使所有相邻两个方格内的两个整数之和为质数。试求出满足这个要求的所有填法。3×3方格中的每个方格按行按列(先行后列)序号排列为:0,1,2,3,4,5,6,7,8。
程序采用试探法,即从序号为0的方格开始,为当前方格寻找一个合理的可填整数,并在当前位置正确填入后,为下一方格寻找可填入的合理整数。如不能为当前方格找到一个合理的可填整数,就要回退到前一方格,调整前一方格的填入整数;直至序号为8的方格也填入合理的整数后,就找到了一个解,将该解输出。再调整序号为8的方格所填整数,继续去找下一个解。为了检查当前方格的填入整数的合理性,程序引入二维数组check Matrix,存放需要进行合理性检查的相邻方格的序号。
include <stdio. h>
define N 12
int b[N+1];
int pos;
int a[9];/* 用于存储诸方格所填入的整数*/
int AllNum=0;/* 统计有多少种填法*/
int checkMatrix[][3]={ {-1},{0,-1},{1,-1},
{0,-1},{1,3,-1},{2,4,-1},
{3,-1},{4,6,-1},{5,7,-1}};
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");
}
}
int isPrime(int m)
{ int i;
if(m==2)return 1;
if(m==1 ‖ m%2==0)return 0;
for(i=3; i*i<m;)
{ if(m%i==0)return 0;
i+=2;
}
return 1;
}
int selectNum(int start)
{ int j;
for(j=start; j<=N; j++)
if(b[j])return j;
return 0;
}
int check()/*检查填入pos位置的整数是否合理*/
{ int i,j;
for(i=0; (j=(1))>=0; i++)
if(!isPrime(a[pos]+a[j]))
(2);
(3);
}
extend ()/* 为下一方格找一个尚未使用过的整数*/
{ a[(4)]=selectNum(1);
b[a[pos]]=0;
}
void change ()/*为当前方格找下一个尚未使用过的整数(找不到回溯)*/
{ int j;
while(pos >=0 && (j=selectNum((5)))==0)
b[a[pos--]]=1;
if(pos<0)return;
b[a[pos]]=1; a[pos]=j; b[j]=0;
}
int find ()
{ int k=1;
pos=0; a[pos]=1; b[a[pos]]=0;
do{
if(ok)
if(pos==8)
{ write(a);
change();
AllNum++;/* 统计有多少种填法*/
}
else extend();
else change();
k=check();
}while(pos>=0);
}
void main()
{ int i;
for(i=1; i<=N; i++) b[i]=1;
find();
prinrf("共有%d种不同填法!/n", AllNum);
}
查看答案
搜索结果不匹配?点我反馈
更多问题