昨天晚上，看到CSDN上西部阿呆-小草屋的一篇Blog 《AIX 程序设计大赛---AIX正方形问题》，描述了Aix正方形问题，并给出了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

解决思路：

通过对上述问题的分析，有一条约束很关键，就是“沿各边线或连接线,自左向右或自下而上的方向,到达正方形的右上角”，根据该约束我们找到一个探寻路径的策略（或称作规则）：向上优先策略，即在探寻一条路径的时候，只要能够向上走，我们就向上走，也就是只在最后一步才向右拐。这样按照这个策略，我们就可以从第一条路径（沿着左边和上边），逐条遍历所有路径。

确定按照向上优先策略遍历路径后，分析发现，在这个探寻路径的过程中，有一个点非常重要，我在这里称作“顶极点”，定义如下：

顶极点：在到达终点point（n，n）之前最后一个拐点，根据这个点是在正方形的上边还是右边，我们分为两种类型：

第一种：顶极点是正方形上边上的点，称作为“上边点”

第二种：顶极点是正方形右边上的点，称作为“右边点”

按照向上优先策略，通过上一条路径的顶极点可以唯一确定下一条路径的突破点，突破点定义如下：

突破点：下一条路径沿着上一条路径，所走出的第一个不同点。

通过分析发现突破点和顶极点之间的关系如下：

我们设定顶极点为：tipPolePoint（ｘ，ｙ），突破点为breakPoint（ｘ，ｙ）

第一种：若顶极点为上边点，则按照向上优先策略，突破点为

breakPoint.x = tipPolePoint.x+1

breakPoint.y = tipPolePoint.y-1

第二种：若顶极点为右边点，则按照向上优先策略，突破点为

breakPoint.x = (min(x)|y=tipPolePoint.y)+1 （不知道这种表示形式对不对）意思是路径节点中y=tipPolePoint.y的最小 x 值加 1

breakPoint.y = tipPolePoint.y-1

程序设计：

根据以上分析，进行Java程序设计，包括三个类，分别简述如下：

Point：基础类，表示坐标点；

AixUtil：工具类，按照向上优先策略，提供解决AIX正方形问题的一些静态方法；

AixClient：一个简单的调用类，通过工具类AixUtil方法，遍历一个正方形的所有路径。

源程序代码如下：

Point：基础类，表示坐标点；

package qinysong.aix;

/**
* Title: 基础类，表示坐标点
* Description: AIX 程序设计大赛---AIX正方形问题
* Copyright: Copyright (c) 2006
* Company: qinysong
* @author zhaoqingsong
* @version 1.0 $Date: 2006/09/05 21:44:36 $
*/

public class Point {
 protected int x;
 protected int y;

 /**
 * 构造函数
 * @param x int
 * @param y int
 */
 public Point(int x, int y){
 this.x = x;
 this.y = y;
 }

 public String toString(){
 return "(" + x + "," + y + ")";
 }

 /**
 * 判断是否为上边点
 * @return boolean
 */
 public boolean isTopBorderPoint(int nValue){
 return this.y == nValue;
 }

 /**
 * 判断thePoint是否与自己相等
 * @param thePoint Point
 * @return boolean
 */
 public boolean equals(Point thePoint){
 return (this.x == thePoint.x) && (this.y == thePoint.y);
 }

}

AixUtil：工具类，按照向上优先策略，提供解决AIX正方形问题的一些静态方法；

package qinysong.aix;

/**
* Title: 工具类，按照向上优先策略，提供解决AIX正方形问题的一些静态方法
* Description: AIX 程序设计大赛---AIX正方形问题
* Copyright: Copyright (c) 2006
* Company: qinysong
* @author zhaoqingsong
* @version 1.0 $Date: 2006/09/05 21:52:18 $
*/

public class AixUtil {

 private static int nValue;

 /**
 * 初始化正方形边长
 * @param nValue int
 */
 public static void initNValue(int nValue) {
 if (nValue <= 0) {
 throw new RuntimeException("初始化正方形边长异常，长度不能小于等于零");
 }
 AixUtil.nValue = nValue;
 }

 /**
 * 取得上一条路径的顶极点
 *
 * 顶极点：在到达最后顶点point（n，n）之前的最后一个拐点，即第一个到达上边或右边的点 
 * 根据是到达的上边还是右边，顶极点分为两种类型 
 * 第一种：顶极点是正方形上边上的点，定义为“上边点” 
 * 第二种：顶极点是正方形右边上的点，定义为“右边点”
 *
 * @param previousPathPoints Point[] 上一条路径节点数组
 * @return Point tipPolePoint顶极点
 */
 public static Point getTipPolePoint(Point[] previousPathPoints) {
 Point tipPolePoint = null;
 int lastIndex = 2*nValue;
 if (previousPathPoints[lastIndex - 1].y == previousPathPoints[lastIndex].y) { //取得上边点
 for (int i = lastIndex; i > 0; i--) {
 if (previousPathPoints[i - 1].y != previousPathPoints[i].y) {
 tipPolePoint = previousPathPoints[i];
 break;
 }
 }
 } else { //取得右边点
 for (int i = lastIndex; i > 0; i--) {
 if (previousPathPoints[i - 1].x != previousPathPoints[i].x) {
 tipPolePoint = previousPathPoints[i];
 break;
 }
 }
 }
 return tipPolePoint;
 }

