Steps

POj No.2590 Steps

题目

在数轴上的两点之间,按照下面规则移动。

  • 每一步的步幅都要是自然数,同时必须与前一步幅相同或者是差 1。
  • 每一步和最后一步的步幅必须是 1。当给出两点位置的时候,请回答从第一个点移动到第二点需要的最小步数。

输入和输出

测试数据个数 n、开始地点 x 以及终点 y(0<=x<=y<2^31^),格式如下:

n
x~1~ y~1~
x~2~ y~2~

x~n~ y~n~

  • 输入

    3
    45 48
    45 49
    45 50

  • 输出

    3
    3
    4

代码

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<stdio.h>
int main(){
int step, i,len;

for(step=0;step<20;++step){
len=0;
//求得一半为止的步数
// 步数是奇数就加1
int mid=step/2+step%2;

//求出1+2+3+...到中间地点为止的合计
for(i=1;i<=mid;++i) len+=i;

//从中间地点开始计算...+3+2+1
for(i=step/2;i>0;--i) len+=i;

printf("%2d step(s)...%3d\n",step,len);
}
}

解决思路

画图找规律

文章作者: lmislm
文章链接: http://blog.booml.cn/2017/05/21/poj No.2590/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Baskerville*