AIX编程挑战赛：AIX正方形问题的算法解析与Java代码实现

作者：三号天宫 | 来源：互联网 | 2024-11-06 16:47

在昨晚的阅读中，我注意到了CSDN博主西部阿呆-小草屋发表的一篇文章《AIX程序设计大赛——AIX正方形问题》。该文详细阐述了AIX正方形问题的背景，并提供了一种基于Java语言的解决方案。本文将深入解析这一算法的核心思想，并展示具体的Java代码实现，旨在为参赛者和编程爱好者提供有价值的参考。

昨天晚上&＃xff0c;看到CSDN上西部阿呆-小草屋的一篇Blog 《AIX 程序设计大赛---AIX正方形问题》&＃xff0c;描述了Aix正方形问题&＃xff0c;并给出了Java解决方法&＃xff0c;感觉这道题很有趣味和手痒&＃xff0c;所以也花了将近一个晚上的时间&＃xff0c;用有别于小草屋的思路通过Java程序进行了解决。

由于有很长时间没有接触数学方面的知识了&＃xff0c;所以解法上或概念上有什么不对/或不当之处&＃xff0c;请对该题也感兴趣的朋友多多指教&＃xff0c;希望通过共同探讨找到一个优秀的解决方案。

问题描述&＃xff1a;

任意给定一个正方形&＃xff0c;将正方形的各边做n等分,并将相应各点连接成水平或垂直的直线,如果从正方形的左下角(0,0)出发,沿各边线或连接线,自左向右或自下而上的方向,到达正方形的右上角(n,n),请用JAVA程序计算并输出所有可能的路径总数和具体线路.请提供相关JAVA源程序和n&＃61;2,3,4时的输出结果。输出结果按以下方式:

以n&＃61;1为例:

n &＃61; 1

Path1: (0,0) - (0,1) - (1,1)

Path2: (0,0) - (1,0) - (1,1)

Total &＃61; 2

解决思路&＃xff1a;

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

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

顶极点&＃xff1a;在到达终点point&＃xff08;n&＃xff0c;n&＃xff09;之前最后一个拐点&＃xff0c;根据这个点是在正方形的上边还是右边&＃xff0c;我们分为两种类型&＃xff1a;

第一种&＃xff1a;顶极点是正方形上边上的点&＃xff0c;称作为“上边点”

第二种&＃xff1a;顶极点是正方形右边上的点&＃xff0c;称作为“右边点”

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

突破点&＃xff1a;下一条路径沿着上一条路径&＃xff0c;所走出的第一个不同点。

通过分析发现突破点和顶极点之间的关系如下&＃xff1a;

我们设定顶极点为&＃xff1a;tipPolePoint&＃xff08;&＃xff58;&＃xff0c;&＃xff59;&＃xff09;&＃xff0c;突破点为breakPoint&＃xff08;&＃xff58;&＃xff0c;&＃xff59;&＃xff09;

第一种&＃xff1a;若顶极点为上边点&＃xff0c;则按照向上优先策略&＃xff0c;突破点为

breakPoint.x &＃61; tipPolePoint.x&＃43;1

breakPoint.y &＃61; tipPolePoint.y-1

第二种&＃xff1a;若顶极点为右边点&＃xff0c;则按照向上优先策略&＃xff0c;突破点为

breakPoint.x &＃61; (min(x)|y&＃61;tipPolePoint.y)&＃43;1 &＃xff08;不知道这种表示形式对不对&＃xff09;意思是路径节点中y&＃61;tipPolePoint.y的最小 x 值加 1

breakPoint.y &＃61; tipPolePoint.y-1

算法特点

由于该算法是通过找到路径之间的关系&＃xff0c;通过上一条路径直接推导出下一条路径&＃xff0c;所以无需采用递归算法&＃xff0c;因此在一定程度上免去了探索回溯的性能开销。

程序设计&＃xff1a;

根据以上分析&＃xff0c;进行Java程序设计&＃xff0c;包括三个类&＃xff0c;分别简述如下&＃xff1a;

Point&＃xff1a;基础类&＃xff0c;表示坐标点&＃xff1b;

AixUtil&＃xff1a;工具类&＃xff0c;按照向上优先策略&＃xff0c;提供解决AIX正方形问题的一些静态方法&＃xff1b;

