`

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

 
阅读更多
<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


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics