科技行者

行者学院 转型私董会 科技行者专题报道 网红大战科技行者

知识库

知识库 安全导航

至顶网软件频道AIX 程序设计大赛---AIX正方形问题

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

  • 扫一扫
    分享文章到微信

  • 扫一扫
    关注官方公众号
    至顶头条

本文将为大家介绍AIX 程序设计大赛---AIX正方形问题。

作者:成晓旭 来源:CSDN 2008年2月27日

关键字: java 正方形 AIX

  • 评论
  • 分享微博
  • 分享邮件

在本页阅读全文(共3页)

AixSquare源码:

/*******************************************************************************
 *    <<AIX 程序设计大赛---AIX正方形问题>>
 *            AIXContest  ver1.0
 *        开发作者:    成晓旭
 *        项目简述:    AIX程序设计的Java程序设计"AIX正方形问题"解决方案
 *        启动时间:    2004年01月14日    20:28:00
 *        完成时间:    2003年01月17日  00:16:00<4个晚上>
 *
 *        开发环境:    Windows2000 Professional + SUN J2SE1.4.2
 *        开发工具:    Rational Rose2002 Enterprise + 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:问题的本身及解答此题的思路是很具一般性的,但目前分析,设计的类结构过于特殊化.
 *
 *****************************************************************************
*/

package    CXXSoft.Aix;

import java.awt.Point;
import java.util.Stack;
import java.util.Vector;
import java.util.List;
import CXXSoft.Aix.AixPoint;

public class AixSquare
{
    
//AIX正方形问题点遍历时前进方向常量定义
    private final static int MOVE_AHEAD = 1;    //向左
    private final static int MOVE_ABOVE = 2;    //向上
    
    
//AIX正方形问题点遍历时优先前进的方向常量定义
    public final static int FIRST_MOVE_AHEAD = 101;    //先从左至右,后从下向上
    public final static int FIRST_MOVE_ABOVE = 102;    //先从下向上,后从左至右
    
    
private    int    moveUnit;            //当前算法处理的单位长度
    private int nPart;                //矩形边被等分的份数
    private int firstMoveWay;        //正方形问题线路优先前进方向
    private int nAccess;            //正确的通路总数
    private Point startP;
    
private Point endP;
    
private String strPath;
    
private Vector    visitedPoint;    //遍历过程中已经访问过的点队列(每找到一条通道后被清空,然后重新加载)
    private    Stack    visitStack;        //遍历过程中的堆栈
    private Vector    rightAccess;    //能到达目标点的正确通路队列
        
    
//算法访问的当前点
    private AixPoint    p;
    
    
private void visitPoint()
    
{
        
if(strPath == null || strPath == "")
            strPath 
= "Path" + (nAccess + 1+"" + p;
        
else
            strPath 
+= " - " + p;
    }

    
    
//判断是否向左前进越界
    private boolean isAheadExcess()
    
{
        
return (p.x > endP.x);
    }

    
    
//判断是否向上前进越界
    private boolean isAboveExcess()
    
{
        
return (p.y > endP.y);
    }

    
    
//将当前轮的遍历结果点组成的遍历线路存储于rightAccess中
    private void saveArriveLine()
    
{
        String str 
= "",strAccess = "";
        
for(int i=0;i<visitedPoint.size();i++)
        
{
            AixPoint q 
= (AixPoint)visitedPoint.get(i);
            str 
= (str == null || str == ""? " Path" + (nAccess + 1+"" : " - ";
            strAccess 
+= str + q;
        }

        rightAccess.add(strAccess);
    }

    
    
//判断是否前进到目标点
    private boolean isArriveAim()
    
{
        
boolean isOK = false;
        isOK 
= ((p.x == endP.x) && (p.y == endP.y) 
              
&&(p.aheadExcess && p.aboveExcess));
        
if(isOK)
        
{
            saveArriveLine();
            nAccess
++;
            strPath 
= "";    
        }

        
return isOK;
    }

    
    
//遍历的当前点进栈
    private void pushPoint()
    
{
        visitStack.push(p);
    }

    
    
//遍历的当前点退栈
    private void popPoint()
    
{
        
if(!visitStack.empty())
        
{
            p 
= (AixPoint)visitStack.pop();
        }

    }

    
    
//修改遍历堆栈中,参数指定的点的越界标志
    private void setVisitStackExcess(AixPoint para,int flag)
    
{
        
for(int i=0;i<visitStack.size();i++)
        
{
            AixPoint q 
= (AixPoint)visitStack.get(i);
            
if(para == q)
            
{
                
switch(flag)
                
{
                    
case MOVE_AHEAD:
                        q.aheadExcess 
= true;
                        
break;
                    
case MOVE_ABOVE:
                        q.aboveExcess 
= true;
                        
break;
                }

                
            }

        }

    }

    
    
//遍历的当前点进入队列
    private void enterList()
    
{
        visitedPoint.add(p);
    }

    
    
//遍历的当前点退出队列(将当前点在遍历队列中删除)
    private void exitList()
    
{
        visitedPoint.remove(p);
    }

    
    
//修改遍历的当前点队列中,参数指定的点的越界标志
    private void setVisitedListExcess(AixPoint para,int flag)
    
{
        
for(int i=0;i<visitedPoint.size();i++)
        
{
            AixPoint q 
= (AixPoint)visitedPoint.get(i);
            
if(para == q)
            
{
                
switch(flag)
                
{
                    
case MOVE_AHEAD:
                        q.aheadExcess 
= true;
                        
break;
                    
case MOVE_ABOVE:
                        q.aboveExcess 
= true;
                        
break;
                }

            }

        }

    }

    
    
//判断当前点是否已经在曾经访问过的队列中
    private boolean isVisited()
    
{
        
boolean isExist = false;
        
for(int i=0;i<visitedPoint.size();i++)
        
{
            
if(p == (AixPoint)visitedPoint.get(i))
            
{
                isExist 
= true;
                
break;
            }

        }

        
return isExist;
    }

    
    
//AIX正方形问题的"尝试前进"方法
    private void attempt(int flag)
    
{
        AixPoint q 
= new AixPoint(p);
        p 
= q;
        
switch(flag)
        
{
            
case MOVE_AHEAD:    
                
//向左移动
                p.goAhead();    //[向前尝试]
                break;
            
case MOVE_ABOVE:
                
//向上移动
                p.goAbove();    //[向上尝试]
        }

    }

    
    
//AIX正方形问题的"回溯后退"方法
    private void backdate(int flag)
    
{
        popPoint();                
//[向后/向下回溯]
        pushPoint();
        setVisitedListExcess(p,flag);
        setVisitStackExcess(p,flag);
    }


    
//新版:goAlwaysLeft()方法
    protected void goAlwaysLeftNew()
    
{
        
        
if(!isVisited())
        
{
            pushPoint();
            enterList();
            visitPoint();
        }

        attempt(MOVE_AHEAD);
        
if(isAheadExcess())
            backdate(MOVE_AHEAD);
    }

    
    
//新版:goAlwaysUpper()方法
    protected void goAlwaysUpperNew()
    
{
        
if(!isVisited())
        
{
            pushPoint();
            enterList();
            visitPoint();
        }

        attempt(MOVE_ABOVE);
        
if(isAboveExcess())
            backdate(MOVE_ABOVE);
    }

    
    
//成功找到一条通道后,回退到下一个正确的新起点方法
    private void backdateNewStartPoint()
    
{
        
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.x <= startP.x))
                
{
                    p.aheadExcess 
= true;
                    
if(p.y >= endP.y)
                        p.aboveExcess 
= true;
                }

                
if((firstMoveWay == FIRST_MOVE_ABOVE) && (p.y <= endP.y))
                
{
                    p.aboveExcess 
= true;
                    
if(p.x >= endP.x)
                        p.aheadExcess 
= true;
                }

            }

        }

        
switch(firstMoveWay)
        
{
            
case FIRST_MOVE_AHEAD:
                p.aheadExcess 
= true;
                
break;
            
case FIRST_MOVE_ABOVE:
                p.aboveExcess 
= true;
                
break;
        }

