回形取数-创新互联
问题描述
回形取数就是沿矩阵的边取数,若当前方向上无数可取或已经取过,则左转90度。一开始位于矩阵左上角,方向向下。
输入格式
输入第一行是两个不超过200的正整数m, n,表示矩阵的行和列。接下来m行每行n个整数,表示这个矩阵。
输出格式
输出只有一行,共mn个数,为输入矩阵回形取数得到的结果。数之间用一个空格分隔,行末不要有多余的空格。
样例输入
3 3
1 2 3
4 5 6
7 8 9
样例输出
1 4 7 8 9 6 3 2 5
样例输入
3 2
1 2
3 4
5 6
样例输出
1 3 5 6 4 2
我设计了三种算法来解决此道题目,并通过对算法的分析,来看该三种算法的优劣。
1. 算法设计:(递归法)
矩阵由四个边组成,回型取数在不同的边上取数方向不同,因此可以分为四种情况来取数。通过一个数s取余4来对应四个状态,通过递归算法来输出每个数,当每边的数取完时就使s加一来取另外一边的数(if...else..实现)。
递归时传参传的是每个数的行列值。例如:
当取完a【i】【j】时,若s=0时,对应取的是左边即向下取数,则传参数solve(i+1,j);若s=3时,对应取的是上边即向左取数,则传参数solve(i,j-1)。
--
程序代码如下
#include
#include
#define N 10
#define M 10
int s=0;
int m,n;
int a[M][N],b[M][N];
void solve(int i,int j){
if(i>=0&&i=0&&j
2、算法设计:逐圈分析分别处理每圈的左侧、下方、右方、上方的数据。先计算可分为几圈,由于每转一圈行上的个数会减少2个,因此看可以减少几个2就有几圈,用行数除以2可算出有几圈。(若行数为奇数,也是除二向下取整可举例实验)。
i 层内输出数据的4个过程为(四角元素分别归四个边):
(1) i 列(左侧),从 i 行到m-i-1 行;
(2) m-i-1行(下方),从 i 列到 n-i -1列;
(3) n-i-1 列(右侧),从 m-i-1 行到 i+1 行;
(4)i 行(上方),从 n-i-1 列到 i 列;
4个过程通过4个循环实现,用 j 表示 i 层内每边中行或列的下标。
__
程序代码如下:
#include
#include
#define M 10
#define N 10
void solve()
{
}
int main(){
int a[M][N];
int m,n,i,j;
scanf("%d%d",&m,&n);
for(i=0;ii;j--)
printf("%d",a[j][n-i-1]); //右侧
for(j=n-i-1;j>i;j--)
printf("%d",a[i][j]); //上方
}
return 0;
}
**3、算法设计:(算法设计数p.83)通过设置变量标识一圈中不同方位的处理差别,并通过算术运算将4个方位的处理归结成一个循环过程。
通过输出最外一圈的情况分析:
j=1 | i=i+1 | 0~n-1 | k=n | //左侧 |
---|---|---|---|---|
i=n | j=j+1 | 1~n-1 | k=n-1 | //下方 |
j=n | i=i-1 | n-2~0 | k=n-1 | //右侧 |
i=1 | j=j+1 | n-2~0 | k=n-2 | //上方 |
从上面i,j 的变化可发现:输出时,前半圈下标变化一致,都加1;后半圈都减1,不同的是变化范围,所以分两边前半圈和后半圈,引入t=1,每半圈改变t的正负号再进行行列值改变。
前半圈再分左边与下边,可知前m个数是左边,后n-1是下边,在此引入两值b【0】与b【1】,当第i个数取余m等于0时则为左边的数,因为(i从0取所以还是m个数)等于1则为下边的数。后半圈同理。。
为表达,要统一表示循环变量的范围,可发现当输出到左下角时行列数少一,右上角行列数又少一,因此在进行半圈输出后,要对行列值减一。**
——
程序代码如下:
#include
#include
#define M 10
#define N 10
int main(){
int a[M][N];
int b[2];
int m,n,x,y,i,j;
int t=1;
b[0]=-1;
b[1]=0;
scanf("%d%d",&m,&n);
for(i=0;i
-----
三种算法比较及学习心得:
算法 1、2比较好理解,在思考方面可以节约大量时间,算法也是相通的,体现了递归和循环的相互转换;
算法 3 需要通过归纳,构造循环不变式,写出的算法节约了运行时的时间。
比较偏向算法1,好理解,清晰明了,递归总是用很简单的语句实现了很复杂的过程,因此我很喜欢读递归程序。
通过算法三了解到,要善于通过数学归纳构造不变式,这也是一个写算法很好的习惯。
ps:第一次写博客,意犹未尽,之前以为完全掌握的在总结的时候还是会有磕绊的地方,通过写博客也是将该问题又踏平了不少,以后这个习惯还是要坚持的,是提高也是个记录与回忆吧,今天算是个好的开端吧?嘿嘿嘿。。
对了,浏览过有问题的话,我们再一起探讨啊!
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
网站题目:回形取数-创新互联
URL标题:http://scyanting.com/article/ispih.html