终于用海龟算法将这个题解出来了。非常感谢徐大哥,希望以后能继续像徐大哥学习更多的关于算法数据结构以及设计模式的相关知识和经验,另外也非常开心能够加入他的团队,也希望他能尽快实现自己梦想。
当我看到这道题时还真的有点不知所措,虽然把基本的想到了但还不知道如何去实现。我和宿舍的另一个一起研究,他在C++里用海龟算法实现了,借助这个思想我又在Flash里实现了,遗憾的是我用的双For输出,所以没有实现一个一个数字出现的效果,是直接全部出现的。而徐大哥当时写的程序是用EnterFrame里用If语句去实现的,所以效果能实现一个一个蹦出数字,但思想上其实都是一样的。
代码部分:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | var N:Number = 10; var arr:Array = new Array(); function init() { //X,Y 轴文本框间距 var cardSpaceX:Number = 42; var cardSpaceY:Number = 42; var offsetX:Number = 18; var offsetY:Number = 18; //循环做二维数组 for(var i:uint=0;i<N;i++) { arr[i] = new Array(); for(var j:uint=0;j<N;j++) { arr[i][j] = new MC(); arr[i][j].x = j*cardSpaceX +offsetX; arr[i][j].y = i*cardSpaceY + offsetY; addChild(arr[i][j]); } } } init(); var A:Number = 0; var B:Number = 1; var C:Number; //c代表行,V代表列 var c:Number = 0; var v:Number = -1; //当前数字 var nowStep:Number = 1; //循环判断转向 for(var i:Number = 2*(N-1)+1;i>=1;i--) { trace("i="+i); for(var j:Number=0;j<i/2;j++) { trace("j="+j); //为数组添加值 arr[c+A][v+B].Value.text = String(nowStep); trace("["+(c+A)+"]"+"["+(v+B)+"]"+"="+nowStep); nowStep++; c+=A; v+=B; } //转向变换 C=A; A=B; B=-C; trace("右转"); } |
在以4为例的输出结果中,就可以将算法的执行看的很清晰了。
i=7
j=0
[0][0]=1
j=1
[0][1]=2
j=2
[0][2]=3
j=3
[0][3]=4
右转
i=6
j=0
[1][3]=5
j=1
[2][3]=6
j=2
[3][3]=7
右转
i=5
j=0
[3][2]=8
j=1
[3][1]=9
j=2
[3][0]=10
右转
i=4
j=0
[2][0]=11
j=1
[1][0]=12
右转
i=3
j=0
[1][1]=13
j=1
[1][2]=14
右转
i=2
j=0
[2][2]=15
右转
i=1
j=0
[2][1]=16
海龟算法思想:
参照海龟行走的做法,用一对变量A,B模拟海龟头的方向,根据屏幕坐标的特点,A、B的取值和“海龟头”方向有这样的关系:(0,1)表示向右;(0, -1)表示向左;(-1,0)表示向上;(1,0)表示向下;用另一对变量X,Y模拟海龟位置,“海龟”每前进一步,它的新位置即为X=X+A,Y=Y+B;要海龟向右转,就改变A、B的值,根据数学知识可以得出具体的变换公式是:C=A;A=B;B=-C。下面用自然语言对算法进行描述:让海龟先走n步,然后右转,再走n-1步,再右转,再走n-1步,再右转,再走n-2步,再右转,再走n-2步……如此类推,直到海龟前进的步数为0时停止;而每当“海龟”前进1步,就在它位置上显示一个数字,那么前进n步即重复执行“X:=X+A,Y:=Y+B”语句n次。但如何让下两个循环的重复次数都为n-1呢?解决的方法是:循环n次后,让n的值减少0.5,然后再转回执行同样的循环。扩展到显示n位数,则须留n列的位置,也就是说,海龟水平方向每次得前进n步,才有足够的位置显示大一点的数字方阵,需把Y=Y+B改成Y=Y+n*B就行了。“海龟”算法的优点是简洁清晰。














