我的逻辑哪里出错了，需要乘以2，再减去1来得到一个给定的数字？

Question

http://codeforces.com/contest/520/problem/B

瓦西娅发现了一个奇怪的装置。在设备的前面板上有:一个红色按钮，一个蓝色按钮和一个显示某个正整数的显示屏。单击红色按钮后，设备会将显示的数字乘以2。单击蓝色按钮后，设备会从显示屏上的数字中减去1。如果在某一时刻这个数字不再是正数，设备就会崩溃。显示器可以显示任意大的数字。最初，显示屏显示数字n。

鲍勃想把数字m显示在显示器上。为了达到这个结果，他至少需要点击多少次？

输入输入的第一行也是唯一一行包含两个不同的整数n和m (1 ≤ n， m ≤ 10^4)，用空格分隔。

输出打印单个数字-按下数字n中的数字m所需的最小按钮次数。

我开发了以下递归解决方案。我知道它会超时，但我会记住它，这将使我的解决方案被接受。但到目前为止，我在其中一个输入中得到了错误的答案。

我的代码是：

int func (int n, int m);
int main (void)
{
    int n,m;
    cin>>n>>m;
    int count = func(n,m);
    cout<<count<<"\n";
    return 0;
}

int func (int n, int m)
{
    if (n == 0)
        return INT_MAX; // this should be because we can never go to some 
                        // other digit if we are at 0
    if (n == m)
        return 0;
    else if (2*n == m || n == m+1)
        return 1;
    else if (n > m)
        return func(n-1,m)+1;
    else 
        return min(func(n-1,m),func(n*2,m))+1;
}

现在，当我输入(1,3)作为输入时，我的代码显示分割错误。我试着调试它，我发现它在无限循环中运行，因此我得到了Seg错误。但是，我想知道，那么我应该如何制定逻辑呢？它的递归函数是什么？谢谢!

Answer 1

SEG故障是由于计算执行INT_MAX+1造成的。

实际上，我认为这样做可以更好地解决这个问题。

• 对于所有情况n>m，最短的计数是n-m。

如果(n

• For all case n==m，则最短计数为0。

else if (n==m)返回0；

• 对于所有情况n< m，最短计数可计算为：

设序列Y= (m/(2^1)，m/(2^2)，... 1 //使用上限值查找X是Y中的下一个数，其中n >= X。return func(X*2) + n-X + 1;

对于n= 57，m= 201，则Y= 101，51，26，13，7，4，2，1，X将是51。因此，答案可以计算为

 (57-51)+1 = 7 steps, result now 51*2 = 102
 (102-101)+1 = 2 steps, result now 101*2 = 202
 (202-201) = 1 steps
 =====> Total steps 10

对于n= 4，m= 6，那么Y= 3，2，1，X就是3。

 (4-3)+1 = 2 steps, result now 3*2=6
 =====> Total steps 2

对于n= 1，m= 3，那么Y= 2，1，X就是1。

 already in Y= 1 steps, result now 1*2 = 2
 already in Y= 1 steps, result now 2*2 = 4
 (4-3) = 1 step
 =====> Total steps 3

请注意，您可以在进入函数之前预先计算Y，并传递它，这样您就不必每次都重新计算。