AIX 程序设计大赛－AIX正方形问题算法及Java程序实现

huobengluantiao8

浏览: 1031093 次

最近访客更多访客>>

u012363178

wangyy

lsmh2000

shlpyy

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (1470)

社区版块

存档分类

昨天晚上，看到CSDN上西部阿呆-小草屋的一篇Blog 《AIX 程序设计大赛---AIX正方形问题》，描述了Aix正方形问题，并给出了Java解决方法，感觉这道题很有趣味和手痒，所以也花了将近一个晚上的时间，用有别于小草屋的思路通过Java程序进行了解决。

由于有很长时间没有接触数学方面的知识了，所以解法上或概念上有什么不对/或不当之处，请对该题也感兴趣的朋友多多指教，希望通过共同探讨找到一个优秀的解决方案。

问题描述：

任意给定一个正方形，将正方形的各边做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

解决思路：

通过对上述问题的分析，有一条约束很关键，就是“沿各边线或连接线,自左向右或自下而上的方向,到达正方形的右上角”，根据该约束我们找到一个探寻路径的策略（或称作规则）：向上优先策略，即在探寻一条路径的时候，只要能够向上走，我们就向上走，也就是只在最后一步才向右拐。这样按照这个策略，我们就可以从第一条路径（沿着左边和上边），逐条遍历所有路径。

确定按照向上优先策略遍历路径后，分析发现，在这个探寻路径的过程中，有一个点非常重要，我在这里称作“顶极点”，定义如下：

顶极点：在到达终点point（n，n）之前最后一个拐点，根据这个点是在正方形的上边还是右边，我们分为两种类型：

第一种：顶极点是正方形上边上的点，称作为“上边点”

第二种：顶极点是正方形右边上的点，称作为“右边点”

按照向上优先策略，通过上一条路径的顶极点可以唯一确定下一条路径的突破点，突破点定义如下：

突破点：下一条路径沿着上一条路径，所走出的第一个不同点。

通过分析发现突破点和顶极点之间的关系如下：

我们设定顶极点为：tipPolePoint（ｘ，ｙ），突破点为breakPoint（ｘ，ｙ）

第一种：若顶极点为上边点，则按照向上优先策略，突破点为

breakPoint.x = tipPolePoint.x+1

breakPoint.y = tipPolePoint.y-1

第二种：若顶极点为右边点，则按照向上优先策略，突破点为

breakPoint.x = (min(x)|y=tipPolePoint.y)+1（不知道这种表示形式对不对）意思是路径节点中y=tipPolePoint.y的最小 x 值加 1

breakPoint.y = tipPolePoint.y-1

算法特点

由于该算法是通过找到路径之间的关系，通过上一条路径直接推导出下一条路径，所以无需采用递归算法，因此在一定程度上免去了探索回溯的性能开销。

程序设计：

根据以上分析，进行Java程序设计，包括三个类，分别简述如下：

Point：基础类，表示坐标点；

AixUtil：工具类，按照向上优先策略，提供解决AIX正方形问题的一些静态方法；

AixClient：一个简单的调用类，通过工具类AixUtil方法，遍历一个正方形的所有路径。

源程序代码如下：

Point：基础类，表示坐标点；

packageqinysong.aix;

/**
*Title:基础类，表示坐标点
*Description:AIX程序设计大赛---AIX正方形问题
*Copyright:Copyright(c)2006
*Company:qinysong
*@authorzhaoqingsong
*@version1.0$Date:2006/09/0521:44:36$
*/

publicclassPoint{
protectedintx;
protectedinty;

/**
*构造函数
*@paramxint
*@paramyint
*/
publicPoint(intx,inty){
this.x=x;
this.y=y;
}

publicStringtoString(){
return"("+x+","+y+")";
}

/**
*判断是否为上边点
*@returnboolean
*/
publicbooleanisTopBorderPoint(intnValue){
returnthis.y==nValue;
}

/**
*判断thePoint是否与自己相等
*@paramthePointPoint
*@returnboolean
*/
publicbooleanequals(PointthePoint){
return(this.x==thePoint.x)&&(this.y==thePoint.y);
}

}

AixUtil：工具类，按照向上优先策略，提供解决AIX正方形问题的一些静态方法；

packageqinysong.aix;

/**
*Title:工具类，按照向上优先策略，提供解决AIX正方形问题的一些静态方法
*Description:AIX程序设计大赛---AIX正方形问题
*Copyright:Copyright(c)2006
*Company:qinysong
*@authorzhaoqingsong
*@version1.0$Date:2006/09/0521:52:18$
*/

