目录
- 题目描述
- 题解部分
- 完整代码
菜鸡蒟蒻想在博客中记录一些算法学习的心得体会,会持续更新c/c++方面的题解,方便理清思路和日后复习。如果还能结识一起敲代码的小伙伴的话就更好啦嘿嘿,因为实在是太弱了,肯定免不了错误百出。欢迎批评指正,期待共同成长!
题目描述
给出一个不大于 9 的正整数 n,输出 n×n 的蛇形方阵。
从左上角填上 1 开始,顺时针方向依次填入数字,如同样例所示。注意每个数字有都会占用 3 个字符,前面使用空格补齐。
输入样例
输入
4
输出
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7
题解部分
涉及算法:模拟。
各位读者有听说过“建模”一词吗?所谓“建模”,就是把事物进行抽象,根据实际问题来建立对应的数学模型。“抽象”并不意味着晦涩难懂;相反,它提供了大量的便利。计算机很难直接去解决实际问题,但是如果把实际问题建模成数学问题,就会大大地方便计算机来“理解”和“解决”。
思路
1.首先我们可以把题目抽象成数学问题,题目可以理解成为在一个方格里按一定规律填自然数,规律如下图。
(画的丑各位轻喷)
可以看出"小蛇"的走向是右、下、左、上、反复循环。
2.建模完毕之后,我们可以把这个矩阵用二维数组来表示,每填一个数就相当于x或者y变化。
注意这个坐标系的建立是根据二维数组的特性建立的x代表行、y代表列。
int map[15][15]; //虽然题目要求数据最大是9*9,但为了避免内存会爆一般会把数组空间开大一点。 for(i=1;i<=n*n;i++) map[x][y]=i;
3.那如何控制方向呢?其实只需要再定义一个二维数组就可以啦。
int pos[4][2]={ {0,1), //向右填数 {1,0},//向下填数 {0,-1},//向左填数 {-1,0}};//向上填数
注意顺序一定要按小蛇的走向规律填写。
为了方便大家理解,可以来看下面这张图,正好与上面的源码对应。
通过这个方向数组,我们就很容易获得下一步的坐标。这里可以用tx,ty来表示。
int tx=x+t[d][0]; int ty=y+t[d][1]; ///通过改变d来改变方向。
4.如何判断下一步要不要换方向呢?这时,tx,ty就派上用场了。
我们需要判断tx、ty是否超出边界,来决定是否转向。
for(i=1;i<=n*n;i++) { map[x][y]=i; tx=x+pos[d][0],ty=y+pos[d][1]; if(tx>n||ty>n||tx<1||ty<1||map[tx][ty]>0) d=(d+1)%4;//因为只有四个方向所以d++时需要%4,使得d只能是0,1,2,3。 x=x+pos[d][0],y=y+pos[d][1];//判断完毕后就可以知道下一步填哪啦。 }
矩阵的大小为n*n,故边界为[1,n]。
所以一旦tx,ty,超出边界,就需转向。
需要注意的是遇到之前已经填过数字的方格也需要转向。
ok核心部分已经讲解完毕,下面奉上完整代码。
完整代码
c语言版
#include<stdio.h> int map[15][15];//需要定义在全局变量,好处是初始化默认值都是0。 int pos[4][2]={0,1,1,0,0,-1,-1,0}; int main() { int n; int i,j; scanf("%d",&n); int x=1,y=1,d=0; for(i=1;i<=n*n;i++) { map[x][y]=i; int tx=x+pos[d][0],ty=y+pos[d][1]; if(tx>n||ty>n||tx<1||ty<1||map[tx][ty]>0) d=(d+1)%4; x=x+pos[d][0],y=y+pos[d][1]; } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) printf("%3d",map[i][j]); printf("n"); } return 0; }
c++版
#include<bits/stdc++.h> using namespace std; int map2[15][15];//因为c++类库太多,定义名为map编译器会产生歧义,所以在后面加个2就ok了。 int pos[4][2]={0,1,1,0,0,-1,-1,0}; int main() { int n; cin>>n; int i,j; int x=1,y=1,d=0; for(i=1;i<=n*n;i++) { map2[x][y]=i; int tx=x+pos[d][0],ty=y+pos[d][1]; if(tx>n||ty>n||tx<1||ty<1||map2[tx][ty]) d=(d+1)%4; x=x+pos[d][0],y=y+pos[d][1]; } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) printf("%3d",map2[i][j]); cout<<endl; } return 0; }
最近刚接触的c++,不过单从这题来看好像也差不多(捂脸)。
到此这篇关于c/c++实现蛇形矩阵的示例代码的文章就介绍到这了,更多相关c/c++ 蛇形矩阵内容请搜索<计算机技术网(www.ctvol.com)!!>以前的文章或继续浏览下面的相关文章希望大家以后多多支持<计算机技术网(www.ctvol.com)!!>!
需要了解更多c/c++开发分享C/C++实现蛇形矩阵的示例代码,都可以关注C/C++技术分享栏目—计算机技术网(www.ctvol.com)!
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/1038220.html