45fan.com - 路饭网

搜索: 您的位置主页 > 网络频道 > 阅读资讯:-AIX正方形问题算法方法介绍

-AIX正方形问题算法方法介绍

2016-09-05 11:21:31 来源:www.45fan.com 【

-AIX正方形问题算法方法介绍

昨天晚上,看到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(x,y),突破点为breakPoint(x,y)
第一种:若顶极点为上边点,则按照向上优先策略,突破点为
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;

/**
*<p>Title:基础类,表示坐标点</p>
*<p>Description:AIX程序设计大赛---AIX正方形问题</p>
*<p>Copyright:Copyright(c)2006</p>
*<p>Company:qinysong</p>
*
@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;

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

publicclassAixUtil{

privatestaticintnValue;

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


/**
*<p>取得上一条路径的顶极点</p>
*
*<p>顶极点:在到达最后顶点point(n,n)之前的最后一个拐点,即第一个到达上边或右边的点<br>
*根据是到达的上边还是右边,顶极点分为两种类型<br>
*第一种:顶极点是正方形上边上的点,定义为“上边点”<br>
*第二种:顶极点是正方形右边上的点,定义为“右边点”</p>
*
*
@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;
}


/**
*<p>取得下一条路径的突破点,返回的突破点定义为breakPoint<br>
*分两种情况:<br>
*第一种:若顶极点为上边点,则按照向上优先策略,突破点为<br>
*breakPoint.x=tipPolePoint.x+1<br>
*breakPoint.y=tipPolePoint.y-1</p>
*
*<p>第二种:若顶极点为右边点,则按照向上优先策略,突破点为<br>
*breakPoint.x=(min(x)|y=tipPolePoint.y)+1即路径节点中y=tipPolePoint.y的最小x值加1<br>
*breakPoint.y=tipPolePoint.y-1</p>
*
*
@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;
}


/**
*<p>按照向上优先策略(即能往上走就往上走),取得下一条路径节点<br>
*这个函数是上面getNextPath和getFirstPath的合并,用以得到整体的下一条路径<br>
*如果previousPathPoints为空,则取得第一条路径<br>
*如果previousPathPoints不为空,则根据其取得下一条路径</p>
*
@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;

/**
*<p>Title:调用类,该类通过工具类AixUtil提供的方法,遍历一个正方形的路径</p>
*<p>Description:AIX程序设计大赛---AIX正方形问题</p>
*<p>Copyright:Copyright(c)2006</p>
*<p>Company:qinysong</p>
*
@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......");
}
}
程序输出结果如下:
当n=2时
-AIX正方形问题算法方法介绍AixUtil.mainbegin......
-AIX正方形问题算法方法介绍当n=2
-AIX正方形问题算法方法介绍Path1:(0,0)-(0,1)-(0,2)-(1,2)-(2,2)
-AIX正方形问题算法方法介绍Path2:(0,0)-(0,1)-(1,1)-(1,2)-(2,2)
-AIX正方形问题算法方法介绍Path3:(0,0)-(0,1)-(1,1)-(2,1)-(2,2)
-AIX正方形问题算法方法介绍Path4:(0,0)-(1,0)-(1,1)-(1,2)-(2,2)
-AIX正方形问题算法方法介绍Path5:(0,0)-(1,0)-(1,1)-(2,1)-(2,2)
-AIX正方形问题算法方法介绍Path6:(0,0)-(1,0)-(2,0)-(2,1)-(2,2)
-AIX正方形问题算法方法介绍Total:6
-AIX正方形问题算法方法介绍AixUtil.mainend......
-AIX正方形问题算法方法介绍
当n=3时
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......
 

本文地址:http://www.45fan.com/a/question/72692.html
Tags: aix 大赛 -AIX
编辑:路饭网
关于我们 | 联系我们 | 友情链接 | 网站地图 | Sitemap | App | 返回顶部