蓝桥杯 C语言省赛 习题3 移动距离 – 小文's blog

蓝桥杯 C语言省赛 习题3 移动距离

题目:


移动距离

X星球居民小区的楼房全是一样的,并且按矩阵样式排列。其楼房的编号为1,2,3...
当排满一行时,从下一行相邻的楼往反方向排号。
比如:当小区排号宽度为6时,开始情形如下:

1 2 3 4 5 6
12 11 10 9 8 7
13 14 15 16 17 18

19

...

...

...

输入为3个整数w m n,空格分开,都在1到10000范围内我们的问题是:已知了两个楼号m和n,需要求出它们之间的最短移动距离(不能斜线方向移动)

w为排号宽度,m,n为待计算的楼号。
要求输出一个整数,表示m n 两楼间最短移动距离。

例如:
用户输入:
6  8  2
则,程序应该输出:
4

再例如:
用户输入:
4  7  20
则,程序应该输出:
5


思路:


其实题目的意思不难理解,就是求出2个数之间的最小距离。可是这并不是一个二维数组,而是一个经过变形了的二维数组。

楼主一开始的思路是:先建立一个标准的二维数组,然后按照题目的要求变形为“X星球居民小区的楼号分布”

按照题目所给的2个楼号找出对应的数组下标,再求最短距离。(楼主语言表达能力不强=.=,看不懂的看下面的流程图吧)

 

 
20161210161546

 

 

这种方法做出来是完全没有问题的,但是楼主又想到一个好方法

既然楼牌号是固定的,只和w的值有关,那我们大可不必创建二维数组,直接求解。

具体思路为:先判断m和n这两楼牌号所在的行((m-1)/w+1   (n-1)/w+1),

若行差为偶数则说明m  n所在的行 同为顺序或者倒序,此时按照同顺序的方式求;

若行差为奇数数则说明m  n所在的行 一个为顺序一个为倒序,此时按照不同顺序的方式求;

这样做不仅节约空间,时间复杂度也低。具体步骤看下面流程图


20161210165211

画图累死了0.0,还有几张图由于今天换站点搞的不能显示了,真是悲催,不懂的或者找不到图片的问我吧。

心累求打赏

运行截图:


20161210170548

完整代码:

 

 

文章:蓝桥杯 C语言省赛 习题3 移动距离 ,来自小文‘s blog,原文地址:https://www.qcgzxw.cn/668.html 转载请注明出处。

 

打赏博主

点赞

发表评论

在发表评论前请确认您的言论中没有违反中国各项法律、法规和违背社会道德的内容。任何无意义的留言内容都会被直接删除。

上传图片