 |
|
|
 首页 |
名片设计 CorelDRAW Illustrator AuotoCAD Painter 其他软件 Photoshop Fireworks Flash |
|
/* * ８情人问题： * * 问题描述： * 在一个８×８的棋盘里放置８个情人，要求每个情人两两之间不相冲突 *（在每一横列，竖列，斜列只有一个情人）。 * * 数据表示： * 用一个 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 ); } } 返回类别: 教程 上一教程: Mini Java编译器（一）??任务概述 下一教程: 如何快速成为Java高手 您可以阅读与"情人碰面的问题.JAVA代码"相关的教程: · [JAVA]变量作用域的问题 · 关于java socket的问题 · 每个初学JAVA者都应该搞懂的问题 · JAVA程序开发小经验 - 使用ObjectStream会出现的问题 · JAVAMAIL发信的连接SMTP验证的问题 |
  |
| 快精灵印艺坊 版权所有 |
首页 会员中心在线印刷在线编辑付款方式索取样品设计指南连锁门店
|
||
