内螺旋矩阵算法分析

shuishou119800

浏览: 7886 次
性别:
来自: 上海

最近访客更多访客>>

zyh2018

418506400

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

2009-12 ( 3)
更多存档...

博客分类：

算法

算法编程设计模式 UP 工作

算法说明：

在屏幕上打印如下结果：

int i=5;

1 2 3 4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

int i=6

1 2 3 4 5 6

20 21 22 23 24 7

19 32 33 34 25 8

18 31 36 35 26 9

17 30 29 28 27 10

16 15 14 13 12 11

算法代码：

public class HelixAlgo {
  
  public void print(int len){
    if(len<=0){
      System.out.println("请输入大于0的整数！");
      return;
    }
    int[][] helix=calculate(len);
    for(int i=0;i<helix.length;i++){
      for(int j=0;j<helix[i].length;j++){
        System.out.print(helix[i][j]+"\t");
      }
      System.out.println("");
    }
  }
  
  private int[][] calculate(int len){
    int[][] helix=new int[len][len];
    int min=0,max=len-1;//行列的最大最小值
    int row=0,col=0;
    for(int i=0;i<len*len;i++){
      helix[row][col]=i+1;
      if(row==min&&col<max){
        col++;
      }else if(row<max&&col==max){
        row++;
      }else if(row==max&&col>min){
        col--;
      }else if(row>min&&col==min){
        row--;
      }
      if(row-1==min&&col==min){ //在一个周期结束时修改最大最小值
        min++;
        max--;
      }
    }
    return helix;
  }
  
  public static void main(String[] args){
    HelixAlgo algo=new HelixAlgo();
    algo.print(6);
  }
  
}

算法分析：

这是一道方阵题，根据结果矩阵的变化规律，此处不妨将其叫做"内螺旋矩阵"。

先画出该方阵的索引图（以6阶方阵为例）：

00 01 02 03 04 05 //第一位为行索引，第二位为列索引

10 11 12 13 14 15

20 21 22 23 24 25

30 31 32 33 34 35

40 41 42 43 44 45

50 51 52 53 54 55

根据题目给出的结果方阵，可画出值递增变化的流向图：

根据上面的流向图，可按流向的方向将变化过程分成4中状态：

1.列索引递增

条件：行索引为最小值，列索引未达到最大值

结果：行索引为最小值，列索引达到最大值

2.行索引递增

条件：列索引为最大值，行索引未达到最大值

结果：列索引为最大值，行索引达到最大值

3.列索引递减

条件：行索引为最大值，列索引未达到最小值

结果：行索引为最大值，列索引达到最小值

4.行索引递减

条件：列索引为最小值，行索引未达到最小值

结果：列索引为最小值，行索引达到最小值

这是一个典型的状态机：当状态的行为使状态达到其结果后，将自动满足另一个状态，即状态是自动流转的。因此在代码实现中并不需要关注状态何时结束(即状态的结果)，我们需要做的只是确认在合适的条件下进入合适的状态。

四种状态分别对应四个条件，因此在代码实现中可使用一个4分支的条件语句，由上面对各状态的条件描述不难写出这个条件语句（条件式中的变量row、col、rmin、rmax、cmin、cmax分别对应当前行索引、当前列索引、行索引最小值、行索引最大值、列索引最小值、列索引最大值，下文中也将使用这几个变量代表这些值，不再赘述）：

if(row==rmin&&col<cmax){ //列索引递增
  ...
}else if(row<rmax&&col==cmax){ //行索引递增
  ...
}else if(row==rmax&&col>cmin){ //列索引递减
  ...
}else if(row>rmin&&col==cmin){ //行索引递减
  ...
}

有了流转条件，下面我们来分析边界条件

仔细分析不难发现，该题存在两种边界条件：状态机运行的边界条件和状态机流转的边界条件

状态机运行的边界条件，即状态机启动和停止的条件

其中启动条件很容易确定，结果集的递增是从方阵的[00]位置开始，因此只需将行列索引的初始位置调整至[00]处即可：

int row=0;
int col=0;

对于不同阶数的方阵(特别是偶数阶方阵)，内螺旋矩阵的结束位置并不固定，故由结束位置来作为状态机停止的条件并不合适。分析下结果方阵可看出：无论其变化规则如何，都是要填满方阵上的各个位。换句话说：只要方阵上的各个位都被填满了，这个状态机也就完成使命了。对于n阶方阵共有n*n个索引位，因此只要完成了n*n次填位操作，即可停止状态机的运行，代码片段如下(对于矩阵题，一般使用二维数组来存储各个索引位的值)：

int[][] helix=new int[n][n];
for(int i=0;i<n*n;i++){
  ...
  helix[row][col]=索引位对应的值;
  ...
}

状态机流转的边界条件，即状态发生改变的条件，从上述的状态结果中很容易看出四个状态对应的流转边界：列索引最大值、行索引最大值、列索引最小值、行索引最小值。对于内螺旋矩阵这四个值是在不断变化的，简单分析下就能看出其变化规律：

列索引递增结束后行索引最小值增一

行索引递增结束后列索引最大值减一

列索引递减结束后行索引最大值减一

行索引递减结束后列索引最小值增一

转换成代码，即：

if(row==rmin&&col==cmax){ //列索引递增边界
  rmin++;
}else if(row==rmax&&col==cmax){ //行索引递增边界
  cmax--;
}else if(row==rmax&&col==cmin){ //列索引递减边界
  rmax--;
}else if(row==rmin&&col==cmin){ //行索引递减边界
  cmin++;
}

深入分析下这个变化规律可发现该变化的周期为螺旋的一圈(注意：螺旋的一圈是不封口的!),在一个周期内，四个边界独立变化，故可在周期结束时统一修改边界变化：

if(row-1==rmin&&col==cmin){ //再次提醒，这里所谓一个周期的结束(螺旋的一圈)是不封口的！
  rmin++;
  cmax--;
  rmax--;
  cmin++;
}

周期结束后，行列索引的最大值均减一，最小值均加一，故可考虑将四个变量简化成两个变量max,min分别代表行列索引的最大值和最小值:

if(row-1==min&&col==min){
  min++;
  max--;
}

将以上分析中的代码片段整合便得到了该题的完整算法逻辑

矩阵题的一般解题思路类似于此，希望对大家有所帮助。

查看图片附件

分享到：

带条件的排列组合算法分析

2009-12-16 12:39
浏览 4484
评论(13)
分类:编程语言
查看更多

13 楼 ilove2009 2009-12-17

我没有给出逆时针的实现是因为我可通过扩展来达到增加功能的目的,也就是所谓的灵活.但可户说要逆时针的我是增加字类来实现,而你是重新写算法.

12 楼 ilove2009 2009-12-17

shuishou119800 写道

re:7 楼 ilove2009
你的代码我看了，想法很好，想通过“dirct.isOut(tempNext)||containsPoint(tempNext)”来实现从任一点的流转。
但笔者认为这并不可行，你可以将“new Point(1,1,"1") ”中的初始坐标换成其他的试试，很多输出都是有问题的，这里以“int size = 5;new Point(4,1,"1") ”为例，输出的结果为：
14    15    16     1     2
13    22    23    24     3
12    21    18    25     4
11    20    19           5
10     9     8     7     6
当走到16的时候碰到了碰到了1，于是调头向下，走到19调头向左，走到20调头向上，走到22问题来了，“dirct.isOut(tempNext)|| containsPoint(tempNext)”判断到他前方已经有值了（即15），符合条件于是进了if，执行了“dirct = dirct.next(next);next = dirct.nextPoint(next);”其中“dirct = dirct.next(next)”使走向调头向右，“next = dirct.nextPoint(next)”使其毫无判断地向右走了一格，于是原本的17就被23替换了，造成了上面的输出。对于内螺旋来说如果不从拐角处出发是很容易出现走进死胡同的现象的，就像这里的22，走到它时，它的前后左右都已经有值了，后面除非覆盖某个值，否则无法继续。
另外你“Direction”的实现类中的“next()”方法已经把下一个方向定死了，那也就只能做顺时针流转了，仍然没有实现逆时针流转，除非再给“Direction”接口定义一套新的实现。

哈哈，你說的我覺得不是問題，这个也是我预料到的.因为我的算法是出了边界和重复的就按指定的方向掉头,如果起始点是四个角并且方向是对的就没有问题.这个只是具体的实现问题而已,整个设计来说还是相对灵活的.

11 楼 shuishou119800 2009-12-17

re:9 楼 ilove2009
我已经新写了一篇关于螺旋矩阵算法的桥梁模式改造http://shuishou119800.iteye.com/blog/550862，欢迎一起探讨

10 楼 shuishou119800 2009-12-17

9 楼 ilove2009 2009-12-17

shuishou119800 写道

re: 6 楼 ilove2009

呵呵，这倒是真的，就像一个手表，你如果只是想改变下它指针的位置，只要拨到想要的位置就可以了，可如果你要想让它的指针逆时针旋转就只能修改其内部结构啦。可无论是逆时针还是顺时针，它的工作原理是一样的，只要你知道了顺时针时的工作原理，改造个逆时针走的手表也就不是什么难事了。
个人觉得对于算法题，关键是要找出问题背后的原理，在抽象的层面思考问题，这样才能达到举一反三，触类旁通的目的。

不过针对ilove2009说的问题，这里笔者给出自己的改进思路：将状态机的流转条件和边界条件分离，使用桥梁模式[Bridge]实现两者的脱耦，使得二者可以独立地变化

其实不管面向对象还是面向过程的编程，都能达到目的。但对维护来说是不一样的，这就是为什么面向对象产生的原因。

期待看到你应用“桥梁模式”的新实现

8 楼 shuishou119800 2009-12-17

7 楼 ilove2009 2009-12-17

公布一下我的实现，大家讨论一下。不同实现有那些优缺点。比如用户不想顺时针、也不想逆时针回旋了，而是：
1 2 3 4 5
109 8 7 6
1112131415
。。。。。
我实现的方法可以通过继承Direction实现，同时也起到保护大部分的代码不被修改的目的。

import java.util.HashMap;
import java.util.Map;

class Point {
	private int x;
	private int y;
	private String val;
	public Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
	public Point(int x, int y, String val) {
		this(x, y);
		this.val = val;
	}
	public int getX() {
		return x;
	}
	public void setX(int x) {
		this.x = x;
	}
	public int getY() {
		return y;
	}
	public void setY(int y) {
		this.y = y;
	}
	public String getVal() {
		return val;
	}
	public void setVal(String val) {
		this.val = val;
	}
}

abstract class Direction {
	int size;
	abstract public Point nextPoint(Point p);// 下个点
	abstract public Direction next(Point point);// 下一个方向
	abstract public boolean isOut(Point point);// 是否在本方向上出界

}

class Right extends Direction {
	public Right(int size) {
		this.size = size;
	}
	public Direction next(Point point) {
		return new Down(size);
	}
	public Point nextPoint(Point p) {
		return new Point(p.getX() + 1, p.getY());
	}
	public boolean isOut(Point point) {
		return point.getX() > size;
	}
}

class Down extends Direction {

	public Down(int size) {
		this.size = size;
	}
	public Direction next(Point point) {
		return new Left(size);
	}
	public Point nextPoint(Point p) {
		return new Point(p.getX(), p.getY() + 1);
	}
	public boolean isOut(Point point) {
		
//		if(point.getX() == size && point.getY() % 2 == 1) {
//			return true;
//		}
//		if(point.getX() == 1 && point.getY() % 2 == 0) {
//			return true;
//		}
//		return false;
		
		return point.getY() > size;
	}
}

class Left extends Direction {
	public Left(int size) {
		this.size = size;
	}
	public Direction next(Point point) {
		return new Up(size);
//		return new Down(size);
	}
	public Point nextPoint(Point p) {
		return new Point(p.getX() - 1, p.getY());
	}
	public boolean isOut(Point point) {
		return point.getX() < 1;
	}
}

class Up extends Direction {
	public Up(int size) {
		this.size = size;
	}
	public Direction next(Point point) {
		return new Right(size);
	}
	public Point nextPoint(Point p) {
		return new Point(p.getX(), p.getY() - 1);
	}
	public boolean isOut(Point point) {
		return point.getY() < 1;
	}
}