 /**
 * 取得下一条路径的突破点，返回的突破点定义为breakPoint 
 * 分两种情况: 
 * 第一种:若顶极点为上边点,则按照向上优先策略,突破点为 
 * breakPoint.x = tipPolePoint.x+1 
 * breakPoint.y = tipPolePoint.y-1
 *
 * 第二种:若顶极点为右边点,则按照向上优先策略,突破点为 
 * breakPoint.x = (min(x)|y=tipPolePoint.y)+1 即路径节点中y=tipPolePoint.y的最小 x 值加 1 
 * breakPoint.y = tipPolePoint.y-1
 *
 * @param previousPathPoints Point[] 路径节点数组,表示上一条路径的节点序列
 * @param tipPolePoint Point 顶极点,表示上一条路径的顶级点
 * @return Point 返回下一条路径的突破点 breakPoint
 */
 public static Point getBreakPoint(Point[] previousPathPoints, Point tipPolePoint) {
 Point breakPoint = null;
 int arrayLength = 2*nValue+1;
 int x = 0;
 int y = 0;
 if (tipPolePoint.isTopBorderPoint(nValue)) {
 x = tipPolePoint.x + 1;
 y = tipPolePoint.y - 1;
 } else {
 Point leftPointOnLine = null;
 for (int i = arrayLength-1; i > 0; i--) {
 if (previousPathPoints[i].y > tipPolePoint.y) continue;
 if (previousPathPoints[i - 1].y != previousPathPoints[i].y) {
 leftPointOnLine = previousPathPoints[i];
 break;
 }
 }
 x = leftPointOnLine.x + 1;
 y = leftPointOnLine.y - 1;
 }
 breakPoint = new Point(x, y);
 return breakPoint;
 }

 /**
 * 按照向上优先策略（即能往上走就往上走），取得下一个路径节点
 * @param currentPoint Point
 * @return Point 下一个路径节点
 */
 public static Point getNextPoint(Point currentPoint) {
 int x = 0;
 int y = 0;
 if (currentPoint.y < nValue) {
 x = currentPoint.x;
 y = currentPoint.y + 1;
 } else if (currentPoint.x < nValue) {
 x = currentPoint.x + 1;
 y = currentPoint.y;
 } else {
 return null;
 }
 return new Point(x, y);
 }

 /**
 * 按照向上优先策略（即能往上走就往上走），取得下一条路径节点
 * @param previousPathPoints Point[] 上一条路径节点
 * @return Point[] 下一条路径
 */
 public static Point[] getNextPath(Point[] previousPathPoints) {
 int arrayLength = 2*nValue+1;
 Point tipPolePoint = getTipPolePoint(previousPathPoints);
 Point breakPoint = getBreakPoint(previousPathPoints, tipPolePoint);
 Point lastKeepPoint = new Point(breakPoint.x - 1, breakPoint.y);
 Point[] nextPath = new Point[arrayLength];
 int index = 0;
 for (; index < arrayLength; index++) {
 nextPath[index] = previousPathPoints[index];
 if (previousPathPoints[index].equals(lastKeepPoint)) {
 break;
 }
 }
 nextPath[++index] = breakPoint;
 Point tempPoint = breakPoint;
 while ( (tempPoint = getNextPoint(tempPoint)) != null) {
 nextPath[++index] = tempPoint;
 }
 return nextPath;
 }

 /**
 * 按照向上优先策略，取得第一条路径
 * @return Point[]
 */
 public static Point[] getFirstPath() {
 Point[] firstPath = new Point[2*nValue+1];
 for (int i = 0; i <= nValue; i++) {
 firstPath[i] = new Point(0, i);
 }
 for (int i = 1; i <= nValue; i++) {
 firstPath[nValue + i] = new Point(i, nValue);
 }
 return firstPath;
 }

 /**
 * 按照向上优先策略（即能往上走就往上走），取得下一条路径节点 
 * 这个函数是上面getNextPath和getFirstPath的合并，用以得到整体的下一条路径 
 * 如果previousPathPoints 为空，则取得第一条路径 
 * 如果previousPathPoints不为空，则根据其取得下一条路径
 * @param previousPathPoints Point[] 上一条路径节点
 * @return Point[] 下一条路径
 */
 public static Point[] getTotalNextPath(Point[] previousPathPoints) {
 if (previousPathPoints == null){
 return getFirstPath();
 } else {
 return getNextPath(previousPathPoints);
 }
 }

 /**
 * 判断是否是最后一条路径
 * @param pathPoints Point[]
 * @return boolean
 */
 public static boolean isLastPath(Point[] pathPoints){
 int middleIndex = nValue;
 return pathPoints[middleIndex].y == 0;
 }

