Java

本类阅读TOP10

·使用MyEclipse开发Struts框架的Hello World!(录像1)
·hibernate配置笔记
·AOP编程入门--Java篇
·linux下Tomcat 5.0.20 与 Apache 2 安装/集成/配置
·在win2003下整合了整合Tomcat5.5+ apache_2.0.53+ mod_jk_2.0.47.dll
·构建Linux下IDE环境--Eclipse篇
·Jsp 连接 mySQL、Oracle 数据库备忘(Windows平台)
·ASP、JSP、PHP 三种技术比较
·Tomcat5.5.9的安装配置
·AWT GUI 设计笔记(二)

分类导航
VC语言Delphi
VB语言ASP
PerlJava
Script数据库
其他语言游戏开发
文件格式网站制作
软件工程.NET开发
情人碰面的问题.JAVA代码

作者:未知 来源:月光软件站 加入时间:2005-5-13 月光软件站

/*
 * 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 );
    }
}




相关文章

相关软件