- 浏览: 7674 次
- 性别:
- 来自: 上海
最新评论
-
王书兴:
似乎有问题吧 ,字符串中的数字是按顺序取的,并没有进行排列啊
带条件的排列组合算法分析 -
yangguo:
<div class="quote_title ...
带条件的排列组合算法分析 -
shuishou119800:
re:3 楼 ilove2009
不可否 ...
用桥梁模式实现螺旋矩阵算法 -
ilove2009:
面向对象的代码很少有if else这样的语句,一般都是用多态 ...
用桥梁模式实现螺旋矩阵算法 -
shuishou119800:
re 1 楼 ilove2009
能说的具体些吗?你觉 ...
用桥梁模式实现螺旋矩阵算法
算法说明:
在屏幕上打印如下结果:
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--; }
将以上分析中的代码片段整合便得到了该题的完整算法逻辑
矩阵题的一般解题思路类似于此,希望对大家有所帮助。
评论
你的代码我看了,想法很好,想通过“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”接口定义一套新的实现。
哈哈,你說的我覺得不是問題,这个也是我预料到的.因为我的算法是出了边界和重复的就按指定的方向掉头,如果起始点是四个角并且方向是对的就没有问题.这个只是具体的实现问题而已,整个设计来说还是相对灵活的.
我已经新写了一篇关于螺旋矩阵算法的桥梁模式改造http://shuishou119800.iteye.com/blog/550862,欢迎一起探讨
你的代码我看了,想法很好,想通过“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”接口定义一套新的实现。
呵呵,这倒是真的,就像一个手表,你如果只是想改变下它指针的位置,只要拨到想要的位置就可以了,可如果你要想让它的指针逆时针旋转就只能修改其内部结构啦。可无论是逆时针还是顺时针,它的工作原理是一样的,只要你知道了顺时针时的工作原理,改造个逆时针走的手表也就不是什么难事了。
个人觉得对于算法题,关键是要找出问题背后的原理,在抽象的层面思考问题,这样才能达到举一反三,触类旁通的目的。
不过针对ilove2009说的问题,这里笔者给出自己的改进思路:将状态机的流转条件和边界条件分离,使用桥梁模式[Bridge]实现两者的脱耦,使得二者可以独立地变化
其实不管面向对象还是面向过程的编程,都能达到目的。但对维护来说是不一样的,这就是为什么面向对象产生的原因。
期待看到你应用“桥梁模式”的新实现
呵呵,这倒是真的,就像一个手表,你如果只是想改变下它指针的位置,只要拨到想要的位置就可以了,可如果你要想让它的指针逆时针旋转就只能修改其内部结构啦。可无论是逆时针还是顺时针,它的工作原理是一样的,只要你知道了顺时针时的工作原理,改造个逆时针走的手表也就不是什么难事了。
个人觉得对于算法题,关键是要找出问题背后的原理,在抽象的层面思考问题,这样才能达到举一反三,触类旁通的目的。
不过针对ilove2009说的问题,这里笔者给出自己的改进思路:将状态机的流转条件和边界条件分离,使用桥梁模式[Bridge]实现两者的脱耦,使得二者可以独立地变化
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(); } }
ilove2009 说的不错,笔者写代码时并未考虑其弹性,如果要实现从05开始旋转必须要修改状态机的启动位置和周期的结束位置。
启动位置需改为:int row=0,col=len-1
周期的结束位置判断条件需改为:if(row==min&&col+1==max)
考虑对代码的改进:如果要矩阵可以正常内螺旋则起始位置只能是矩阵的某一角,这样对于顺时针内螺旋矩阵只能有四个可能的起始点,因而可以考虑给calculate方法加上个“起始位置标识”参数,在方法中根据这个参数动态地决定“状态机的启动位置和周期的结束位置”
其实笔者写这个算法主要的意图是提供一种通过状态机原理解决矩阵问题的思路,从上面的修改可以看出,只要"顺时针内螺旋"这个核心没变,状态机的流转机制就不会发生变化,变化的只是边界条件
哈哈,如果用户提出不想顺时针回旋了,现在要逆时针回旋。估计楼主要疯掉啦。
ilove2009 说的不错,笔者写代码时并未考虑其弹性,如果要实现从05开始旋转必须要修改状态机的启动位置和周期的结束位置。
启动位置需改为:int row=0,col=len-1
周期的结束位置判断条件需改为:if(row==min&&col+1==max)
考虑对代码的改进:如果要矩阵可以正常内螺旋则起始位置只能是矩阵的某一角,这样对于顺时针内螺旋矩阵只能有四个可能的起始点,因而可以考虑给calculate方法加上个“起始位置标识”参数,在方法中根据这个参数动态地决定“状态机的启动位置和周期的结束位置”
其实笔者写这个算法主要的意图是提供一种通过状态机原理解决矩阵问题的思路,从上面的修改可以看出,只要"顺时针内螺旋"这个核心没变,状态机的流转机制就不会发生变化,变化的只是边界条件
试想,如果让这个程序打印:
1011121
916132
815143
7 6 54
是不是要修改你的代码?
看看我的文章http://heis.iteye.com/blog/546981
相关推荐
以面向对象的思想及普通算法各写了这个算法,有源代码,可以比较两种方法的区别。这样更容易了解JAVA面向对象思想的优点与便捷。
矩阵算法题。这道题主要是类似螺旋的数字排列,从外层1旋转到最中间。 让你更加了解二维数组和矩阵的相关的应用。这里主要是一个逻辑,转过弯就容易了。想了我1天呀。很值得, 很难得,分享给大家,希望对学C的同学...
C++螺旋矩阵C++螺旋矩阵C++螺旋矩阵C++螺旋矩阵C++螺旋矩阵C++螺旋矩阵C++螺旋矩阵C++螺旋矩阵
螺旋矩阵算法对比.doc
对于奇数阶和偶数阶的外螺旋矩阵,分别找到他们的螺旋起点,即1的位置,依次向左、下、右、上执行由阶数决定的循环,对该位赋值为前一数值加1。
c++面试题,螺旋矩阵递归算法实现及动态内存分配
包括了分割法和自己想的标记算法 可以通过修改N的值,实现不同大小的矩阵的打印
有两个算法,螺旋矩阵和折线矩阵的实现,可以自己输入(n×n)矩阵的n值。
输出螺旋矩阵的VB程序,共学习VB程序设计的复杂算法编程
实现由外向内螺旋矩阵的操作 矩阵大小为M*N 实现方法为递归调用 有完整注释,看起来比较轻松
螺旋矩阵时间限制: 1000ms 内存限制: 64000kB 描述 螺旋数组: 打印方阵为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 输入 5 输出 矩阵 样例输入 5 样例...
数据结构螺旋矩阵VC6,能够进行正时针外循环螺旋矩阵。
用C语言实现了螺旋矩阵,其中n。如输入4,则会输出4*4的螺旋矩阵
主要介绍了Java实现的打印螺旋矩阵算法,结合完整实例形式详细分析了java打印螺旋矩阵的算法原理与实现技巧,需要的朋友可以参考下
打印输出螺旋矩阵,要求螺旋矩阵的阶数由用户输入
采用内螺旋算法,房间抽象为矩阵,0不可行,1可行,2为已清扫
用C语言完成螺旋矩阵,输入n,得到n行n列的四种螺旋矩阵 1. 给定N的值,从矩阵的左上角输出顺时针螺旋矩阵 例如N=4时,输出: 1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7 2.给定N的值,从矩阵的右上角输出逆时针螺旋...
提供了两种螺旋矩阵的输出方式,对于研究螺旋矩阵的网友可以作参考之用 刚学VB.NET做的
螺旋矩阵完整,用c语言实现,正,逆螺旋矩阵!