AixClient&＃xff1a;一个简单的调用类&＃xff0c;通过工具类AixUtil方法&＃xff0c;遍历一个正方形的所有路径。

源程序代码如下&＃xff1a;

Point&＃xff1a;基础类&＃xff0c;表示坐标点&＃xff1b;

package qinysong.aix;

/**
*

Title: 基础类&＃xff0c;表示坐标点

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

Company: qinysong

* &＃64;author zhaoqingsong
* &＃64;version 1.0 $Date: 2006/09/05 21:44:36 $
*/

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

  /**
   * 构造函数
   * &＃64;param x int
   * &＃64;param y int
   */
  public Point(int x, int y){
    this.x &＃61; x;
    this.y &＃61; y;
  }

  public String toString(){
    return "(" &＃43; x &＃43; "," &＃43; y &＃43; ")";
  }

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

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

}

AixUtil&＃xff1a;工具类&＃xff0c;按照向上优先策略&＃xff0c;提供解决AIX正方形问题的一些静态方法&＃xff1b;

package qinysong.aix;

/**
*

Title: 工具类&＃xff0c;按照向上优先策略&＃xff0c;提供解决AIX正方形问题的一些静态方法

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

Company: qinysong

* &＃64;author zhaoqingsong
* &＃64;version 1.0 $Date: 2006/09/05 21:52:18 $
*/

public class AixUtil {

  private static int nValue;

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

  /**
   *

取得上一条路径的顶极点

*
*

顶极点&＃xff1a;在到达最后顶点point&＃xff08;n&＃xff0c;n&＃xff09;之前的最后一个拐点&＃xff0c;即第一个到达上边或右边的点

   * 根据是到达的上边还是右边&＃xff0c;顶极点分为两种类型

   * 第一种&＃xff1a;顶极点是正方形上边上的点&＃xff0c;定义为“上边点”

   * 第二种&＃xff1a;顶极点是正方形右边上的点&＃xff0c;定义为“右边点”

   *
   * &＃64;param previousPathPoints Point[] 上一条路径节点数组
   * &＃64;return Point  tipPolePoint顶极点
   */
  public static Point getTipPolePoint(Point[] previousPathPoints) {
    Point tipPolePoint &＃61; null;
    int lastIndex &＃61; 2*nValue;
    if (previousPathPoints[lastIndex - 1].y &＃61;&＃61; previousPathPoints[lastIndex].y) { //取得上边点
      for (int i &＃61; lastIndex; i > 0; i--) {
        if (previousPathPoints[i - 1].y !&＃61; previousPathPoints[i].y) {
          tipPolePoint &＃61; previousPathPoints[i];
          break;
        }
      }
    } else { //取得右边点
      for (int i &＃61; lastIndex; i > 0; i--) {
        if (previousPathPoints[i - 1].x !&＃61; previousPathPoints[i].x) {
          tipPolePoint &＃61; previousPathPoints[i];
          break;
        }
      }
    }
    return tipPolePoint;
  }

  /**
   *

取得下一条路径的突破点&＃xff0c;返回的突破点定义为breakPoint

   * 分两种情况:

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

   * breakPoint.x &＃61; tipPolePoint.x&＃43;1

   * breakPoint.y &＃61; tipPolePoint.y-1

*
*

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

* breakPoint.x &＃61; (min(x)|y&＃61;tipPolePoint.y)&＃43;1 即路径节点中y&＃61;tipPolePoint.y的最小 x 值加 1

* breakPoint.y &＃61; tipPolePoint.y-1

   *
   * &＃64;param previousPathPoints Point[]  路径节点数组,表示上一条路径的节点序列
   * &＃64;param tipPolePoint Point 顶极点,表示上一条路径的顶级点
   * &＃64;return Point 返回下一条路径的突破点 breakPoint
   */
  public static Point getBreakPoint(Point[] previousPathPoints, Point tipPolePoint) {
    Point breakPoint &＃61; null;
    int arrayLength &＃61; 2*nValue&＃43;1;
    int x &＃61; 0;
    int y &＃61; 0;
    if (tipPolePoint.isTopBorderPoint(nValue)) {
      x &＃61; tipPolePoint.x &＃43; 1;
      y &＃61; tipPolePoint.y - 1;
    } else {
      Point leftPointOnLine &＃61; null;
      for (int i &＃61; arrayLength-1; i > 0; i--) {
        if (previousPathPoints[i].y > tipPolePoint.y) continue;
        if (previousPathPoints[i - 1].y !&＃61; previousPathPoints[i].y) {
          leftPointOnLine &＃61; previousPathPoints[i];
          break;
        }
      }
      x &＃61; leftPointOnLine.x &＃43; 1;
      y &＃61; leftPointOnLine.y - 1;
    }
    breakPoint &＃61; new Point(x, y);
    return breakPoint;
  }

