螺旋数组算法[中篇]--常规数学分析

从农夫三拳的分析开始

在农夫三拳的博文里，我们可以看见一个神奇的公式

f(n) = 4*n^2 - 2*n + 1

当我们把起点1放到螺旋中心后，从内圈开始作为第一圈，如下图，3，13，31，57… 形成了一个符合上述规律的数列。

有兴趣的园友可以进一步利用相同的联立方程求解更多有趣的公式

例如我们选取1，7，21，43，73，111…

设f(x)=an^2+bn+c

得

a+b+c=1

4a+2b+c=7

9a+3b+c=21

解得a,b,c=4,-2,3

x=4*n^2-2*n+3， 经检验，能完美计算这个数列。

资料：常规数列分析

等差数列

1，2，3，4，5，6，....，n，n+1

特点：前后项差值相等，可以简单用循环变量获得。

 

反向等差数列

n+1,n,n-1,n-2, ..., 6,5,4,3,2,1

如果发现反向等差数列，那么用两个逆向等差数列之和去减其中一个就能得到另一个

例如 数列A=1，2，3，4，5，6  数列B=6，5，4，3，2，1

则数列A=7-数列B

具体到我们这个螺旋数组，其实只要用N平方去减获得的值，就能轻松实现起点1在螺旋中心还是外围。也就是说，内旋或外旋算法本质是一样的。

 

等比数列

1，2，4，8，16....n,2*n,4*n...

特点：前后项比例关系一定

1 2^0

2 2^1

4 2^2

8 2^3

观察2的指数，又变回到等差数列了

另外，简单倍数好处理，有时候需要变通

1，1.5, 2.25, 3.375, 5.0625, 7.59375....

呵呵，前后项是1：1.5

其实就是1*1.5^n n=1,2,3,4,5....

 

二次数列

农夫三拳就是发现了二次数列的秘密，那么有什么办法能发现某个数列是二次数列呢？我也不是很清楚，不过有一个模糊的感觉

如有数列A，求该数列的前后项差，形成数列B

如果数列B是一个等差数列，则数列A很有可能就是二次数列

 

例如

1，3，13，31，57，91...

计算前后差，获得数列

2，10，18，26，34...

明显看出该数列是公差为8的等差数列

（希望科班出身的兄弟帮忙推演一下，最好能获得充分的数学论证。鄙人当年高数是勉强过关的，如今心里那个悔啊，呜呜....）

Chinese_xu猜想，自变量在整数范围内，任何二次函数f(x)=ax^2+bx+c 的值形成的数列，计算其前后数据项得到的新数列为等差数列。

 

如果这个猜想为真，那么农夫三拳就可以不要凭直觉去发现二次函数公式了。大家都能有趁手的分析方法了。

在此先谢过各位。

 

心得：数学是很重要的

从小到大，到学计算机，老鸟们一直教育新手：数学是很重要的

不过没栽过跟头不过有刻骨的记忆。

没见过实例不会有深刻的印象。

没学过、没学好，不丢脸，看不起数学，丢脸。

虽然通过摸索一样可以独创微积分原理，但是有巨人的肩膀不去靠，实在是浪费。

各位和我一样数学基础不怎么样的同仁请每天少泡半小时视频网站，少半小时魔兽，几年后大学数学还是能补得上来的。

 

我以前的另一个分析

说老半天人家的东西，终于开始说说我自己的货色。

 

设计思想

由于直接模拟算法的方式是先有1，2，3，4...的数列，然后根据数值计算出对应的X，Y坐标，进行赋值。这导致了对目标数组的访问是非线性的，在数组尺寸较大时会有性能问题。

再说，我有时候会用极端方式去重构代码，No if，No loop。

不逼自己改变，人都是很懒的。

 

主体思路和农夫三拳是一样的，用X，Y坐标值，努力确定一个参考点的值，然后根据坐标偏移和螺旋数组规律计算并直接获得对应X，Y坐标处的数据值。

这么一来，我们可以按传统方式遍历目标数组，并逐一赋值。

 

约定术语：

以边长分别为10和11的螺旋矩阵为例，约定一些基本术语用于后续讨论。

圈数

一个矩阵从外到内可以分成很多圈，约定从1开始，依次从内到外编号。

0起点值

第一圈是从1开始，不过为了讨论方便约定起点之前的一个值为0起点值。例如，边长为10的螺旋矩阵，第一圈的0起点值是96，第二圈的0起点值是84。而边长为11的第一圈的0起点值是120，而第二圈的0起点值是112。

基础算法模块

所谓基础算法模块就是在完成整体任务过程中要用到的一些可以分离的步骤。

 

按螺旋矩阵边长N，以及X、Y坐标确定圈数

