情人碰面的問題：JAVA代碼概述

2019-11-18 13:09:43

字體：大中小

來源：轉載

供稿：網友

　　/*
　　* ８情人問題：
　　*
　　* 問題描述：
　　* 在一個８×８的棋盤里放置８個情人，要求每個情人兩兩之間不相沖突
　　*（在每一橫列，豎列，斜列只有一個情人）。
　　*
　　* 數據表示：
　　* 用一個 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 ();
　　}
　　
　　//main()就是在這里.
　　public static void main(String args[]) {
　　(new Queen()).compute( 8 );
　　}
　　}

上一篇：教你如何利用JAVACC將HQL轉換為SQL

下一篇：查詢頁面顯示進度條,load成功后隱去進度條