  /**
   * 按照向上优先策略&＃xff08;即能往上走就往上走&＃xff09;&＃xff0c;取得下一个路径节点
   * &＃64;param currentPoint Point
   * &＃64;return Point 下一个路径节点
   */
  public static Point getNextPoint(Point currentPoint) {
    int x &＃61; 0;
    int y &＃61; 0;
    if (currentPoint.y < nValue) {
      x &＃61; currentPoint.x;
      y &＃61; currentPoint.y &＃43; 1;
    } else if (currentPoint.x < nValue) {
      x &＃61; currentPoint.x &＃43; 1;
      y &＃61; currentPoint.y;
    } else {
      return null;
    }
    return new Point(x, y);
  }

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

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

  /**
   *

按照向上优先策略&＃xff08;即能往上走就往上走&＃xff09;&＃xff0c;取得下一条路径节点

   * 这个函数是上面getNextPath和getFirstPath的合并&＃xff0c;用以得到整体的下一条路径

   * 如果previousPathPoints 为空&＃xff0c;则取得第一条路径

   * 如果previousPathPoints不为空&＃xff0c;则根据其取得下一条路径

   * &＃64;param previousPathPoints Point[] 上一条路径节点
   * &＃64;return Point[] 下一条路径
   */
  public static Point[] getTotalNextPath(Point[] previousPathPoints) {
    if (previousPathPoints &＃61;&＃61; null){
      return getFirstPath();
    } else {
      return getNextPath(previousPathPoints);
    }
  }

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

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

}

AixClient&＃xff1a;一个简单的调用类&＃xff0c;通过工具类AixUtil方法&＃xff0c;遍历一个正方形的所有路径。

package qinysong.aix;

