AIX 程序设计大赛-AIX正方形问题算法及Java程序实现（方案三）

这是到目前为止，我觉得这是最简单的实现《AIX 程序设计大赛－AIX正方形问题》的解决方案。

问题描述：

任意给定一个正方形，将正方形的各边做n等分,并将相应各点连接成水平或垂直的直线,如果从正方形的左下角(0,0)出发,沿各边线或连接线,自左向右或自下而上的方向,到达正方形的右上角(n,n),请用JAVA程序计算并输出所有可能的路径总数和具体线路.请提供相关JAVA源程序和n=2,3,4时的输出结果。输出结果按以下方式:

以n=1为例:

n = 1

Path1: (0,0) - (0,1) - (1,1)

Path2: (0,0) - (1,0) - (1,1)

Total = 2

解决思路：

由题目要求，“沿各边线或连接线,自左向右或自下而上的方向,到达正方形的右上角”，可以得出一条完整的有效的路径，即是向上走n步，向右走n步的排列组合，即可得到所有路径的条数等于：

所有路径条数=（2n）！/（n！*n！）

我们把向上走一步用 1 表示，向右走一步用 0 表示，那么一条完整的有效路径就可以表示成n个 1和n个0组成的字符串，若n=3，那么“111000”就表示向上走到（0，3），再水平走到（3，3）；“110100”就表示（0，0）-（0，1）-（0，2）-（1，2）-（1，3）-（2，3）-（3，3）。

所以所有的路径，就可以通过遍历从二进制“0...01...1”到“1...10...0”之间的所有数，只要其二进制表示中含有n个1，就是一条有效的路径。

算法特点：

本算法将几何问题，抽象成排列组合问题，因此实现算法理解性非常好，程序实现也非常简单，只是和前面两篇文章中的算法相比，对于每一０～11…100…0（二进制数）之间的数都要判断，所以性能上相对差一些。

程序设计：

这个算法的程序实现非常简单，在这里用两个类来实现，一个命名为AixUtil3，表示用到的各种方法，另一个命名AixClient3，通过调用AixUtil3遍历正方形的各条路径并打印。

Java程序源代码：

AixUtil3：处理类，按照向上优先策略，提供解决AIX正方形问题的一些静态方法

packageqinysong.aix;

/**
*<p>Title:方案3，通过抽象成排列组合进行实现</p>
*<p>Description:AIX程序设计大赛---AIX正方形问题</p>
*<p>Copyright:Copyright(c)2006</p>
*<p>Company:qinysong</p>
*@authorzhaoqingsong
*@version1.0
*/

publicclassAixUtil3{

privatestaticintnValue;
privatestaticintminValue;
privatestaticintmaxValue;
privatestaticint[]binaryArray;

/**
*初始化正方形边长
*@paramnValueint
*/
publicstaticvoidinitNValue(intnValue){
if(nValue<=0){
thrownewRuntimeException("初始化正方形边长异常，长度不能小于等于零");
}
AixUtil3.nValue=nValue;
binaryArray=newint[2*nValue];
StringbinaryString1="";
StringbinaryString0="";
for(inti=0;i<nValue;i++){
binaryString1+="1";
binaryString0+="0";
}
minValue=Integer.parseInt(binaryString0+binaryString1,2);
maxValue=Integer.parseInt(binaryString1+binaryString0,2);
}

/**
*取得路径值为pathValue,二进制字符串中1的个数
*并将二进制字符串进行缓存,以便取得该值所对应的路径
*@parampathValueint路径值
*@returnint二进制字符串中1的个数
*/
publicstaticintgetOneBitCount(intpathValue){
intindex=0;
intoneBitCount=0;
intmodules=0;
inttempValue=pathValue;
while(tempValue>0){
modules=tempValue%2;
oneBitCount+=modules;
binaryArray[index++]=modules;
tempValue=tempValue/2;
}
returnoneBitCount;
}

/**
*取得当前缓存路径值,所对应的路径
*@parampathNumberint该路径为第几条路径
*@returnString路径字符串
*/
publicstaticStringgetCurrentPathPoint(intpathNumber){
StringBufferpathPointBuffer=newStringBuffer("Path"+pathNumber+":(0,0)");
intzeroCount=0;
intoneCount=0;
for(inti=0;i<2*nValue;i++){
if(binaryArray[i]==1){
oneCount++;
}else{
zeroCount++;
}
pathPointBuffer.append("-("+oneCount+","+zeroCount+")");
}
returnpathPointBuffer.toString();
}

publicstaticintgetMinValue(){
returnminValue;
}
publicstaticintgetMaxValue(){
returnmaxValue;
}
}

AixClient3：一个简单的调用类，通过调用AixUtil3实现方案三的遍历

packageqinysong.aix;

importjava.util.Date;

/**
*<p>Title:方案3的调用客户端，通过方案3工具类AixUtil3，遍历一个正方形的路径</p>
*<p>Description:AIX程序设计大赛---AIX正方形问题</p>
*<p>Copyright:Copyright(c)2006</p>
*<p>Company:qinysong</p>
*@authorzhaoqingsong
*@version1.0
*/

publicclassAixClient3{

publicstaticvoidmain(String[]args){
System.out.println("AixClient3.mainbegin......");
System.out.println("AixClient3.main方案3");
DatebeginTime3=newDate();
System.out.println("beginTime3:"+beginTime3.toString());
//初始化
intnValue=15;
AixUtil3.initNValue(nValue);
intminValue=AixUtil3.getMinValue();
intmaxValue=AixUtil3.getMaxValue();
intavailablePathCount=0;
StringpathPointString="";
//从minValue到maxValue,遍历所有整数,如果字符串中1的个数等于nValue,即为一条有效路径
for(inti=minValue;i<=maxValue;i++){
if(AixUtil3.getOneBitCount(i)==nValue){
++availablePathCount;
pathPointString=AixUtil3.getCurrentPathPoint(availablePathCount);
System.out.println(pathPointString);
}
}
System.out.println("pathCount:"+availablePathCount);
DateendTime3=newDate();
System.out.println("endendTime3:"+endTime3.toString());
System.out.println("方案3所花时间毫秒:"+(endTime3.getTime()-beginTime3.getTime()));
System.out.println("AixClient3.mainend......");
}
}