`
happmaoo
  • 浏览: 4335423 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

AIX 程序设计大赛---AIX正方形问题

AIX算法IBM 
阅读更多
<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;
}

/
分享到：
| IDEA数据加密算法介绍
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

Magicbox
Global site tag (gtag.js) - Google Analytics