 /**
 * 按照题目要求格式打印一条路径的节点
 * @param pathNumber int
 * @param pathPoints Point[]
 */
 public static void printlnPathPoints(int pathNumber, Point[] pathPoints) {
 StringBuffer pathStringBuffer = new StringBuffer();
 pathStringBuffer.append("Path" + pathNumber + "：");
 int arrayLength = 2*nValue+1;
 for (int i = 0; i < arrayLength; i++) {
 pathStringBuffer.append(pathPoints[i].toString() + "-");
 }
 String pathString = pathStringBuffer.toString();
 if (pathString.length()>0) pathString = pathString.substring(0,pathString.length()-1);
 System.out.println(pathString);
 }

}

AixClient：一个简单的调用类，通过工具类AixUtil方法，遍历一个正方形的所有路径。

package qinysong.aix;

/**
* Title: 调用类,该类通过工具类AixUtil提供的方法，遍历一个正方形的路径
* Description: AIX 程序设计大赛---AIX正方形问题
* Copyright: Copyright (c) 2006
* Company: qinysong
* @author zhaoqingsong
* @version 1.0 $Date: 2006/09/05 22:49:22 $
*/

public class AixClient {

 public static void main(String[] args) {
 System.out.println("AixUtil.main begin ......");
 int nValue = 2;
 System.out.println("当n=" + nValue);
 AixUtil.initNValue(nValue);
 Point[] pathPoints = null;
 int pathNumber = 0;
 do {
 pathPoints = AixUtil.getTotalNextPath(pathPoints);
 AixUtil.printlnPathPoints(++pathNumber, pathPoints);
 }while (!AixUtil.isLastPath(pathPoints));
 System.out.println("Total：" + pathNumber);

 System.out.println("AixUtil.main end ......");
 }
}

程序输出结果如下：

当ｎ＝２时

AixUtil.main begin ......

当n=2

Path1：(0,0)-(0,1)-(0,2)-(1,2)-(2,2)

Path2：(0,0)-(0,1)-(1,1)-(1,2)-(2,2)

Path3：(0,0)-(0,1)-(1,1)-(2,1)-(2,2)

Path4：(0,0)-(1,0)-(1,1)-(1,2)-(2,2)

Path5：(0,0)-(1,0)-(1,1)-(2,1)-(2,2)

Path6：(0,0)-(1,0)-(2,0)-(2,1)-(2,2)

Total：6

AixUtil.main end ......

当ｎ＝３时

AixUtil.main begin ......
当n=3
Path1：(0,0)-(0,1)-(0,2)-(0,3)-(1,3)-(2,3)-(3,3)
Path2：(0,0)-(0,1)-(0,2)-(1,2)-(1,3)-(2,3)-(3,3)
Path3：(0,0)-(0,1)-(0,2)-(1,2)-(2,2)-(2,3)-(3,3)
Path4：(0,0)-(0,1)-(0,2)-(1,2)-(2,2)-(3,2)-(3,3)
Path5：(0,0)-(0,1)-(1,1)-(1,2)-(1,3)-(2,3)-(3,3)
Path6：(0,0)-(0,1)-(1,1)-(1,2)-(2,2)-(2,3)-(3,3)
Path7：(0,0)-(0,1)-(1,1)-(1,2)-(2,2)-(3,2)-(3,3)
Path8：(0,0)-(0,1)-(1,1)-(2,1)-(2,2)-(2,3)-(3,3)
Path9：(0,0)-(0,1)-(1,1)-(2,1)-(2,2)-(3,2)-(3,3)
Path10：(0,0)-(0,1)-(1,1)-(2,1)-(3,1)-(3,2)-(3,3)
Path11：(0,0)-(1,0)-(1,1)-(1,2)-(1,3)-(2,3)-(3,3)
Path12：(0,0)-(1,0)-(1,1)-(1,2)-(2,2)-(2,3)-(3,3)
Path13：(0,0)-(1,0)-(1,1)-(1,2)-(2,2)-(3,2)-(3,3)
Path14：(0,0)-(1,0)-(1,1)-(2,1)-(2,2)-(2,3)-(3,3)
Path15：(0,0)-(1,0)-(1,1)-(2,1)-(2,2)-(3,2)-(3,3)
Path16：(0,0)-(1,0)-(1,1)-(2,1)-(3,1)-(3,2)-(3,3)
Path17：(0,0)-(1,0)-(2,0)-(2,1)-(2,2)-(2,3)-(3,3)
Path18：(0,0)-(1,0)-(2,0)-(2,1)-(2,2)-(3,2)-(3,3)
Path19：(0,0)-(1,0)-(2,0)-(2,1)-(3,1)-(3,2)-(3,3)
Path20：(0,0)-(1,0)-(2,0)-(3,0)-(3,1)-(3,2)-(3,3)
Total：20
AixUtil.main end ......

posted on 2006-09-06 14:18 qinysong 阅读(310) 评论(0) 编辑收藏所属分类: 程序算法

新用户注册刷新评论列表


只有注册用户登录后才能发表评论。




网站导航: 博客园 IT新闻 Chat2DB C++博客博问管理

2025年7月

日

一

二

三

四

五

六

留言簿

文章分类

文章档案

搜索

最新评论