        pushPoint();
    }

    
    
//成功找到一条通道后,从正确的新起点开始,将堆栈中所有的点转存入遍历队列
    private void TransStackToNewList()
    
{
        visitedPoint.clear();
        
for(int i = 0; i < visitStack.size();i++)
            visitedPoint.add(visitStack.get(i));
    }

    
    
//正方形问题的沿当前线路前进的核心算法
    private boolean advanceMoveKernel()
    
{
        
switch(firstMoveWay)
        
{
            
case FIRST_MOVE_AHEAD:
                
if(p.aheadExcess)
                    goAlwaysLeftNew();
                
else
                    goAlwaysUpperNew();
                
break;
            
case FIRST_MOVE_ABOVE:
                
if(p.aboveExcess)
                    goAlwaysUpperNew();
                
else
                    goAlwaysLeftNew();
                
break;    
        }

        
return isArriveAim();
    }

    
    
//类构造器
    public AixSquare()
    
{
        visitStack 
= new Stack();
        visitedPoint 
= new Vector();
        rightAccess 
= new Vector();
        startP 
= new Point();
        endP 
= new Point();
        moveUnit 
= 1;
        nAccess 
= 0;
        strPath 
= "";
    }

    
    
//类构造器
    public void setProblemCondition(int part,int firstMove)
    
{
        
this.firstMoveWay = firstMove;
        
if(part <= 0)
            part 
= 1;
        
this.nPart = part;
        endP.x 
= nPart;
        endP.y 
= nPart;
        
        nAccess 
= 0;
        strPath 
= "";
        visitStack.clear();
        visitedPoint.clear();
        rightAccess.clear();
    }

    
    
//新版:正方形问题解答方法
    public void solveProblemNew()
    
{
        
boolean arriveAim = false;
        p 
= new AixPoint(startP);
        
while(!p.aheadExcess || !p.aboveExcess)
        
{
            
while(!p.aheadExcess || !p.aboveExcess)
            
{
                
switch(firstMoveWay)
                
{
                    
case FIRST_MOVE_AHEAD:
                        
if(!p.aheadExcess)
                            goAlwaysLeftNew();
                        
else
                            goAlwaysUpperNew();
                        
break;
                    
case FIRST_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;
        }

    }

    
    
//类的处理结果输出串
    public String toString()
    
{
        String str
=" n = " + nPart;
        
for(int i=0;i<rightAccess.size();i++)
        
{
            str 
+= rightAccess.get(i);
        }

        str 
+= " Total = " + nAccess;
        
return str;
    }

}
    • 评论
    • 分享微博
    • 分享邮件
    邮件订阅

    如果您非常迫切的想了解IT领域最新产品与技术信息,那么订阅至顶网技术邮件将是您的最佳途径之一。

    重磅专题
    往期文章
    最新文章