c语言提问：求正整数x到y的最小步数（0<=x<y<=2^31)

Question

我描述一下问题，说实话我都花好大劲才懂。
求正整数x到y的最小步数（0<x<y<2^31)： 第一步和最后一步的步长必须是1。以后每一步步长必须和前一步步长相等，或者多1，或者少1。

我给点例子：
55到59 最少3步：1， 2， 1
55到60 最少4步：1，2，1，1 或者 1，1，2，1 (不可以1，3，1，违反了规则)
55到61 最少4步：1，2，2，1 (不可以1，4，1，这违反了规则)

用C或者C++求解 500 1000的最小步长。
谁能求解呢？给点想法也可以。很急，最好今天答案。多谢多谢！！！！！！！！！！

Answer 1

差 分解
1 1

2 1 1
3 1 1 1

4 1 2 1
5 1 2 1 1
6 1 2 2 1
7 1 2 2 1 1
8 1 2 2 2 1

9 1 2 3 2 1
10 1 2 3 2 1 1
11 1 2 3 2 2 1
12 1 2 3 3 2 1
13 1 2 3 3 2 1 1
14 1 2 3 3 2 2 1
15 1 2 3 3 3 2 1
16 1 2 3 4 3 2 1
从分解中可以看出，分解的数中最大的数（最大步长）为对差值求根号，并取整（如sqrt（10）=3），假设这个值为n，
对于差值为n*n的这个差值（9），分解后的形式就是1 2 3...n...3 2 1，这个步数为2*n-1（例如9的步长为5），这个是基本的步数；
继续往下，差值大于n*n+0*n，小于n*n+1n步数就加1,
(如10大于3*3+0，小于3*3+3，所以10的步数为5+1=6)
差值大于n*n+1*n，小于n*n+2*n步数就加2,
（如13，大于3*3+1*3，小于3*3+2*3，步数为7）
.....

以后遇到这种问题，果断的多写几个例子出来，慢慢分析.

#include<stdio.h>
#include<math.h>
int main(void)
{
int x,y;
int nStep=0;//步数
int nMax;//最大的步长
int m;//y-x与nMax平方的差
scanf("%d %d",&x,&y);
nMax=(int)(sqrt(y-x));

nStep=2*nMax-1;//基本步长

m=(y-x)-nMax*nMax;
nStep=nStep+(m+nMax-1)/nMax;//每多一个nMax，步长加1

printf("最小的步数为:%d\n",nStep);

return 0;
}

Answer 2

第一，明确最小步长一定是让中间几步尽可能大。
然后容易得出影响步长的关键数据num
=（大数-小数）/2
令1+2+3……在小于num的前提下得出序列的最大值max。
然后num-max的剩余值如果等于max+说明中间还差一步更大的值，即max+1，且刚好用完所有值。即步数=2*max+1。

如果不等则须插两个小于等于max的值。即步数等于2*max+2。

我要睡觉了。直接给你函数算了

int fun(int beginNum, int endNum)
{
int max = 1;
int sum = 2*max;
int num = endNum-beginNum;
while(sum < num)
{
sum+=2*(max++);
}
if(max == sum - num)
return 2*max-1;
else return 2*max;
}

睡去了，代码没跑，不过估计问题不大

Answer 3

我觉得这好比一个金子塔
1
1 1 1
1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
而仔细点看就只有一半了，将两边1加起来就是2，4，6，8....之后就成了多个偶数再加上最顶上（也就是最中间那一排）一个奇数或两个偶数求和的sum要等於1000-500,可以在快到得时候加一个判断比500大或者下，然后处理一下边界问题就可以了。细的程序就不说了，我下班回家了

Answer 4

对不起 问题没有说明白