阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】
n-皇后问题是在n行n列的棋盘上放置n个皇后,使得皇后彼此之间不受攻击,其规则是任意两个皇后不在同一行、同一列和相同的对角线上。
拟采用以下思路解决n-皇后问题:第i个皇后放在第i行。从第一个皇后开始,对每个皇后,从其对应行(第i个皇后对应第i行)的第一列开始尝试放置,若可以放置,确定该位置,考虑下一个皇后;若与之前的皇后冲突,则考虑下一列;若超出最后一列,则重新确定上一个皇后的位置。重复该过程,直到找到所有的放置方案。
【C代码】
下面是算法的C语言实现。
(1)常量和变量说明
pos:一维数组,pos[i]表示第i个皇后放置在第i行的具体位置。
count:统计放置方案数。
i,j,k:变量。
N:皇后数。
(2)C程序
#include <stdio.h>
#include <math.h>
#define N4
//*判断第k个皇后目前放置位置是否与前面的皇后冲突
in isplace(int pos[],int k)
{
int i;
for(i=1; i<k; i++)
{
if( (1) || fabs(i-k) ══fabs(pos[i] - pos[k]))
{return();}}
return 1;
}
int main()
{
int i,j,count=1;
int pos[N+1];
//初始化位置
for(i=1;
i<=N; i++)
{
pos[i]=0;}(2) ;
while(j>=1) {pos[j]= pos[j]+1;
/*尝试摆放第1个皇后
/while(pos[j]<=N&&(3)_)
{
pos[j]= pos[j]+1;}/
得到一个摆放方案
/if(pos[j]<=N&&j══ N)
{
printf("方案%d: ",count++);
for(i=1; i<=N; i++)
{
printf("%d",pos[i]);
}
printf("\n");}/
考虑下一个皇后
/if(pos[j]<=N&&(4) )
{
j=j+1;
} else{ //返回考虑上一个皇后
pos[j]=0;(5) ;
}
}return 1;}。
【问题1】(10分)
根据以上说明和C代码,填充C代码中的空(1)~(5)。
【问题2】(2分)
根据以上说明和C代码,算法采用了(6)设计策略。
【问题3】(3分)
上述C代码的输出为:(7)。
【问题1】
(1)pos[i] ==pos[k]
(2)j=1
(3)isplace(pos,j)==0
(4)j<N
(5)j=j-1
【问题2】
答案:回溯法
【问题3】
答案:
方案1:2 4 1 3
方案2:3 1 4 2