螺旋矩阵通项公式O(1)算法实现
本帖最后由 陈尚涵 于 2024-2-3 10:20 编辑前言：
事情是酱的{:10_282:} 2024/1/24，我看到了@zhangjinxuan 发的这么一则帖子：https://fishc.com.cn/thread-239305-1-1.html
在之前，我是做过螺旋矩阵的题的，当时呢第一时间想到用数学，但是想了想似乎不是很简单就直接用暴力了{:10_250:}
现在看到 zhangjinxuan 的帖子，我又开始思考这个问题，但是我太弱了，当时想了0.5h才想出来{:10_277:}
btw，这个主题我托更了亿点点，各位见谅{:10_245:}
问题：
虽然 zhangjinxuan 已经发了问题，但是我再重申一遍{:10_256:}
对于N*N的矩阵，令原点为左上角为(1,1)，并使x从左向右增大，y从上向下增大
接着从原点开始，逆时针（注意这里是逆时针，有的螺旋矩阵是顺时针）绕着矩阵每次增大1（到角落拐弯）
比如，N=5的：
1 16 15 14 13
2 17 24 23 12
3 18 25 22 11
4 19 20 21 10
56789
求通项公式（即数学算法）并达到O(1)
解法：
解法说难不难，说简单不简单，对萌新来说不太好推，大犇又不屑于推
首先就是检查(x,y)地方所处的层数（转一圈为1层，初始第一层），每一层都有四个部分
但是都有一个共同点，那就是距离边缘的距离+1=层数，稍加思考就可以写出，层数(设为d)=$min(x,y,n-x+1,n-y+1)$，所以就可以写出代码了
int d = fourmin(x, y, n-x+1, n-y+1);
此外，由于min不支持4个，所以要自定义一下fourmin
int fourmin(int a, int b, int c, int d){
int abmin = min(a,b);
int cdmin = min(c,d);
return min(abmin,cdmin);
}
接下来有了层数之后，我们就要统计这层以前所有层数的数量，并设置为初始值
那么一层一层来，我们知道一层的数量=4(边长-1)
又边长=$n-2(d-1)$
所以说一层的数量应该是$4(n-2(d-1)-1)$
但是咱们要求的所有层的，所以说设求前m层，数量为$\sum\limits_{c=1}^{m}4(n-2(c-1)-1)$
简单因式分解一下就是$4(nm-m-m(m-1))$
这里我们应该求前(d-1)层，所以说就可以设初始值了，写出代码（为了方便，直接--）
d--;
int a = 4*(n*d-d-d*(d-1))+1;
d++;
这里我+1是个伏笔，为了后面的程序
这样的话，咱们就要分四种情况了，一层分上下左右，这个怎么判定？想想开头，只需要用层数判定就可以了
if (d == x){
} else if (d == n-y+1){
} else if (d == n-x+1){
} else if (d == y){
}
接着就要考虑每种情况怎么去计算，由于咱们提前+1，所以咱们每个边长只需要加边长-1就可以了，也就是$n-2(d-1)-1$
左就是0个边长，下就是1个边长，右就是2个边长，上就是3个边长
但是除了边长还需要判定剩余的一个缺失的边长，怎么判定？还是用层数！这个层数还是非常有用的，因为这里层数可以帮我们快速定位这一行的第一个
综上，写出
if (d == x){
a += y-d;
} else if (d == n-y+1){
a += (n-2*(d-1)-1)+(x-d);
} else if (d == n-x+1){
a += 2*(n-2*(d-1)-1)+(n-d+1-y);
} else if (d == y){
a += 3*(n-2*(d-1)-1)+(n-d+1-x);
}
好的，这样就完结了，来看下整个程序
#include <iostream>
using namespace std;
int fourmin(int a, int b, int c, int d){
int abmin = min(a,b);
int cdmin = min(c,d);
return min(abmin,cdmin);
}
int main(){
int x, y, n;
cin >> x >> y >> n;
int d = fourmin(x, y, n-x+1, n-y+1);
d--;
int a = 4*(n*d-d-d*(d-1))+1;
d++;
if (d == x){
a += y-d;
} else if (d == n-y+1){
a += (n-2*(d-1)-1)+(x-d);
} else if (d == n-x+1){
a += 2*(n-2*(d-1)-1)+(n-d+1-y);
} else if (d == y){
a += 3*(n-2*(d-1)-1)+(n-d+1-x);
}
cout << a;
return 0;
}
结尾
求各位大犇赐教@zhangjinxuan @liuhongrun2022 @歌者文明清理员 @一点沙 @tommyyu
（没有 人造人 好友{:10_250:} ）
对托更非常抱歉，所以撒个币吧
你的代码基本上是对的，但是有一点小错误和不够简洁的地方。
首先，自定义的`fourmin`函数中的两个返回值应该是`abmin`和`cdmin`，而不是`a`和`b`。所以应该修改为：
int fourmin(int a, int b, int c, int d){
int abmin = min(a,b);
int cdmin = min(c,d);
return min(abmin,cdmin);
}
其次，在计算每种情况下的通项时，可以将重复的部分提取出来，减少重复代码的编写。修改为：
if (d == x){
a += y-d;
} else if (d == n-y+1){
a += (n-2*(d-1)-1)+(x-d);
} else if (d == n-x+1){
a += 2*(n-2*(d-1)-1)+(n-d+1-y);
} else if (d == y){
a += 3*(n-2*(d-1)-1)+(n-d+1-x);
}
最后，在输出结果时，缺少了`<< a`。修改为：
cout << a;
改正以上问题后的完整代码如下：
#include <iostream>
using namespace std;
int fourmin(int a, int b, int c, int d){
int abmin = min(a,b);
int cdmin = min(c,d);
return min(abmin,cdmin);
}
int main(){
int x, y, n;
cin >> x >> y >> n;
int d = fourmin(x, y, n-x+1, n-y+1);
d--;
int a = 4*(n*d-d-d*(d-1))+1;
d++;
if (d == x){
a += y-d;
} else if (d == n-y+1){
a += (n-2*(d-1)-1)+(x-d);
} else if (d == n-x+1){
a += 2*(n-2*(d-1)-1)+(n-d+1-y);
} else if (d == y){
a += 3*(n-2*(d-1)-1)+(n-d+1-x);
}
cout << a;
return 0;
}
希望我的解答能够帮助到你！如果还有其他问题，请随时提问。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 FishC 发表于 2024-2-3 10:17
你的代码基本上是对的，但是有一点小错误和不够简洁的地方。
首先，自定义的`fourmin`函数中的两个返回 ...
谢谢你帮我加上了回车{:10_250:} 陈尚涵 发表于 2024-02-03 10:19
谢谢你帮我加上了回车{:10_250:}
不客气，随时为您效劳！如果您有任何其他问题，都可以随时提问哦。祝您编程愉快！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 我还没学C计划25年学，24年先学HTML{:10_256:} 太棒了 {:5_106:} 学习 哇大神.@人造人 tql%%%
{:5_104:} 不错不错，太牛啦{:5_93:}
我之前也碰到过一个类似的：https://fishc.com.cn/thread-237590-1-1.html 厉害。 太强了
太强了
好好学习 6 只是来回帖的 好 啊？
页:
[1]
2