WEB开发网
开发学院WEB开发Jsp 情人碰面的问题:JAVA代码概述 阅读

情人碰面的问题:JAVA代码概述

 2008-01-05 10:01:36 来源:WEB开发网   
核心提示:/** 8情人问题:** 问题描述:* 在一个8×8的棋盘里放置8个情人,要求每个情人两两之间不相冲突*(在每一横列,情人碰面的问题:JAVA代码概述,竖列,斜列只有一个情人),* 输出部分可以修改成棋盘形式的输出** @author cinc 2002-09-11**/public class Queen {int

  /*
  * 8情人问题:
  *
  * 问题描述:
  * 在一个8×8的棋盘里放置8个情人,要求每个情人两两之间不相冲突
  *(在每一横列,竖列,斜列只有一个情人)。
  *
  * 数据表示:
  * 用一个 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 );
  }
  }

Tags:情人 碰面 问题

编辑录入:爽爽 [复制链接] [打 印]
赞助商链接