热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

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

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

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

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 <&#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正方形问题


 * 

Copyright: Copyright (c) 2006


 * 

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   ......



  
推荐阅读
  • HBase Java API 进阶:过滤器详解与应用实例
    本文详细探讨了HBase 1.2.6版本中Java API的高级应用,重点介绍了过滤器的使用方法和实际案例。首先,文章对几种常见的HBase过滤器进行了概述,包括列前缀过滤器(ColumnPrefixFilter)和时间戳过滤器(TimestampsFilter)。此外,还详细讲解了分页过滤器(PageFilter)的实现原理及其在大数据查询中的应用场景。通过具体的代码示例,读者可以更好地理解和掌握这些过滤器的使用技巧,从而提高数据处理的效率和灵活性。 ... [详细]
  • 本文详细探讨了Zebra路由软件中的线程机制及其实际应用。通过对Zebra线程模型的深入分析,揭示了其在高效处理网络路由任务中的关键作用。文章还介绍了线程同步与通信机制,以及如何通过优化线程管理提升系统性能。此外,结合具体应用场景,展示了Zebra线程机制在复杂网络环境下的优势和灵活性。 ... [详细]
  • 本文探讨了基于点集估算图像区域的Alpha形状算法在Python中的应用。通过改进传统的Delaunay三角剖分方法,该算法能够生成更加灵活和精确的形状轮廓,避免了单纯使用Delaunay三角剖分时可能出现的过大三角形问题。这种“模糊Delaunay三角剖分”技术不仅提高了形状的准确性,还增强了对复杂图像区域的适应能力。 ... [详细]
  • Java中处理NullPointerException:getStackTrace()方法详解与实例代码 ... [详细]
  • 本文介绍了如何在iOS平台上使用GLSL着色器将YV12格式的视频帧数据转换为RGB格式,并展示了转换后的图像效果。通过详细的技术实现步骤和代码示例,读者可以轻松掌握这一过程,适用于需要进行视频处理的应用开发。 ... [详细]
  • 本文介绍了UUID(通用唯一标识符)的概念及其在JavaScript中生成Java兼容UUID的代码实现与优化技巧。UUID是一个128位的唯一标识符,广泛应用于分布式系统中以确保唯一性。文章详细探讨了如何利用JavaScript生成符合Java标准的UUID,并提供了多种优化方法,以提高生成效率和兼容性。 ... [详细]
  • 本文深入探讨了CGLIB BeanCopier在Bean对象复制中的应用及其优化技巧。相较于Spring的BeanUtils和Apache的BeanUtils,CGLIB BeanCopier在性能上具有显著优势。通过详细分析其内部机制和使用场景,本文提供了多种优化方法,帮助开发者在实际项目中更高效地利用这一工具。此外,文章还讨论了CGLIB BeanCopier在复杂对象结构和大规模数据处理中的表现,为读者提供了实用的参考和建议。 ... [详细]
  • 如何使用R语言高效连接并操作MySQL数据库
    如何使用R语言高效连接并操作MySQL数据库 ... [详细]
  • 在JavaScript中,定位属性是理解元素布局的关键。本文通过详细的图示解析,介绍了这些属性的基础概念。以`clientHeight`为例,它表示元素的可见内容区域高度,不包括边距(margin)、边框(border)和滚动条。同样,`clientWidth`则表示元素的可见内容区域宽度。这些属性对于精确控制页面元素的尺寸和位置至关重要。 ... [详细]
  • 本文深入解析了Java 8并发编程中的`AtomicInteger`类,详细探讨了其源码实现和应用场景。`AtomicInteger`通过硬件级别的原子操作,确保了整型变量在多线程环境下的安全性和高效性,避免了传统加锁方式带来的性能开销。文章不仅剖析了`AtomicInteger`的内部机制,还结合实际案例展示了其在并发编程中的优势和使用技巧。 ... [详细]
  • JavaScript XML操作实用工具类:XmlUtilsJS技巧与应用 ... [详细]
  • 在前文探讨了Spring如何为特定的bean选择合适的通知器后,本文将进一步深入分析Spring AOP框架中代理对象的生成机制。具体而言,我们将详细解析如何通过代理技术将通知器(Advisor)中包含的通知(Advice)应用到目标bean上,以实现切面编程的核心功能。 ... [详细]
  • 在Python中,是否可以通过使用Tkinter或ttk库创建一个具有自动换行功能的多行标签,并使其宽度能够随着父容器的变化而动态调整?例如,在调整NotePad窗口宽度时,实现类似记事本的自动换行效果。这种功能在设计需要显示长文本的对话框时非常有用,确保文本内容能够完整且美观地展示。 ... [详细]
  • 利用 Spring BeanUtils 实现 JavaBean 的深度克隆与属性复制 ... [详细]
  • Java 模式原型在游戏服务器架构中的应用与优化 ... [详细]
author-avatar
三号天宫
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有