publicclassAixUtil{

privatestaticintnValue;

/**
*初始化正方形边长
*@paramnValueint
*/
publicstaticvoidinitNValue(intnValue){
if(nValue<=0){
thrownewRuntimeException("初始化正方形边长异常，长度不能小于等于零");
}
AixUtil.nValue=nValue;
}

/**
*取得上一条路径的顶极点
*
*顶极点：在到达最后顶点point（n，n）之前的最后一个拐点，即第一个到达上边或右边的点 
*根据是到达的上边还是右边，顶极点分为两种类型 
*第一种：顶极点是正方形上边上的点，定义为“上边点” 
*第二种：顶极点是正方形右边上的点，定义为“右边点”
*
*@parampreviousPathPointsPoint[]上一条路径节点数组
*@returnPointtipPolePoint顶极点
*/
publicstaticPointgetTipPolePoint(Point[]previousPathPoints){
PointtipPolePoint=null;
intlastIndex=2*nValue;
if(previousPathPoints[lastIndex-1].y==previousPathPoints[lastIndex].y){//取得上边点
for(inti=lastIndex;i>0;i--){
if(previousPathPoints[i-1].y!=previousPathPoints[i].y){
tipPolePoint=previousPathPoints[i];
break;
}
}
}else{//取得右边点
for(inti=lastIndex;i>0;i--){
if(previousPathPoints[i-1].x!=previousPathPoints[i].x){
tipPolePoint=previousPathPoints[i];
break;
}
}
}
returntipPolePoint;
}

/**
*取得下一条路径的突破点，返回的突破点定义为breakPoint 
*分两种情况: 
*第一种:若顶极点为上边点,则按照向上优先策略,突破点为 
*breakPoint.x=tipPolePoint.x+1 
*breakPoint.y=tipPolePoint.y-1
*
*第二种:若顶极点为右边点,则按照向上优先策略,突破点为 
*breakPoint.x=(min(x)|y=tipPolePoint.y)+1即路径节点中y=tipPolePoint.y的最小x值加1 
*breakPoint.y=tipPolePoint.y-1
*
*@parampreviousPathPointsPoint[]路径节点数组,表示上一条路径的节点序列
*@paramtipPolePointPoint顶极点,表示上一条路径的顶级点
*@returnPoint返回下一条路径的突破点breakPoint
*/
publicstaticPointgetBreakPoint(Point[]previousPathPoints,PointtipPolePoint){
PointbreakPoint=null;
intarrayLength=2*nValue+1;
intx=0;
inty=0;
if(tipPolePoint.isTopBorderPoint(nValue)){
x=tipPolePoint.x+1;
y=tipPolePoint.y-1;
}else{
PointleftPointOnLine=null;
for(inti=arrayLength-1;i>0;i--){
if(previousPathPoints[i].y>tipPolePoint.y)continue;
if(previousPathPoints[i-1].y!=previousPathPoints[i].y){
leftPointOnLine=previousPathPoints[i];
break;
}
}
x=leftPointOnLine.x+1;
y=leftPointOnLine.y-1;
}
breakPoint=newPoint(x,y);
returnbreakPoint;
}

/**
*按照向上优先策略（即能往上走就往上走），取得下一个路径节点
*@paramcurrentPointPoint
*@returnPoint下一个路径节点
*/
publicstaticPointgetNextPoint(PointcurrentPoint){
intx=0;
inty=0;
if(currentPoint.y<nValue){
x=currentPoint.x;
y=currentPoint.y+1;
}elseif(currentPoint.x<nValue){
x=currentPoint.x+1;
y=currentPoint.y;
}else{
returnnull;
}
returnnewPoint(x,y);
}

/**
*按照向上优先策略（即能往上走就往上走），取得下一条路径节点
*@parampreviousPathPointsPoint[]上一条路径节点
*@returnPoint[]下一条路径
*/
publicstaticPoint[]getNextPath(Point[]previousPathPoints){
intarrayLength=2*nValue+1;
PointtipPolePoint=getTipPolePoint(previousPathPoints);
PointbreakPoint=getBreakPoint(previousPathPoints,tipPolePoint);
PointlastKeepPoint=newPoint(breakPoint.x-1,breakPoint.y);
Point[]nextPath=newPoint[arrayLength];
intindex=0;
for(;index<arrayLength;index++){
nextPath[index]=previousPathPoints[index];
if(previousPathPoints[index].equals(lastKeepPoint)){
break;
}
}
nextPath[++index]=breakPoint;
PointtempPoint=breakPoint;
while((tempPoint=getNextPoint(tempPoint))!=null){
nextPath[++index]=tempPoint;
}
returnnextPath;
}

/**
*按照向上优先策略，取得第一条路径
*@returnPoint[]
*/
publicstaticPoint[]getFirstPath(){
Point[]firstPath=newPoint[2*nValue+1];
for(inti=0;i<=nValue;i++){
firstPath[i]=newPoint(0,i);
}
for(inti=1;i<=nValue;i++){
firstPath[nValue+i]=newPoint(i,nValue);
}
returnfirstPath;
}

/**
*按照向上优先策略（即能往上走就往上走），取得下一条路径节点 
*这个函数是上面getNextPath和getFirstPath的合并，用以得到整体的下一条路径 
*如果previousPathPoints为空，则取得第一条路径 
*如果previousPathPoints不为空，则根据其取得下一条路径
*@parampreviousPathPointsPoint[]上一条路径节点
*@returnPoint[]下一条路径
*/
publicstaticPoint[]getTotalNextPath(Point[]previousPathPoints){
if(previousPathPoints==null){
returngetFirstPath();
}else{
returngetNextPath(previousPathPoints);
}
}

/**
*判断是否是最后一条路径
*@parampathPointsPoint[]
*@returnboolean
*/
publicstaticbooleanisLastPath(Point[]pathPoints){
intmiddleIndex=nValue;
returnpathPoints[middleIndex].y==0;
}

/**
*按照题目要求格式打印一条路径的节点
*@parampathNumberint
*@parampathPointsPoint[]
*/
publicstaticvoidprintlnPathPoints(intpathNumber,Point[]pathPoints){
StringBufferpathStringBuffer=newStringBuffer();
pathStringBuffer.append("Path"+pathNumber+"：");
intarrayLength=2*nValue+1;
for(inti=0;i<arrayLength;i++){
pathStringBuffer.append(pathPoints[i].toString()+"-");
}
StringpathString=pathStringBuffer.toString();
if(pathString.length()>0)pathString=pathString.substring(0,pathString.length()-1);
System.out.println(pathString);
}

}

