main()
{ comb(5,3);
}
【问题】 填字游戏
问题描述：在3×3个方格的方阵中要填入数字1到N（N≥10）内的某9个数字，每个方格填一个整数，似的所有相邻两个方格内的两个整数之和为质数。试求出所有满足这个要求的各种数字填法。
可用试探发找到问题的解，即从第一个方格开始，为当前方格寻找一个合理的整数填入，并在当前位置正确填入后，为下一方格寻找可填入的合理整数。如不能为当前方格找到一个合理的可填证书，就要回退到前一方格，调整前一方格的填入数。当第九个方格也填入合理的整数后，就找到了一个解，将该解输出，并调整第九个的填入的整数，寻找下一个解。
为找到一个满足要求的9个数的填法，从还未填一个数开始，按某种顺序（如从小到大的顺序）每次在当前位置填入一个整数，然后检查当前填入的整数是否能满足要求。在满足要求的情况下，继续用同样的方法为下一方格填入整数。如果最近填入的整数不能满足要求，就改变填入的整数。如对当前方格试尽所有可能的整数，都不能满足要求，就得回退到前一方格，并调整前一方格填入的整数。如此重复执行扩展、检查或调整、检查，直到找到一个满足问题要求的解，将解输出。
回溯法找一个解的算法：
{ int m=0,ok=1;
int n=8;
do{
if (ok) 扩展;
else 调整;
ok=检查前m个整数填放的合理性;
} while ((!ok||m!=n)&&(m!=0))
if (m!=0) 输出解;
else 输出无解报告；
}
如果程序要找全部解，则在将找到的解输出后，应继续调整最后位置上填放的整数，试图去找下一个解。相应的算法如下：
回溯法找全部解的算法：
{ int m=0,ok=1;
int n=8;
do{
if (ok)
{ if (m==n)
{ 输出解；
调整；
}
else 扩展;
}
else 调整;
ok=检查前m个整数填放的合理性;
} while (m!=0);
}
为了确保程序能够终止，调整时必须保证曾被放弃过的填数序列不会再次实验，即要求按某种有许模型生成填数序列。给解的候选者设定一个被检验的顺序，按这个顺序逐一形成候选者并检验。从小到大或从大到小，都是可以采用的方法。如扩展时，先在新位置填入整数1，调整时，找当前候选解中下一个还未被使用过的整数。将上述扩展、调整、检验都编写成程序，细节见以下找全部解的程序。
【程序】
# 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,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[j])
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=0,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();
}
【问题】 n皇后问题
问题描述：求出在一个n×n的棋盘上，放置n个不能互相捕捉的国际象棋“皇后”的所有布局。
这是来源于国际象棋的一个问题。皇后可以沿着纵横和两条斜线4个方向相互捕捉。如图所示，一个皇后放在棋盘的第4行第3列位置上，则棋盘上凡打“×”的位置上的皇后就能与这个皇后相互捕捉。

1 2 3 4 5 6 7 8
× ×
× × ×
× × ×
× × Q × × × × ×
× × ×
× × ×
× ×
× ×
从图中可以得到以下启示：一个合适的解应是在每列、每行上只有一个皇后，且一条斜线上也只有一个皇后。
求解过程从空配置开始。在第1列至第m列为合理配置的基础上，再配置第m+1列，直至第n列配置也是合理时，就找到了一个解。接着改变第n列配置，希望获得下一个解。另外，在任一列上，可能有n种配置。开始时配置在第1行，以后改变时，顺次选择第2行、第3行、…、直到第n行。当第n行配置也找不到一个合理的配置时，就要回溯，去改变前一列的配置。得到求解皇后问题的算法如下：
{ 输入棋盘大小值n；
m=0;
good=1;
do {
if (good)
if (m==n)
{ 输出解；
改变之，形成下一个候选解;
}
else 扩展当前候选接至下一列；
else 改变之，形成下一个候选解；
good=检查当前候选解的合理性；
} while (m!=0);
}
在编写程序之前，先确定边式棋盘的数据结构。比较直观的方法是采用一个二维数组，但仔细观察就会发现，这种表示方法给调整候选解及检查其合理性带来困难。更好的方法乃是尽可能直接表示那些常用的信息。对于本题来说，“常用信息”并不是皇后的具体位置，而是“一个皇后是否已经在某行和某条斜线合理地安置好了”。因在某一列上恰好放一个皇后，引入一个一维数组（col[ ]），值col[i]表示在棋盘第i列、col[i]行有一个皇后。例如：col[3]=4，就表示在棋盘的第3列、第4行上有一个皇后。另外，为了使程序在找完了全部解后回溯到最初位置，设定col[0]的初值为0当回溯到第0列时，说明程序已求得全部解，结束程序运行。
为使程序在检查皇后配置的合理性方面简易方便，引入以下三个工作数组：
（1） 数组a[ ]，a[k]表示第k行上还没有皇后；
（2） 数组b[ ]，b[k]表示第k列右高左低斜线上没有皇后；
（3） 数组 c[ ]，c[k]表示第k列左高右低斜线上没有皇后；
棋盘中同一右高左低斜线

此新闻共有11页 上一页 1 2 3 4 5 6 7 8 9 10 11 下一页