情人碰面的問題.JAVA代碼

2019-11-18 13:47:47

字體：大中小

來源：轉載

供稿：網友

　　/*
* ８情人問題：
*
* 問題描述：
* 在一個８×８的棋盤里放置８個情人，要求每個情人兩兩之間不相沖突
*（在每一橫列，豎列，斜列只有一個情人）。
*
* 數據表示：
* 用一個 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 ();

上一篇：全面解析定義方法

下一篇：求出e=1+1/1!+1/2!+1/3!+……+1/n!+……的近似值的java applet程序