科技行者

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

知识库

知识库 安全导航

至顶网›软件频道 ›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;
    }
}
    • 评论
    • 分享微博
    • 分享邮件
    VIP专区
    邮件订阅

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

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

    业界热点:

    北京第二十六维信息技术有限公司（至顶网）版权所有. 京ICP备15039648号-7 京ICP证161336号 京公网安备 11010802021500号