AixClient：一个简单的调用类，通过工具类AixUtil方法，遍历一个正方形的所有路径。

packageqinysong.aix;

/**
*Title:调用类,该类通过工具类AixUtil提供的方法，遍历一个正方形的路径
*Description:AIX程序设计大赛---AIX正方形问题
*Copyright:Copyright(c)2006
*Company:qinysong
*@authorzhaoqingsong
*@version1.0$Date:2006/09/0522:49:22$
*/

publicclassAixClient{

publicstaticvoidmain(String[]args){
System.out.println("AixUtil.mainbegin......");
intnValue=2;
System.out.println("当n="+nValue);
AixUtil.initNValue(nValue);
Point[]pathPoints=null;
intpathNumber=0;
do{
pathPoints=AixUtil.getTotalNextPath(pathPoints);
AixUtil.printlnPathPoints(++pathNumber,pathPoints);
}while(!AixUtil.isLastPath(pathPoints));
System.out.println("Total："+pathNumber);

System.out.println("AixUtil.mainend......");
}
}

程序输出结果如下：

当ｎ＝２时

AixUtil.mainbegin......

当n=2

Path1：(0,0)-(0,1)-(0,2)-(1,2)-(2,2)

Path2：(0,0)-(0,1)-(1,1)-(1,2)-(2,2)

Path3：(0,0)-(0,1)-(1,1)-(2,1)-(2,2)

Path4：(0,0)-(1,0)-(1,1)-(1,2)-(2,2)

Path5：(0,0)-(1,0)-(1,1)-(2,1)-(2,2)

Path6：(0,0)-(1,0)-(2,0)-(2,1)-(2,2)

Total：6

AixUtil.mainend......

当ｎ＝３时

AixUtil.mainbegin......
当n=3
Path1：(0,0)-(0,1)-(0,2)-(0,3)-(1,3)-(2,3)-(3,3)
Path2：(0,0)-(0,1)-(0,2)-(1,2)-(1,3)-(2,3)-(3,3)
Path3：(0,0)-(0,1)-(0,2)-(1,2)-(2,2)-(2,3)-(3,3)
Path4：(0,0)-(0,1)-(0,2)-(1,2)-(2,2)-(3,2)-(3,3)
Path5：(0,0)-(0,1)-(1,1)-(1,2)-(1,3)-(2,3)-(3,3)
Path6：(0,0)-(0,1)-(1,1)-(1,2)-(2,2)-(2,3)-(3,3)
Path7：(0,0)-(0,1)-(1,1)-(1,2)-(2,2)-(3,2)-(3,3)
Path8：(0,0)-(0,1)-(1,1)-(2,1)-(2,2)-(2,3)-(3,3)
Path9：(0,0)-(0,1)-(1,1)-(2,1)-(2,2)-(3,2)-(3,3)
Path10：(0,0)-(0,1)-(1,1)-(2,1)-(3,1)-(3,2)-(3,3)
Path11：(0,0)-(1,0)-(1,1)-(1,2)-(1,3)-(2,3)-(3,3)
Path12：(0,0)-(1,0)-(1,1)-(1,2)-(2,2)-(2,3)-(3,3)
Path13：(0,0)-(1,0)-(1,1)-(1,2)-(2,2)-(3,2)-(3,3)
Path14：(0,0)-(1,0)-(1,1)-(2,1)-(2,2)-(2,3)-(3,3)
Path15：(0,0)-(1,0)-(1,1)-(2,1)-(2,2)-(3,2)-(3,3)
Path16：(0,0)-(1,0)-(1,1)-(2,1)-(3,1)-(3,2)-(3,3)
Path17：(0,0)-(1,0)-(2,0)-(2,1)-(2,2)-(2,3)-(3,3)
Path18：(0,0)-(1,0)-(2,0)-(2,1)-(2,2)-(3,2)-(3,3)
Path19：(0,0)-(1,0)-(2,0)-(2,1)-(3,1)-(3,2)-(3,3)
Path20：(0,0)-(1,0)-(2,0)-(3,0)-(3,1)-(3,2)-(3,3)
Total：20
AixUtil.mainend......

分享到：