题目要求: 所谓“螺旋方阵”,是指对任意给定的N,将1到N×N的数字从左上角第1个格子开始,按顺时针螺旋方向顺序填入N×N的方阵里。本题要求构造这样的螺旋方阵。
输入格式:输入在一行中给出一个正整数N(<10)。 输出格式:输出N×N的螺旋方阵。每行N个数字,每个数字占3位。 输入样例:
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问题分析及求解基本思路: 这道题思路比较简单,建立二维数组,只需要满足一定条件填充: ① 当到达左上角时向右递增; ② 当到达右上角时向下递增; ③ 当到达右下角时向左递增; ④ 当到达左下角时向上递增; 循环执行直至填充数组全部元素,即可达到螺旋效果。 最后输出该方阵。
重要目标实现: 目标一: 递增转向条件的实现:当输入n之后会创建一个n阶方阵(先初始化所有元素为0,方便之后判断),当达到转角时需要判断四个方向是否为0,但是如果是最外层的话,判断会越界,所以为了安全起见,在矩阵最外层加一层边界,即输入n,建立(n+1)阶的方阵,为了与原有元素初始值区别开,将边界初始值设为-1。 目标二: 循环次数目标一只是循环体,还需要确定循环次数,即循环退出条件。以5*5数组为例:
共需判断10次。其他方阵: 3阶…6次 4阶…8次 6阶…12次 … n阶…2n次 经过归纳分析得判断点个数即为行(列)数的二倍,即2n;所以循环次数 for(k=1;k<=2n;k++)
for(k=1;k<=2*n;k++){//2*n次的判断 if(s[i-1][j]!=0 && s[i][j-1]!=0 && s[i][j+1]==0){//右方遮挡下方,优先选择右方 while(s[i][j+1]==0){ j++; s[i][j]=s[i][j-1]+1; } } if(s[i-1][j]!=0 && s[i+1][j]==0 && s[i][j-1]!=0 && s[i][j+1]!=0){ while(s[i+1][j]==0){ i++; s[i][j]=s[i-1][j]+1; } } if(s[i-1][j]!=0 && s[i+1][j]!=0 && s[i][j-1]==0 && s[i][j+1]!=0){ while(s[i][j-1]==0){ j--; s[i][j]=s[i][j+1]+1; } } if(s[i-1][j]==0 && s[i+1][j]!=0 && s[i][j-1]!=0 && s[i][j+1]!=0){ while(s[i-1][j]==0){ i--; s[i][j]=s[i+1][j]+1; } } }右方遮挡下方:对于第一个元素[1][1]来说,其下方和右方均为0,填充方向为右方,但仅此一个元素会出现两个方向均为0的情况
主要算法:
输入n建立(n+1)阶方阵s[n+1][n+1]外层元素赋值为-1,内部元素赋值为0s[1][1]=1进入for循环(循环2*n次),填充数组: 1.如果左方和上方均非0且右方为0,则向右递增直至元素原值非0; 2.如果只有下方为0,则向下方递增直至元素原值非0; 3.如果只有左方为0,则向左方递增直至元素原值非0; 4.如果只有上方为0,则向上方递增直至元素原值非0;按格式输出代码:
#include<stdio.h> int main(){ int n,i,j,k; scanf("%d",&n); int s[n+2][n+2]; for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ s[i][j]=0; } } for(i=0;i<n+2;i++){ s[i][0]=-1; s[i][n+1]=-1; } for(j=1;j<n+2;j++){ s[0][j]=-1; s[n+1][j]=-1; } s[1][1]=1; i=1,j=1; for(k=1;k<=2*n;k++){ if(s[i-1][j]!=0 && s[i][j-1]!=0 && s[i][j+1]==0){ while(s[i][j+1]==0){ j++; s[i][j]=s[i][j-1]+1; } } if(s[i-1][j]!=0 && s[i+1][j]==0 && s[i][j-1]!=0 && s[i][j+1]!=0){ while(s[i+1][j]==0){ i++; s[i][j]=s[i-1][j]+1; } } if(s[i-1][j]!=0 && s[i+1][j]!=0 && s[i][j-1]==0 && s[i][j+1]!=0){ while(s[i][j-1]==0){ j--; s[i][j]=s[i][j+1]+1; } } if(s[i-1][j]==0 && s[i+1][j]!=0 && s[i][j-1]!=0 && s[i][j+1]!=0){ while(s[i-1][j]==0){ i--; s[i][j]=s[i+1][j]+1; } } } for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ if(j==n){ printf("%3d\n",s[i][j]); }else{ printf("%3d",s[i][j]); } } } return 0; }