今天又对前天所实现的《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
解决思路:
上篇回顾
上一篇文章中的解决思路,为通过采用“向上优先”策略,发现通过上一条路径可以直接推导出下一条路径,在这个推导过程中,定义了两个关键点,一个命名为上一条路径的“顶极点”,一个命名为下一条路径的“突破点”,并发现这两个点之间的关系:
第一种:若顶极点为上边点,则按照向上优先策略,突破点和顶极点关系为:
breakPoint.x = tipPolePoint.x+1
breakPoint.y = tipPolePoint.y-1
第二种:若顶极点为右边点,则按照向上优先策略,突破点和顶极点关系为:
breakPoint.x = (min(x)|y=tipPolePoint.y)+1
breakPoint.y = tipPolePoint.y-1
思路优化
通过进一步的分析,发现以上描述的突破点和顶极点的两种关系,最核心的其实是“最后右拐点”,通过最后右拐点我们既可以简化(上一条路径)顶极点的查找,又可以简化(下一条路径)突破点的推导。
最后右拐点定义:既一条路径中最有一次向右拐弯的那个点。
依然按照向上优先侧略,下一条路径的突破点和上一条路径的最后右拐点,之间的关系为:
设:最后右拐点为lastRightTurnPoint,突破点为breakPoint。则有
breakPoint.x = lastRightTurnPoint.x+1
breakPoint.y = lastRightTurnPoint.y-1
算法特点
由于该算法统一了第一种算法中突破点推导的两种方法,简化了推导过程,所以思路更加清晰、效率更加高效。
程序设计:
和以上算法设计类似,这个算法的实现也包括三个类,分别简述如下:
Point:基础类,表示坐标点,和第一方案相同;
AixUtil2:工具类,按照向上优先策略,提供解决AIX正方形问题的一些静态方法,是第一方案的优化;
AixClient:一个简单的调用类,可同时测试方案一(调用AixUtil)和方案二(调用AixUtil2)。
源程序代码如下:
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);
}
}
AixUtil2:工具类,按照向上优先策略,提供解决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$
*/
publicclassAixUtil2{
privatestaticintnValue;
privatestaticintlaseRightTurnIndex;
privatestaticPoint[]squarePoints=null;
/**
*初始化正方形边长
*@paramnValueint
*/
publicstaticvoidinitNValue(intnValue){
if(nValue<=0){
thrownewRuntimeException("初始化正方形边长异常,长度不能小于等于零");
}
AixUtil2.nValue=nValue;
squarePoints=newPoint[(nValue+1)*(nValue+1)];
for(inty=0;y<=nValue;y++){
for(intx=0;x<=nValue;x++){
squarePoints[y*(nValue+1)+x]=newPoint(x,y);
}
}
}
/**
*<p>取得上一条路径的最后右拐点</p>
*<p>最后右拐点:在到达最后顶点point(n,n)之前的最后一个向右拐的点<br>
*
*@parampreviousPathPointsPoint[]上一条路径节点数组
*@returnPointtipPolePoint顶极点
*/
publicstaticPointgetLastRightTurnPoint(Point[]previousPathPoints){
PointlastRightTurnPoint=null;
intindex=2*nValue;
while(previousPathPoints[index].x==nValue
||previousPathPoints[index].y==previousPathPoints[index-1].y){
index--;
}
laseRightTurnIndex=index;
lastRightTurnPoint=previousPathPoints[index];
returnlastRightTurnPoint;
}
/**
*<p>取得下一条路径的突破点,返回的突破点定义为breakPoint<br>
*通过几何数学分析,按照向上优先策略,有如下突破点和上一条路径的最后右拐点的关系<br>
*breakPoint.x=lastRightTurnPoint.x+1<br>
*breakPoint.y=lastRightTurnPoint.y-1</p>
*
*@paramlastRightTurnPointPoint最后右拐点,表示上一条路径的最后右拐点
*@returnPoint返回下一条路径的突破点breakPoint
*/
publicstaticPointgetBreakPoint(PointlastRightTurnPoint){
intindex=(lastRightTurnPoint.y-1)*(nValue+1)+lastRightTurnPoint.x+1;
PointbreakPoint=squarePoints[index];
returnbreakPoint;
}
/**
*按照向上优先策略(即能往上走就往上走),取得下一个路径节点
*@paramcurrentPointPoint
*@returnPoint下一个路径节点
*/
publicstaticPointgetNextPoint(PointcurrentPoint){
intindex=0;
if(currentPoint.y<nValue){
index=(currentPoint.y+1)*(nValue+1)+currentPoint.x;
}elseif(currentPoint.x<nValue){
index=(currentPoint.y)*(nValue+1)+currentPoint.x+1;
}else{
returnnull;
}
returnsquarePoints[index];
}
/**
*按照向上优先策略(即能往上走就往上走),取得下一条路径节点
*@parampreviousPathPointsPoint[]上一条路径节点
*@returnPoint[]下一条路径
*/
publicstaticPoint[]getNextPath(Point[]previousPathPoints){
intarrayLength=2*nValue+1;
PointlastRightTurnPoint=getLastRightTurnPoint(previousPathPoints);
PointbreakPoint=getBreakPoint(lastRightTurnPoint);
Point[]nextPath=newPoint[arrayLength];
intindex=0;
for(;index<laseRightTurnIndex;index++){
nextPath[index]=previousPathPoints[index];
}
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]=squarePoints[i*(nValue+1)];
}
for(inti=1;i<=nValue;i++){
firstPath[nValue+i]=squarePoints[nValue*(nValue+1)+i];
}
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)和方案二(调用AixUtil2)
packageqinysong.aix;
importjava.util.Date;
/**
*<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("AixClient.mainbegin......");
System.out.println("AixClient.main方案1");
DatebeginTime1=newDate();
System.out.println("beginTime1:"+beginTime1.toString());
intnValue=5;
Point[]pathPoints=null;
intpathNumber=0;
System.out.println("当n="+nValue);
AixUtil.initNValue(nValue);
do{
pathPoints=AixUtil.getTotalNextPath(pathPoints);
++pathNumber;
AixUtil.printlnPathPoints(pathNumber,pathPoints);
}while(!AixUtil.isLastPath(pathPoints));
System.out.println("Total:"+pathNumber);
DateendTime1=newDate();
System.out.println("endendTime1:"+endTime1.toString());
System.out.println("AixClient.main方案2");
DatebeginTime2=newDate();
System.out.println("beginTime2:"+beginTime2.toString());
System.out.println("当n="+nValue);
AixUtil2.initNValue(nValue);
pathPoints=null;
pathNumber=0;
do{
pathPoints=AixUtil2.getTotalNextPath(pathPoints);
++pathNumber;
AixUtil2.printlnPathPoints(pathNumber,pathPoints);
}while(!AixUtil2.isLastPath(pathPoints));
System.out.println("Total:"+pathNumber);
DateendTime2=newDate();
System.out.println("endendTime2:"+endTime2.toString());
System.out.println("方案1所花时间毫秒:"+(endTime1.getTime()-beginTime1.getTime()));
System.out.println("方案2所花时间毫秒:"+(endTime2.getTime()-beginTime2.getTime()));
System.out.println("AixClient.mainend......");
}
}
分享到:
相关推荐
此资源为AIX7.2版本 cd1和cd2,已经上传度盘 aix_7200-04-02-2027_1of2_072020.iso aix_7200-04-02-2027_2of2_072020.iso 通过qemu-system-ppc程序能在X86平台安装运行 此资源为AIX7.1版本 cd1和cd2 AIX_7.1_Base_...
aix_nmon--用于监控aix系统中的各项资源使用情况
AIX 技术资料-AIX 技术资料-AIX 技术资料-AIX 技术资料-AIX 技术资料-AIX 技术资料-AIX 技术资料-AIX 技术资料-AIX 技术资料-AIX 技术资料-AIX 技术资料-AIX 技术资料-
AIX JDK1.8 JRE1.8 IBM官网下载的安装包 jdk 和jre都有 64位,由于官网下载太慢,这里另存一份,需要的同学自取
AIX 7100-03-02 CD1+CD2 两个镜像下载AIX 7100-03-02 CD1+CD2 两个镜像下载AIX 7100-03-02 CD1+CD2 两个镜像下载AIX 7100-03-02 CD1+CD2 两个镜像下载
Oracle Database 19c (AIX.PPC64_193000_grid_home.zip), 适用于IBM AIX 系统,文件分割成 四个 压缩包,必须集齐 四个 文件后才能一起解压一起使用: AIX.PPC64_193000_grid_home.part1.rar ... ...
AIX培训笔记---AIX操作系统中级教程
aix宝典---命令、LVM、设备管理等
AIX维护大全--为解决日常维护,因此收集到该文档
AIX学习笔记---系统管理和网络管理等
AIX视频教程1-smit AIX视频教程1-smit AIX视频教程1-smit
AIX 手册1-18 10英文 AIX 手册1-18 10英文
AIX命令介绍篇-find-命令实例讲解.doc
AIX上vg--pv-filesystem基础.doc
参考:china.emc.... 环境:2台 aix5.3-08-05 &2台 aix6.1-01-02 这些机器通过fc与cx300连接,能正常使用,能正产识别。 通过tcpip与EMC CX4-120连接。没有配置chap AIX新版本中都是自带Initiator
AIX-IO-Perf-ohvcmg 硬盘检测
aix篇-cpu-men-io性能观察.part1.ra
AIX5_3-64bit 下JDK1_6&WebLogic Server10_3的安装
等保测评-AIX测评指导书