|
|
在程序设计中，有很多经典问题，如迷宫问题、八皇后问题、背包问题、汉诺塔等等，这些问题不但很有趣，而且也为很多大型项目提供解决方案。
我先开个头：
八皇后问题：
[code:1]〖问题描述〗
在一个８×８的棋盘里放置８个皇后，要求每个皇后两两之间不相"冲"（在每一横列竖列斜列只有一个皇后）。
〖问题分析〗(聿怀中学 吕思博)
这道题可以用递归循环来做，分别一一测试每一种摆法，直到得出正确的答案。主要解决以下几个问题：
1、冲突。包括行、列、两条对角线：
（1）列：规定每一列放一个皇后，不会造成列上的冲突；
（2）行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态；
（3）对角线：对角线有两个方向。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。因此，当第I个皇后占领了第J列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。
2、数据结构。
（1）解数组A。A[I]表示第I个皇后放置的列；范围：1..8
（2）行冲突标记数组B。B[I]=0表示第I行空闲；B[I]=1表示第I行被占领；范围：1..8
（3）对角线冲突标记数组C、D。
C[I-J]=0表示第（I-J）条对角线空闲；C[I-J]=1表示第（I-J）条对角线被占领；范围：-7..7
D[I+J]=0表示第（I+J）条对角线空闲；D[I+J]=1表示第（I+J）条对角线被占领；范围：2..16
〖算法流程〗
１、数据初始化。
２、从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当前位置(n,m)是否等于０（未被占领）:
如果是，摆放第n个皇后，并宣布占领(记得要横列竖列斜列一起来哦)，接着进行递归；
如果不是，测试下一个位置(n,m+1)，但是如果当n<=8,m=8时，却发现此时已经无法摆放时，便要进行回溯。
３、当n>8时，便一一打印出结果。
〖优点〗逐一测试标准答案，不会有漏网之鱼。
Pascal实现：
program tt;
var a:array [1..8] of integer;
b,c,d:array [-7..16] of integer;
t,i,j,k:integer;
procedure print;
begin
t:=t+1;
write(t,' ');
for k:=1 to 8 do write(a[k],' ');
writeln;
end;
procedure try(i:integer);
var j:integer;
begin
for j:=1 to 8 do {每个皇后都有8种可能位置}
if (b[j]=0) and (c[i+j]=0) and (d[i-j]=0) then {判断位置是否冲突}
begin
a[i]:=j; {摆放皇后}
b[j]:=1; {宣布占领第J行}
c[i+j]:=1; {占领两个对角线}
d[i-j]:=1;
if i<8 then try(i+1) {8个皇后没有摆完，递归摆放下一皇后}
else print; {完成任务，打印结果}
b[j]:=0; {回溯}
c[i+j]:=0;
d[i-j]:=0;
end;
end;
begin
for k:=-7 to 16 do {数据初始化}
begin
b[k]:=0;
c[k]:=0;
d[k]:=0;
end;
try(1);{从第1个皇后开始放置}
end.
java实现：
/*
* ８皇后问题：
*
* 问题描述：
* 在一个８×８的棋盘里放置８个皇后，要求每个皇后两两之间不相冲突
*（在每一横列，竖列，斜列只有一个皇后）。
*
* 数据表示：
* 用一个 8 位的 8 进制数表示棋盘上皇后的位置：
* 比如：45615353 表示：
* 第0列皇后在第4个位置
* 第1列皇后在第5个位置
* 第2列皇后在第6个位置
* 。。。
* 第7列皇后在第3个位置
*
* 循环变量从 00000000 加到 77777777 （8进制数）的过程，就遍历了皇后所有的情况
* 程序中用八进制数用一个一维数组 data[] 表示
*
* 检测冲突：
* 横列冲突：data[i] == data[j]
* 斜列冲突：(data[i]+i) == (data[j]+j) 或者 (data[i]-i) == (data[j]-j)
*
* 好处：
* 采用循环，而不是递规，系统资源占有少
* 可计算 n 皇后问题
* 把问题线性化处理，可以把问题分块，在分布式环境下用多台计算机一起算。
*
* ToDo：
* 枚举部分还可以进行优化，多加些判断条件速度可以更快。
* 输出部分可以修改成棋盘形式的输出
*
* @author cinc 2002-09-11
*
*/
public class Queen {
int size;
int resultCount;
public void compute ( int size ) {
this.size = size;
resultCount = 0;
int data[] = new int[size];
int count; // 所有可能的情况个数
int i,j;
// 计算所有可能的情况的个数
count = 1;
for ( i=0 ; i<size ; i++ ) {
count = count * size;
}
// 对每一个可能的情况
for ( i=0 ; i<count ; i++ ) {
// 计算这种情况下的棋盘上皇后的摆放位置，用 8 进制数表示
// 此处可优化
int temp = i;
for ( j=0 ; j<size ; j++ ) {
data [j] = temp % size;
temp = temp / size;
}
// 测试这种情况是否可行，如果可以，输出
if ( test(data) )
output( data );
}
}
/*
* 测试这种情况皇后的排列是否可行
*
*/
public boolean test( int[] data ) {
int i,j;
for ( i=0 ; i<size ; i++ ) {
for ( j=i+1 ; j<size ; j++ ) {
// 测试是否在同一排
if ( data[i] == data[j] )
return false;
// 测试是否在一斜线
if ( (data[i]+i) == (data[j]+j) )
return false;
// 测试是否在一反斜线
if ( (data[i]-i) == (data[j]-j) )
return false;
}
}
return true;
}
/*
* 输出某种情况下皇后的坐标
*
*/
public void output ( int[] data ) {
int i;
System.out.print ( ++resultCount + ": " );
for ( i=0 ; i<size ; i++ ) {
System.out.print ( "(" + i + "," + data[i] + ") " );
}
System.out.println ();
}
public static void main(String args[]) {
(new Queen()).compute( 8 );
}
}
C实现：
/*
八皇后问题：
问题提出： 8×8的棋盘上放置8个皇后，在同一横线、竖线、对角线上会产生冲突，
求不产生冲突即8个皇后都安全的放置方法。
这里改变NCOUNT即可以求出n皇后的n×n棋盘的放置方法
张可彦： [email protected]
*/
#include "stdio.h"
#define NCOUNT 8
int nArray[NCOUNT][NCOUNT];
// 判断一个点是否是安全点
bool IsSafe(int i,int j)
{
int x=i,y=j;
while(1)
{
x -= 1;
if( x<0 )break;
y -= 1;
if( y<0)break;
if( nArray[x][y] == 1)return false;
}
x=i;
y=j;
while(1)
{
x += 1;
if( x>NCOUNT-1 )break;
y += 1;
if( y >NCOUNT-1 )break;
if( nArray[x][y] == 1)return false;
}
x=i;
y=j;
while(1)
{
x -=1;
if( x<0 )break;
y +=1;
if( y>NCOUNT-1 )break;
if( nArray[x][y] == 1)return false;
}
x=i;
y=j;
while(1)
{
x +=1;
if( x>NCOUNT-1 )break;
y-=1;
if( y<0 )break;
if( nArray[x][y] == 1)return false;
}
x=i;
y=j;
while(1)
{
x -=1;
if( x<0 )break;
if( nArray[x][y] == 1)return false;
}
x=i;
y=j;
while(1)
{
x +=1;
if( x>NCOUNT-1 )break;
if( nArray[x][y] == 1)return false;
}
x=i;
y=j;
while(1)
{
y -=1;
if( y<0 )break;
if( nArray[x][y] == 1)return false;
}
x=i;
y=j;
while(1)
{
y +=1;
if( y>NCOUNT-1 )break;
if( nArray[x][y] == 1)return false;
}
return true;
}
void main()
{
int nVe=-1,nHo=0;
bool bRetry = false;
int nSol = 0;
// 清除棋盘
for(int i=0;i<NCOUNT;i++)
{
for( int j=0;j<NCOUNT;j++)
nArray[i][j] = 0;
}
while(1)
{
nVe += 1;
if( nVe>NCOUNT-1)
{// 棋盘放满，打印当前棋盘上棋子位置
nSol++;
printf("Sol %d: ",nSol);
for(int i=0;i<NCOUNT;i++)
{
for( int j=0;j<NCOUNT;j++)
if( nArray[i][j]==1)
printf("(%d,%d) ",i,j);
}
printf("\r\n");
// 回溯查找下一个可行方案
nVe -= 2;
bRetry = true;
continue;
}
int nFill = 0;
if( bRetry )
{ // 回溯计算
bRetry = false;
for( i=0;i<NCOUNT;i++)
{// 得到棋子的位置
if( nArray[nVe][i] == 1)
{
nArray[nVe][i] = 0;
nFill = i;
break;
}
}
if( nFill == NCOUNT-1)
{// 棋子在当前行已经是最后的位置
// 如果是第一行，算法结束
if( nVe == 0)return;
// 否则回溯
nVe -= 2;
bRetry = true;
continue;
}
// 从当前位置之后查找一个安全点
nFill += 1;
}
bool bFilled = false;
for( i=nFill;i<NCOUNT;i++)
{// 当前行查找一个安全点
if( IsSafe(nVe,i))
{
bFilled = true;
nArray[nVe][i] = 1;
break;
}
}
// 找不到安全点，回溯
if( !bFilled )
{
nVe -= 2;
bRetry = true;
}
}
}
[/code:1] |
|
IP卡
狗仔卡
发表于 2002-11-30 10:48:22
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
发表于 2002-12-22 18:27:50