<iframe align="top" marginwidth="0" marginheight="0" src="http://www.zealware.com/csdnblog01.html" frameborder="0" width="728" scrolling="no" height="90"></iframe>
AIX 程序设计大赛---AIX正方形问题
作者:成晓旭
作为“算法及实现”栏目的“抛砖引玉”之作,将自己2年多前实现的一个算法放出来。有一年IBM出了这个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
[设计简介]:
共设计3个类:
AixPoint:正方形问题的低层处理类,抽象正方形问题的每个访问点信息;
AixSquare:正方形问题的核心处理类,抽象正方形算法处理过程;
AixContest:正方形问题的客户调用处理类,抽象正方形问题的应用层。
[算法源码]:
AixPoint源码:
/***//*******************************************************************************
*>
*AIXContestver1.0
*开发作者:成晓旭
*项目简述:AIX程序设计的Java程序设计"AIX正方形问题"解决方案
*启动时间:2004年01月14日20:00:08
*完成时间:2003年01月14日20:09:00
*
*开发环境:Windows2000Professional+SUNJ2SE1.4.2
*开发工具:RationalRose2002Enterprise+JCreator2.5Pro
*
*文件名称:AixPoint.java
*简介:正方形问题的低层处理类,抽象正方形问题的每个访问点信息
*
*备注:
*
*修改时间1:
*
******************************************************************************/
packageCXXSoft.Aix;
importjava.awt.Point;
publicclassAixPointextendsPoint
...{
privateintmoveUnit;
publicbooleanaheadExcess;
publicbooleanaboveExcess;
//类构造器
publicAixPoint()
...{
aheadExcess=false;
aboveExcess=false;
moveUnit=1;
}
//类构造器
publicAixPoint(intx,inty)
...{
this();
this.x=x;
this.y=y;
}
//类构造器
publicAixPoint(Pointp)
...{
this();
this.x=p.x;
this.y=p.y;
}
//向左移动(前进)
publicvoidgoAhead()
...{
this.x+=moveUnit;
}
//向左的反方向移动(后退)
publicvoidgoAheadReturn()
...{
this.x-=moveUnit;
}
//向上移动
publicvoidgoAbove()
...{
this.y+=moveUnit;
}
//向上的反方向移动(后退)
publicvoidgoAboveReturn()
...{
this.y-=moveUnit;
}
//形成输出串
publicStringtoString()
...{
return"("+x+","+y+")";
}
}
AixSquare源码:
/***//*******************************************************************************
*>
*AIXContestver1.0
*开发作者:成晓旭
*项目简述:AIX程序设计的Java程序设计"AIX正方形问题"解决方案
*启动时间:2004年01月14日20:28:00
*完成时间:2003年01月17日00:16:00
*
*开发环境:Windows2000Professional+SUNJ2SE1.4.2
*开发工具:RationalRose2002Enterprise+JCreator2.5Pro
*
*文件名称:AixSquare.java
*简介:正方形问题的核心处理类,抽象正方形算法处理过程
*
*备注:
*
*修改时间1:
*
*[问题描述]:
*任意给定一个正方形,将正方形的各边做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
*
*[解答思路]:
*此问题的核心是一个"有向无环图"的遍历问题,
*解答的思想就是一个"试探"与"回溯"算法的抽象与实现.甚至比完整的
*"有向无环图"的遍历问题还要简单.
*
*[建模提示]:
*为了简化问题的处理过程,强调解决问题的实质性思路,在建模过程中,
*对遍历过程中每步"前进"的步长进行了"固定步长为1"的假设,即对将被
*n等分的正方形的边长,自动设置为n,以简化算法中对边的计算处理.
*
*[算法优化]:
*目前设计的算法有以下几处有待优化:
*1:此题是一般的"试探"与"回溯"算法一个特例,所以有些处理过程是可以省略的
*(目前实现的是一个标准的"试探"与"回溯"算法)
*2:由于题目自身的特殊性,对某些处理过程可做简化,以提高算法的执行效率
*(如:对进栈,出栈的处理,对访问队列的处理,对在正方形边上"前进"时的
*回溯处理,对临界条件,到达目标点条件的判断等等)
*3:问题的本身及解答此题的思路是很具一般性的,但目前分析,设计的类结构过于特殊化.
*
******************************************************************************/
packageCXXSoft.Aix;
importjava.awt.Point;
importjava.util.Stack;
importjava.util.Vector;
importjava.util.List;
importCXXSoft.Aix.AixPoint;
publicclassAixSquare
...{
//AIX正方形问题点遍历时前进方向常量定义
privatefinalstaticintMOVE_AHEAD=1;//向左
privatefinalstaticintMOVE_ABOVE=2;//向上
//AIX正方形问题点遍历时优先前进的方向常量定义
publicfinalstaticintFIRST_MOVE_AHEAD=101;//先从左至右,后从下向上
publicfinalstaticintFIRST_MOVE_ABOVE=102;//先从下向上,后从左至右
privateintmoveUnit;//当前算法处理的单位长度
privateintnPart;//矩形边被等分的份数
privateintfirstMoveWay;//正方形问题线路优先前进方向
privateintnAccess;//正确的通路总数
privatePointstartP;
privatePointendP;
privateStringstrPath;
privateVectorvisitedPoint;//遍历过程中已经访问过的点队列(每找到一条通道后被清空,然后重新加载)
privateStackvisitStack;//遍历过程中的堆栈
privateVectorrightAccess;//能到达目标点的正确通路队列
//算法访问的当前点
privateAixPointp;
privatevoidvisitPoint()
...{
if(strPath==null||strPath=="")
strPath="Path"+(nAccess+1)+":"+p;
else
strPath+="-"+p;
}
//判断是否向左前进越界
privatebooleanisAheadExcess()
...{
return(p.x>endP.x);
}
//判断是否向上前进越界
privatebooleanisAboveExcess()
...{
return(p.y>endP.y);
}
//将当前轮的遍历结果点组成的遍历线路存储于rightAccess中
privatevoidsaveArriveLine()
...{
Stringstr="",strAccess="";
for(inti=0;ivisitedPoint.size();i++)
...{
AixPointq=(AixPoint)visitedPoint.get(i);
str=(str==null||str=="")?" Path"+(nAccess+1)+":":"-";
strAccess+=str+q;
}
rightAccess.add(strAccess);
}
//判断是否前进到目标点
privatebooleanisArriveAim()
...{
booleanisOK=false;
isOK=((p.x==endP.x)&&(p.y==endP.y)
&&(p.aheadExcess&&p.aboveExcess));
if(isOK)
...{
saveArriveLine();
nAccess++;
strPath="";
}
returnisOK;
}
//遍历的当前点进栈
privatevoidpushPoint()
...{
visitStack.push(p);
}
//遍历的当前点退栈
privatevoidpopPoint()
...{
if(!visitStack.empty())
...{
p=(AixPoint)visitStack.pop();
}
}
//修改遍历堆栈中,参数指定的点的越界标志
privatevoidsetVisitStackExcess(AixPointpara,intflag)
...{
for(inti=0;ivisitStack.size();i++)
...{
AixPointq=(AixPoint)visitStack.get(i);
if(para==q)
...{
switch(flag)
...{
caseMOVE_AHEAD:
q.aheadExcess=true;
break;
caseMOVE_ABOVE:
q.aboveExcess=true;
break;
}
}
}
}
//遍历的当前点进入队列
privatevoidenterList()
...{
visitedPoint.add(p);
}
//遍历的当前点退出队列(将当前点在遍历队列中删除)
privatevoidexitList()
...{
visitedPoint.remove(p);
}
//修改遍历的当前点队列中,参数指定的点的越界标志
privatevoidsetVisitedListExcess(AixPointpara,intflag)
...{
for(inti=0;ivisitedPoint.size();i++)
...{
AixPointq=(AixPoint)visitedPoint.get(i);
if(para==q)
...{
switch(flag)
...{
caseMOVE_AHEAD:
q.aheadExcess=true;
break;
caseMOVE_ABOVE:
q.aboveExcess=true;
break;
}
}
}
}
//判断当前点是否已经在曾经访问过的队列中
privatebooleanisVisited()
...{
booleanisExist=false;
for(inti=0;ivisitedPoint.size();i++)
...{
if(p==(AixPoint)visitedPoint.get(i))
...{
isExist=true;
break;
}
}
returnisExist;
}
//AIX正方形问题的"尝试前进"方法
privatevoidattempt(intflag)
...{
AixPointq=newAixPoint(p);
p=q;
switch(flag)
...{
caseMOVE_AHEAD:
//向左移动
p.goAhead();//[向前尝试]
break;
caseMOVE_ABOVE:
//向上移动
p.goAbove();//[向上尝试]
}
}
//AIX正方形问题的"回溯后退"方法
privatevoidbackdate(intflag)
...{
popPoint();//[向后/向下回溯]
pushPoint();
setVisitedListExcess(p,flag);
setVisitStackExcess(p,flag);
}
//新版:goAlwaysLeft()方法
protectedvoidgoAlwaysLeftNew()
...{
if(!isVisited())
...{
pushPoint();
enterList();
visitPoint();
}
attempt(MOVE_AHEAD);
if(isAheadExcess())
backdate(MOVE_AHEAD);
}
//新版:goAlwaysUpper()方法
protectedvoidgoAlwaysUpperNew()
...{
if(!isVisited())
...{
pushPoint();
enterList();
visitPoint();
}
attempt(MOVE_ABOVE);
if(isAboveExcess())
backdate(MOVE_ABOVE);
}
//成功找到一条通道后,回退到下一个正确的新起点方法
privatevoidbackdateNewStartPoint()
...{
while((p.aheadExcess&&p.aboveExcess))
...{
if(p.x==startP.x&&p.y==startP.y)
break;
popPoint();
if((p.x==endP.x)&&(p.y==endP.y))
continue;
if(p.aheadExcess&&!p.aboveExcess)
p.aboveExcess=true;
if(!p.aheadExcess&&p.aboveExcess)
p.aheadExcess=true;
if((!p.aheadExcess&&!p.aboveExcess))
...{
if((firstMoveWay==FIRST_MOVE_AHEAD)&&(p.xstartP.x))
...{
p.aheadExcess=true;
if(p.y>=endP.y)
p.aboveExcess=true;
}
if((firstMoveWay==FIRST_MOVE_ABOVE)&&(p.yendP.y))
...{
p.aboveExcess=true;
if(p.x>=endP.x)
p.aheadExcess=true;
}
}
}
switch(firstMoveWay)
...{
caseFIRST_MOVE_AHEAD:
p.aheadExcess=true;
break;
caseFIRST_MOVE_ABOVE:
p.aboveExcess=true;
break;
}
pushPoint();
}
//成功找到一条通道后,从正确的新起点开始,将堆栈中所有的点转存入遍历队列
privatevoidTransStackToNewList()
...{
visitedPoint.clear();
for(inti=0;ivisitStack.size();i++)
visitedPoint.add(visitStack.get(i));
}
//正方形问题的沿当前线路前进的核心算法
privatebooleanadvanceMoveKernel()
...{
switch(firstMoveWay)
...{
caseFIRST_MOVE_AHEAD:
if(p.aheadExcess)
goAlwaysLeftNew();
else
goAlwaysUpperNew();
break;
caseFIRST_MOVE_ABOVE:
if(p.aboveExcess)
goAlwaysUpperNew();
else
goAlwaysLeftNew();
break;
}
returnisArriveAim();
}
//类构造器
publicAixSquare()
...{
visitStack=newStack();
visitedPoint=newVector();
rightAccess=newVector();
startP=newPoint();
endP=newPoint();
moveUnit=1;
nAccess=0;
strPath="";
}
//类构造器
publicvoidsetProblemCondition(intpart,intfirstMove)
...{
this.firstMoveWay=firstMove;
if(part0)
part=1;
this.nPart=part;
endP.x=nPart;
endP.y=nPart;
nAccess=0;
strPath="";
visitStack.clear();
visitedPoint.clear();
rightAccess.clear();
}
//新版:正方形问题解答方法
publicvoidsolveProblemNew()
...{
booleanarriveAim=false;
p=newAixPoint(startP);
while(!p.aheadExcess||!p.aboveExcess)
...{
while(!p.aheadExcess||!p.aboveExcess)
...{
switch(firstMoveWay)
...{
caseFIRST_MOVE_AHEAD:
if(!p.aheadExcess)
goAlwaysLeftNew();
else
goAlwaysUpperNew();
break;
caseFIRST_MOVE_ABOVE:
if(!p.aboveExcess)
goAlwaysUpperNew();
else
goAlwaysLeftNew();
break;
}
arriveAim=isArriveAim();
if(arriveAim)
break;
}
backdateNewStartPoint();
TransStackToNewList();
if(visitStack.isEmpty()&&(p.x==startP.x&&p.y==startP.y))
break;
}
}
//类的处理结果输出串
publicStringtoString()
...{
Stringstr=" n="+nPart;
for(inti=0;irightAccess.size();i++)
...{
str+=rightAccess.get(i);
}
str+=" Total="+nAccess;
returnstr;
}
}
AixContest源码:
/***//*******************************************************************************
*>
*AIXContestver1.0
*开发作者:成晓旭
*项目简述:AIX程序设计的Java程序设计"AIX正方形问题"解决方案
*启动时间:2004年01月14日20:00:00
*完成时间:2003年01月14日23:16:00
*
*开发环境:Windows2000Professional+SUNJ2SE1.4.2
*开发工具:RationalRose2002Enterprise+JCreator2.5Pro
*
*文件名称:AixContest.java
*简介:正方形问题的客户调用处理类,抽象正方形问题的应用层
*
*备注:
*
*修改时间1:
*
*[问题描述]:
*任意给定一个正方形,将正方形的各边做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
*
*[解答思路]:
*此问题的核心是一个"有向无环图"的遍历问题,
*解答的思想就是一个"试探"与"回溯"算法的抽象与实现.甚至比完整的
*"有向无环图"的遍历问题还要简单.
*
*[建模提示]:
*为了简化问题的处理过程,强调解决问题的实质性思路,在建模过程中,
*对遍历过程中每步"前进"的步长进行了"固定步长为1"的假设,即对将被
*n等分的正方形的边长,自动设置为n,以简化算法中对边的计算处理.
*
*[算法优化]:
*目前设计的算法有以下几处有待优化:
*1:此题是一般的"试探"与"回溯"算法一个特例,所以有些处理过程是可以省略的
*(目前实现的是一个标准的"试探"与"回溯"算法)
*2:由于题目自身的特殊性,对某些处理过程可做简化,以提高算法的执行效率
*(如:对进栈,出栈的处理,对访问队列的处理,对在正方形边上"前进"时的
*回溯处理,对临界条件,到达目标点条件的判断等等)
*3:问题的本身及解答此题的思路是很具一般性的,但目前分析,设计的类结构过于特殊化.
******************************************************************************/
packageCXXSoft.Aix;
importjava.awt.Point;
importCXXSoft.Aix.AixSquare;
publicclassAixContest
...{
publicstaticvoidmain(String[]arg)
...{
System.out.println("AIX知识大赛初赛Java程序设计---AIX正方形问题");
AixSquareasProblem=newAixSquare();
Stringstr="";
for(inti=1;i3;i++)
...{
asProblem.setProblemCondition(i,AixSquare.FIRST_MOVE_AHEAD);
asProblem.solveProblemNew();
str+=asProblem+" ";
}
System.out.println(str);
System.out.println(" AIX正方形问题---运行结束......");
}
}
Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=1108610
分享到:
相关推荐
aix_nmon--用于监控aix系统中的各项资源使用情况
通过qemu-system-ppc程序能在X86平台安装运行 此资源为AIX7.1版本 cd1和cd2 AIX_7.1_Base_Operating_System_TL_7100-03-00_DVD_1_of_2_112013.iso AIX_7.1_Base_Operating_System_TL_7100-03-00_DVD_2_of_2_112013....
AIX 技术资料-AIX 技术资料-AIX 技术资料-AIX 技术资料-AIX 技术资料-AIX 技术资料-AIX 技术资料-AIX 技术资料-AIX 技术资料-AIX 技术资料-AIX 技术资料-AIX 技术资料-
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 JDK1.8 JRE1.8 IBM官网下载的安装包 jdk 和jre都有 64位,由于官网下载太慢,这里另存一份,需要的同学自取
aix宝典---命令、LVM、设备管理等
AIX视频教程1-smit AIX视频教程1-smit AIX视频教程1-smit
AIX学习笔记---系统管理和网络管理等
AIX上vg--pv-filesystem基础.doc
AIX维护大全--为解决日常维护,因此收集到该文档
AIX命令介绍篇-find-命令实例讲解.doc
参考:china.emc.... 环境:2台 aix5.3-08-05 &2台 aix6.1-01-02 这些机器通过fc与cx300连接,能正常使用,能正产识别。 通过tcpip与EMC CX4-120连接。没有配置chap AIX新版本中都是自带Initiator
AIX 手册1-18 10英文 AIX 手册1-18 10英文
aix篇-cpu-men-io性能观察.part1.ra
aix篇-cpu-men-io性能观察.part2.rar
unix-linux-aix-hp unix-Solaris命令手册-大全-史上最齐收集
AIX-IO-Perf-ohvcmg 硬盘检测