牛猫大侠查看:12 回复:9 评论:12 创建时间:2021-08-04T17:23:55用户:牛猫大侠查看:12 回复:9 评论:12 创建时间:2021-08-04T17:23:55
C++ 巧解 “螺旋方阵”
原创作者：牛猫大侠 【转载请注明，谢谢！】
摘要：使用 C++ 语言编程实现对任意自然数的 n 阶螺旋方阵的自动生成及打印输出
关键词：n 阶方阵，螺旋方阵，数字方阵，二维数组，循环，算法，Online Judge
难度：高级
题目来源：https://judge.codemao.biz/problem/1153 【编程猫OJ系统
1. 方阵简介
所谓“螺旋方阵”，就本题而言，是对任意给定的 n，将 1 到 n×n 的数字从左上角第 1 个格子开始，从外到内，按顺时针螺旋方向顺序填入 n×n 的方阵里。
这类方阵在计算机图形学等学科中有着十分重要的应用。这类问题的算法分析对于计算机图形学、解析几何中的相关问题有一定的启发性。
2. 模拟填充螺旋方阵的输出是指将一些数字（从1到 n×n）按照一定的顺序输出到计算机屏幕或输出到一个指定文件中。按螺旋顺序填充的数字显然有一定的规律，而实际输出顺序却不是按照螺旋填充顺序输出，通常是将数字逐行（行列对齐）输出。
因此，这类问题的关键在于如何将有规律的数字的填充顺序与实际输出时的先后顺序对应起来。
上图是一个 8 阶螺旋方阵，我们以此为例作个简单分析：
第 1 圈 从 1 开始，到 28 结束。
//起点为左上角，从左向右填充
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
//第 1 圈 共 4×7 个数字
第 2 圈 从 29 开始，到 48 结束。
//起点为左上角，从左向右填充
29 30 31 32 33
//从右上角开始，从上向下填充
34 35 36 37 38
//从右下角开始，从右向左填充
39 40 41 42 43
//从左下角开始，从下向上填充
44 45 46 47 48
//第 2 圈 共 4×5 个数字
第 3 圈 从 49 开始，到 60 结束。
//起点为左上角，从左向右填充
49 50 51
//从右上角开始，从上向下填充
52 53 54
//从右下角开始，从右向左填充
55 56 57
//从左下角开始，从下向上填充
58 59 60
//第 3 圈 共 4×3 个数字
第 4 圈 从 61 开始，到 喵 结束。
//起点为左上角，从左向右填充
61
//从右上角开始，从上向下填充
62
//从右下角开始，从右向左填充
63
//从左下角开始，从下向上填充
喵
//第 4 圈 共 4×1 个数字
通过上面的文字，我们模拟了整个 8 阶螺旋方阵的填充方法。
那么，我们来思考一下：
每圈的数字个数有什么特点和关联？
圈数和阶数的关系是什么？
每圈的起始点有什么共同点？
思考明白这类问题，对我们下面的算法分析有极大帮助。
3. 算法分析我们来回顾下题目内容。
输入要求：输入一个正整数 n (0< n <15）
输出要求：输出一个 n 阶螺旋方阵
针对方阵这类程序设计一般是先定义一个二维数组 ，然后设计算法对此数组自动赋值。
当然，你也可以人工手动直接初始化数组并输出，但是这样的程序只能产生一个固定的方阵，显然不符合我们的要求。
我们需要的是，方阵的元素值全部由程序根据阶数自动产生。只需要输入一个整数 n (n=阶数)，就能打印输出我们需要的任何阶数的螺旋方阵。
我们以 8 阶螺旋方阵为例，进行算法分析。
//n=8，填充数字为 1-8×8，共 喵 个数字。
int n,c=1; //n为阶数；c 为填充数字，从 1 开始，到 喵 结束。
//假定 n 阶螺旋方阵为 top 圈，每圈由四边组成。
int top; //top为圈数，n=8 时，top 共 4 层；即 top = n/2 。
通过我们找到的圈数和阶数的关系，我们可以设计一个外循环来控制层数的产生：
for(top=1;top<=n/2;top++){ //外层循环
... //内部再设计每圈循环代码
... //圈数的值同时也可以对应到每圈起点坐标值（后面有图示说明）
}
首先，我们还需要创建一个二维数组，保存填充数据。
int n; //设定 n 为阶数
cin>>n;
int a[n+1][n+1]={}； //初始化二维数组，数字 1 对应 a[1][1]，习惯从 a[0][0] 开始的同学请自行修改对应代码。
那么，下一步我们如何给二维数组中的元素赋值呢？我们需要找到元素的下标（坐标）与行列的关系。
通过上节“模拟填充”，我们找到了填充规律。我们已经知道圈数与阶数的关系了，我们再来思考一下每圈数字个数有什么规律。
int k,c=1,i=1,j=1; //行 i，列 j
for(k=1;k<=4*(n-top*2+1);top++){ //思考每圈要填充的数字总数计算公式
//根据圈数、阶数、填充数字等对应关系编写内层循环
a[i][j]=c;c++; //填充数字到二维数组中
... //根据行、列、填充规律对应关系编写代码
}
接下来，我们再观察下行、列与数字填充顺序的关系。
//仔细观察上图，以第一圈为例，元素下标和数字的对应关系，详解如下：
1 2 3 4 5 6 7 //从左到右，直到右上角顶点结束
a[1][1] a[1][2] a[1][3] a[1][4] a[1][5] a[1][6] a[1][7] // i = 1，值不变；j 从 1 到 7，递增。
8 9 10 11 12 13 14 //从上到下，直到右下角顶点结束
a[1][8] a[2][8] a[3][8] a[4][8] a[5][8] a[6][8] a[7][8] // j = 8，值不变；i 从 1 到 7，递增。
15 16 17 18 19 20 21 //从右到左，直到左下角顶点结束
a[8][8] a[8][7] a[8][6] a[8][5] a[8][4] a[8][3] a[8][2] // i = 8，值不变；j 从 8 到 2，递减。
22 23 24 25 26 27 28 //从下向上，直到左上角顶点结束
a[8][1] a[7][1] a[6][1] a[5][1] a[4][1] a[3][1] a[2][1] // j = 1，值不变；i 从 8 到 2，递减。
//余下每圈类似，着重思考一下每圈四个顶点坐标与圈数、阶数的关系。
根据上面的分析，我们可以这样编写代码：
//边界定位：左或上边界 = top，右或下边界 = n-top+1
if(j==top&&i>top) i--; //从下到上，参照点：左上顶点
if(i==n-top+1&&j>top) j--; //从右到左，参照点：左下顶点
if(j==n-top+1&&i<n-top+1) i++; //从上到下，参照点：右下顶点
if(i==top&&j<n-top+1) j++; //从左到右，参照点：右上顶点
//条件判断的先后顺序影响输出结果吗？
走到这一步，已经可以编写整套代码了。通过不同输出数据测试后，发现当阶数为奇数时，我们还需要对方阵中心点（可以视为仅一个数字的特殊圈）单独赋值。
if(n%2!=0) a[n/2+1][n/2+1]=n*n; //奇数方阵中心点
根据题目输出要求，编写输出语句。
#include<iomainip> //头文件
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
cout<<setw(4)<<a[i][j];
}
cout<<endl;
}
还有一种输出方法，仅供学习。
for(i=1;i<=n;i++){4. 拓展训练
for(j=1;j<=n;j++){
printf("%4d",a[i][j]);
}
cout<<endl;
}
通过修改填充规则，我们可以定义更多的螺旋方阵。比如，修改填充方向为逆时针旋转，我们又可以得到一个不一样的螺旋方阵；通过改变起点位置，从中心向外填充，从右上角顶点开始填充，等等。还有一些非螺旋结构的数字方阵。
方阵算法一般有“海龟”、“分割”、“递归”等算法。大家有时间可以试试编写代码实现各类数字方阵的自动化输出。
欢迎大家在编程猫社区https://shequ.codemao.cn/user/8854985与作者交流。
Alcala我看得懂，但没必要这么麻烦吧
直接喵枚举x，y就行啦
复杂度O(n²)已经是最快的了
直接贴代码，毕竟太简单
#include<bits/stdc++.h>
using namespace std;
int a[1010][1010];
int main(){
int k = 1;
int n,x = 1,y = 0;
cin>>n;
while(k <= n * n){
while(y < n && !a[x][y + 1]){
y++;
a[x][y] = k;
k++;
}
while(x < n && !a[x + 1][y]){
x++;
a[x][y] = k;
k++;
}
while(y > 1 && !a[x][y - 1]){
y--;
a[x][y] = k;
k++;
}
while(x > 1 && !a[x - 1][y]){
x--;
a[x][y] = k;
k++;
}
}
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
cout<<setw(3)<<a[i][j];
}
cout<<endl;
}
}点赞0
评论
方块麦刷怪玩家
#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;
int main()
{
int n;
cin>>n;
int a[n+2][n+2];
for(int i=0; i<=n+1; i++)
{
for(int j=0; j<=n+1; j++)
{
if(i==0||i==n+1||j==0||j==n+1)
{
a[i][j]=0;
}
else
{
a[i][j]=-1;
}
}
}
int dx[4]= {0,1,0,-1};
int dy[4]= {-1,0,1,0};
int i=1,j=n;
int t=0;
for(int k=1; k<=pow(n,2); k++)
{
a[i][j]=k;
if(a[i+dx[t]][j+dy[t]]!=-1)
{
t++;
if(t%4==0)
{
t=0;
}
}
i=i+dx[t];
j=j+dy[t];
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
cout<<setw(3)<<a[i][j];
}
cout<<endl;
}
return 0;
}点赞0
评论
方块麦刷怪玩家#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;
int main()
{
int n;
cin>>n;
int a[n+2][n+2];
for(int i=0; i<=n+1; i++)
{
for(int j=0; j<=n+1; j++)
{
if(i==0||i==n+1||j==0||j==n+1)
{
a[i][j]=0;
}
else
{
a[i][j]=-1;
}
}
}
int dx[4]= {0,1,0,-1};
int dy[4]= {1,0,-1,0};
int i=1,j=1;
int t=0;
for(int k=1; k<=pow(n,2); k++)
{
a[i][j]=k;
if(a[i+dx[t]][j+dy[t]]!=-1)
{
t++;
if(t%4==0)
{
t=0;
}
}
i=i+dx[t];
j=j+dy[t];
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
cout<<setw(3)<<a[i][j];
}
cout<<endl;
}
ret点赞0
评论