如图，当螺旋矩阵边长N=11的时候。行列的对称坐标位置是（5，5）

X=0，10，是第六圈

X=1，9，可能是第五圈

X=2，8，可能是第四圈

X=3，7，可能是第三圈

X=4，6，可能是第二圈

X=5，可能是第一圈

然后考虑偶数边长情况

X=0，9，都是第五圈

X=1，8，可能是第四圈

X=2，7，可能是第三圈

X=3，6，可能是第二圈

X=4，5，可能是第一圈

由此，综合判断，抽象后得到算法如下

按给定(X,Y)，给定边长记作N

圈数I=ABS((N-1)/2.0-X)+(N%2+1)*0.5

圈数II=ABS((N-1)/2.0-Y)+(N%2+1)*0.5

两个结果中较大的一个是所求圈数

 

进一步可以得到指定圈数对应的最大和最小坐标值

坐标数小=(N-1)/2.0-圈数+(N%2+1)*0.5)

坐标数大=(N-1)/2.0+圈数-(N%2+1)*0.5)

 

上面这些公式都是奇数和偶数数组通用的，里面使用了模运算以达到这个效果。

 

已知边长，求指定圈数的0起点值

这个很好解释，其实就是减掉中间的一个平方数就可以了。

已知边长N，求指定圈数R的0起点值

0起点值=N*N-(2R-N%2)*(2R-N%2)

 

最后整合

已知边长、圈数和坐标，求实际数值

1。按坐标秋圈数

2。计算起点值

3。计算本圈的最大最小坐标

4。根据给定坐标值和最大最小坐标，判断在哪个边上

5。计算最终值

 

实际代码 

public int GetMatrixValue(int N, Point p)

{

int value=0;

int circleNumber,circleNumberX,circleNumberY;

int zeroStart;

int min, max;

//Get circle number

circleNumberX =(int) (Math.Abs((N - 1) / 2.0 - p.X) + (N % 2 + 1) * 0.5);

circleNumberY = (int)(Math.Abs((N - 1) / 2.0 - p.Y) + (N % 2 + 1) * 0.5);

circleNumber = Math.Max(circleNumberX, circleNumberY);

 

//Get zero start number

zeroStart = N * N - (2 * circleNumber - N % 2) * (2 * circleNumber - N % 2);

//Get min X and min Y

min = (N - 1) / 2 - circleNumber + 1;

max = min + circleNumber * 2 - N % 2-1;

//Get line number

if (p.X < max && p.Y == min) { value = zeroStart + p.X - min+1; }

if (p.X == max && p.Y < max) { value = zeroStart + circleNumber * 2 - N % 2 + p.Y - min; }

if (p.X <= max && p.Y == max) { value = zeroStart + 2 * (circleNumber * 2 - N % 2) - 1 + max - p.X; }

if (p.X == min && p.Y > min) { value = zeroStart + 3 * (circleNumber * 2 - N % 2) - 2 + max - p.Y; }

return value;

}

点评

优点

实现了按输入的X，Y坐标计算得到对应值，对目标数组可以进行简单的循环即可。

缺点

说实话，看着最后那4个IF我还是不爽。极限追求，No IF，No Loop。

 

感悟，以及对面试官的肺腑之言

什么是算法？排序？查找？树遍历？图路径搜索？

什么是设计模式？世界上只有23种设计模式？

 

我们都学过不少东西，学校考试的时候，必须按照标准答案往空格上填，往答题卡上描！

可是，世界上有更多东西是没有标准答案的。99.99%的程序设计题，都可以有多种答案，哪怕这个题有多简单。

不同的解决方案，对应不同的思路，不同的思考侧重点。

如果只是招一个码工，那么我多言了。

想招一个程序员，让他做笔试题也是可以的，也是应该的。

不过，评价标准不应该是他写出来的是不是和面试官自己写的(甚至是抄的)答案一致。而是面对问题的解决思路、应变、细节，乃至对自己代码的阐述。

为什么很多HR说难招人？

我感觉可能是很多HR认为“常识”的试题，却是多数埋头工作的人不一定能立刻完美回答得上来。尤其是编程笔试题。

 

螺旋数组终极算法

好了，马上就要公布我的终极算法了，其实核心已经写好了，计划明天将矩阵转换的部分都搞定后再发，估计在12/23。

No If，No Loop

据路边社消息：完成如上的GetMatrixValue，函数内可执行代码只有5行，当然，硬要嵌成一行也是可以的，而上面的函数，里面的可执行代码要嵌成一行就太勉强了。

 

导读：

螺旋数组算法[上篇]--直接模拟算法

螺旋数组算法[中篇]--常规数学分析

螺旋数组算法[下篇]--努力接近需求的本质 预计12/23日发布