熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> Java編程 >> JSP教程 >> 正文

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

2013-11-15 11:37:11  來源: JSP教程 

  /*
  * 8情人問題
  *
  * 問題描述
  * 在一個8×8的棋盤裡放置8個情人要求每個情人兩兩之間不相沖突
  *(在每一橫列豎列斜列只有一個情人)
  *
  * 數據表示
  * 用一個 位的 進制數表示棋盤上情人的位置
  * 比如 表示
  *    第列情人在第個位置
  *    第列情人在第個位置
  *    第列情人在第個位置
  *   
  *    第列情人在第個位置
  *
  * 循環變量從 加到 進制數)的過程就遍歷了情人所有的情況
  * 程序中用八進制數用一個一維數組 data[] 表示
  *
  * 檢測沖突
  *   橫列沖突data[i] == data[j]
  *   斜列沖突(data[i]+i) == (data[j]+j) 或者 (data[i]i) == (data[j]j)
  *
  * 好處
  * 采用循環而不是遞規系統資源占有少
  * 可計算 n 情人問題
  * 把問題線性化處理可以把問題分塊在分布式環境下用多台計算機一起算
  *
  * ToDo
  *  枚舉部分還可以進行優化多加些判斷條件速度可以更快
  *  輸出部分可以修改成棋盤形式的輸出
  *
  * @author cinc
  *
  */
  
  public class Queen {
  int size;
  int resultCount;
  
  public void compute ( int size ) {
  thissize = size;
  resultCount = ;
  int data[] = new int[size];
  int count; // 所有可能的情況個數
  int ij;
  
  // 計算所有可能的情況的個數
  count = ;
  for ( i= ; i<size ; i++ ) {
  count = count * size;
  }
  // 對每一個可能的情況
  for ( i= ; i<count ; i++ ) {
  // 計算這種情況下的棋盤上情人的擺放位置 進制數表示
  // 此處可優化
  int temp = i;
  for ( j= ; j<size ; j++ ) {
  data [j] = temp % size;
  temp = temp / size;
  }
  // 測試這種情況是否可行如果可以輸出
  if ( test(data) )
  output( data );
  }
  }
  
  /*
  * 測試這種情況情人的排列是否可行
  *
  */
  public boolean test( int[] data ) {
  int ij;
  for ( i= ; i<size ; i++ ) {
  for ( j=i+ ; 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;
  Systemoutprint ( ++resultCount + : );
  for ( i= ; i<size ; i++ ) {
  Systemoutprint ( ( + i + + data[i] + );
  }
  Systemoutprintln ();
  }
  
  //main()就是在這裡
  public static void main(String args[]) {
  (new Queen()pute( );
  }
  }
From:http://tw.wingwit.com/Article/program/Java/JSP/201311/19303.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.