/**
*

Title: 调用类,该类通过工具类AixUtil提供的方法&＃xff0c;遍历一个正方形的路径

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

Company: qinysong

* &＃64;author zhaoqingsong
* &＃64;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 &＃61; 2;
    System.out.println("当n&＃61;" &＃43; nValue);
    AixUtil.initNValue(nValue);
    Point[] pathPoints &＃61; null;
    int pathNumber &＃61; 0;
    do {
      pathPoints &＃61; AixUtil.getTotalNextPath(pathPoints);
      AixUtil.printlnPathPoints(&＃43;&＃43;pathNumber, pathPoints);
    }while (!AixUtil.isLastPath(pathPoints));
    System.out.println("Total&＃xff1a;" &＃43; pathNumber);

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

程序输出结果如下&＃xff1a;

当&＃xff4e;&＃xff1d;&＃xff12;时

AixUtil.main begin ......

当n&＃61;2

Path1&＃xff1a;(0,0)-(0,1)-(0,2)-(1,2)-(2,2)

Path2&＃xff1a;(0,0)-(0,1)-(1,1)-(1,2)-(2,2)

Path3&＃xff1a;(0,0)-(0,1)-(1,1)-(2,1)-(2,2)

Path4&＃xff1a;(0,0)-(1,0)-(1,1)-(1,2)-(2,2)

Path5&＃xff1a;(0,0)-(1,0)-(1,1)-(2,1)-(2,2)

Path6&＃xff1a;(0,0)-(1,0)-(2,0)-(2,1)-(2,2)

Total&＃xff1a;6

AixUtil.main end ......

当&＃xff4e;&＃xff1d;&＃xff13;时

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

推荐阅读

stream
解析JSON格式文本并处理数据

本文介绍如何使用阿里云的fastjson库解析包含时间戳、IP地址和参数等信息的JSON格式文本，并进行数据处理和保存。 ... [详细]

蜡笔小新 2024-12-26 16:06:09
text
使用 SQLiteJDBC 和 HikariCP 实现 Java 程序连接 SQLite 数据库

本文介绍了如何通过 Maven 依赖引入 SQLiteJDBC 和 HikariCP 包，从而在 Java 应用中高效地连接和操作 SQLite 数据库。文章提供了详细的代码示例，并解释了每个步骤的实现细节。 ... [详细]

蜡笔小新 2024-12-26 17:34:42
tree
新浪笔试题

1:有如下一段程序：packagea.b.c;publicclassTest{privatestaticinti0;publicintgetNext(){return ... [详细]

蜡笔小新 2024-12-27 19:32:17
random
Java并发编程：LinkedBlockingQueue的实际应用

本文介绍了Java并发库中的阻塞队列（BlockingQueue）及其典型应用场景。通过具体实例，展示了如何利用LinkedBlockingQueue实现线程间高效、安全的数据传递，并结合线程池和原子类优化性能。 ... [详细]

蜡笔小新 2024-12-27 18:51:49
input
XNA 3.0 游戏编程：从 XML 文件加载数据

本文介绍如何在 XNA 3.0 游戏项目中从 XML 文件加载数据。我们将探讨如何将 XML 数据序列化为二进制文件，并通过内容管道加载到游戏中。此外，还会涉及自定义类型读取器和写入器的实现。 ... [详细]

蜡笔小新 2024-12-27 11:39:44
input
深入理解Python的os和sys模块

本文详细解析了Python中的os和sys模块，介绍了它们的功能、常用方法及其在实际编程中的应用。 ... [详细]

蜡笔小新 2024-12-26 22:04:19
string
Objective-C 编程中的关键语法点

本文探讨了 Objective-C 中的一些重要语法特性，包括 goto 语句、块（block）的使用、访问修饰符以及属性管理等。通过实例代码和详细解释，帮助开发者更好地理解和应用这些特性。 ... [详细]

蜡笔小新 2024-12-26 19:42:38
php
android知识杂记（三）

andr ... [详细]

蜡笔小新 2024-12-26 13:29:32
string
Python 实现字符串双拆分并转换为矩阵

本文介绍如何使用 Python 将一个字符串按照指定的行和元素分隔符进行两次拆分，最终将字符串转换为矩阵形式。通过两种不同的方法实现这一功能：一种是使用循环与 split() 方法，另一种是利用列表推导式。 ... [详细]

蜡笔小新 2024-12-28 12:15:45
include
深入理解KMP算法中的next数组：北大OJ 2406题解

本文详细探讨了KMP算法中next数组的构建及其应用，重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现，帮助读者更好地理解KMP算法的核心原理。 ... [详细]

蜡笔小新 2024-12-28 11:30:01
text
Python 的 10 个开发技巧！太实用了

1.如何在运行状态查看源代码？查看函数的源代码，我们通常会使用IDE来完成。比如在PyCharm中，你可以Ctrl+鼠标点击进入函数的源代码。那如果没有IDE呢？当我们想使用一个函 ... [详细]

蜡笔小新 2024-12-27 18:36:54
header
使用 Azure Service Principal 和 Microsoft Graph API 获取 AAD 用户列表

本文介绍了一段通用代码示例，该代码不仅能够操作 Azure Active Directory (AAD)，还可以通过 Azure Service Principal 的授权访问和管理 Azure 订阅资源。Azure 的架构可以分为两个层级：AAD 和 Subscription。 ... [详细]

蜡笔小新 2024-12-27 16:07:12
stream
Java 序列化接口详解

本文深入探讨了 Java 中的 Serializable 接口，解释了其实现机制、用途及注意事项，帮助开发者更好地理解和使用序列化功能。 ... [详细]

蜡笔小新 2024-12-27 15:06:12
php
将Web服务部署到Tomcat

本文介绍了如何在JDeveloper 12c中创建一个Java项目，并将其打包为Web服务，然后部署到Tomcat服务器。内容涵盖从项目创建、编写Web服务代码、配置相关XML文件到最终的本地部署和验证。 ... [详细]

蜡笔小新 2024-12-27 11:48:15
text
Android LED 数字字体的应用与实现

本文介绍了一种适用于 Android 应用的 LED 数字字体（digital font），并详细描述了其在 UI 设计中的应用场景及其实现方法。这种字体常用于视频、广告倒计时等场景，能够增强视觉效果。 ... [详细]

蜡笔小新 2024-12-27 10:34:22

三号天宫

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章