public class Snake {

	int size;
	Direction dirct;
	Point startPoint;
	Map<String, Point> map = new HashMap<String, Point>();// 记录走过的点
	public Snake(int size,Direction startDirection,Point startPoint) {
		this.size = size;
		this.dirct = startDirection;
		this.startPoint = startPoint;
		map.put(key(startPoint.getX(),startPoint.getY()), startPoint);
	}
	public void run() {
		Point next = startPoint;
		for (int i = 2; i < size * size + 1; i++) {
			Point tempNext = dirct.nextPoint(next);
			// 如果在一个方向上出界或者已经走过的点要掉头
			if (dirct.isOut(tempNext)
					|| containsPoint(tempNext)) {
				dirct = dirct.next(next);
				next = dirct.nextPoint(next);
			} else {
				next = tempNext;
			}
			next.setVal(String.valueOf(i));
			map.put(key(next.getX(), next.getY()), next);// 记录走过的点
		}
	}
	
	private boolean containsPoint(Point next) {
		return map.containsKey(key(next.getX(),next.getY()));
	}
	// 生成key
	private String key(int x, int y) {
		String xVal = "000000" + x;
		String yVal = "000000" + y;
		return xVal.substring(xVal.length() - 3)
				+ yVal.substring(yVal.length() - 3);
	}
	public void print() {
		for (int y = 1; y < size + 1; y++) {
			for (int x = 1; x < size + 1; x++) {
				String temp = "      " + (map.containsKey(key(x,y)) ? map.get(key(x, y)).getVal() : "");
				System.out.print(temp.substring(temp.length() - 6));
			}
			System.out.println("");
		}
	}
	public static void main(String[] args) {
		int size = 20;
		/**
		 * 使用场景:告诉snake，起始方向、起始点、范围，snake就知道怎么做啦
		 */
		Snake sn = new Snake(size,new Right(size),new Point(1,1,"1"));
		sn.run();
		sn.print();
	}
}

6 楼 ilove2009 2009-12-17

shuishou119800 写道

re:4 楼 ilove2009

ilove2009 说的不错，笔者写代码时并未考虑其弹性，如果要实现从05开始旋转必须要修改状态机的启动位置和周期的结束位置。
启动位置需改为：int row=0,col=len-1
周期的结束位置判断条件需改为：if(row==min&&col+1==max)

考虑对代码的改进：如果要矩阵可以正常内螺旋则起始位置只能是矩阵的某一角，这样对于顺时针内螺旋矩阵只能有四个可能的起始点，因而可以考虑给calculate方法加上个“起始位置标识”参数，在方法中根据这个参数动态地决定“状态机的启动位置和周期的结束位置”

其实笔者写这个算法主要的意图是提供一种通过状态机原理解决矩阵问题的思路，从上面的修改可以看出，只要"顺时针内螺旋"这个核心没变，状态机的流转机制就不会发生变化，变化的只是边界条件

哈哈，如果用户提出不想顺时针回旋了，现在要逆时针回旋。估计楼主要疯掉啦。

5 楼 shuishou119800 2009-12-17

4 楼 ilove2009 2009-12-17

对于过程化的编程来说，这是非常好的算法。但对于java来说不是很好的编程思维，我们用java是为了更好的应用面向对象思想。结果我们很多人都用面向对象的语言写面向过程的代码。面向对象比面向过程的优点是灵活。
试想，如果让这个程序打印：
       1011121
       916132
       815143
       7 6 54

是不是要修改你的代码？

3 楼 mwei 2009-12-16

代码简短，还好理解，不错

2 楼 Heis 2009-12-16

我的算法与你有些不同,虽然矩阵都分解为圈来解决,但是没有设置边界判断,而是直接计算出圈的边长.这样当矩阵边长很大的时候,就省下了很多的边界判断的操作.
看看我的文章http://heis.iteye.com/blog/546981

1 楼 ilove2009 2009-12-16

感觉不够灵活，当开始点是从05那里开始旋转能不能实现？

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论