将一个整数转换为另一整数的最小步骤数

Question

最近我遇到一个问题，给定2个整数A和B，我们需要以最少的步数将A转换为B。我们可以在A上执行以下操作：

• 如果A是奇数，则减少1
• 如果A是偶数，则增加1
• A（偶数或奇数）乘以2
• 如果A是偶数，则除以2

同样，我们必须找到将A转换为B所需的最少步骤。

约束为0

我的方法：我尝试使用广度优先搜索解决问题，将所有可能的可到达数字从一个步骤添加到队列中，但是在更高的约束（即超时）下失败。

谁能建议一个更快的替代方法？

编辑：A不一定小于B

Answer 1

基本上，您可以进行以下操作：

1. 翻转最低位
2. 向左或向右移动位

假设您有A == 0，您将如何构造B？右，您将低位一位一位翻转，然后将数字左移，例如，如果B == 5为0x0101，则需要2次翻转和2次移位。

[现在，我们必须处理A != 0的情况-在这种情况下，您必须将低位转到0并向右移以清理混乱。例如，如果您有A == 32，即0x0100000，而您想获得5（0x0101），则必须向右移动3个移位，然后翻转低位，就可以完成。

因此，您要做的就是：

1. 计算在A的最高位等于B的最高位之前必须执行的翻转/右移次数。
2. 然后计算您需要清理多少次翻转/右移
3. 计算重建B的下部需要多少次翻转/左移。

Answer 2

可以使用动态编程来优化此问题。

我编写了以下代码，其中考虑了几件事：

1. 应该通过提出基本条件来小心地避免无限递归。例如：如果A = 0且B <0，则不存在答案。

2. 如果函数convert（A，B）在递归中调用了1次以上，并且事先未计算状态（A，B）的答案，则由于在这种情况下不存在答案，因此递归终止。例如：（80，100）->（160，100）->（80-> 100）->（160，100）。

这是通过将每个状态的计数保存到映射中并为DP的相同状态定义最大递归调用限制（在以下程序中为3）来完成的。

#include <utility> 
#include <iterator> 
#include <map>
#include <set> 
#include <iostream>
#include <climits>

typedef long long int LL;

std::map<std::pair<LL, LL>, LL> dp;

std::map<std::pair<LL, LL>, int > iterationsCount;

LL IMPOSSIBLE = (LL)1e9;

LL MAX_RECURSION_LIMIT = 3;

LL convert(LL a, LL b) 
{ 
//std::cout<<a<<" "<<b<<std::endl;

    //To avoid infinite recursion:
        if(iterationsCount.find(std::make_pair(a, b))!=iterationsCount.end() &&
        iterationsCount[std::make_pair(a,b)] > MAX_RECURSION_LIMIT &&
        dp.find(std::make_pair(a,b))==dp.end()){
            return IMPOSSIBLE;
        }

    iterationsCount[std::make_pair(a, b)]++;

    LL value1, value2, value3, value4, value5;

    value1 = value2 = value3 = value4 = value5 = IMPOSSIBLE;

    if(dp.find(std::make_pair(a,b)) != dp.end()){
        return dp[std::make_pair(a, b)];
    }

    if(a==0 && b<0){
        return IMPOSSIBLE;
    }

    if (a == b) 
        return 0; 

    if (a%2 == 1){

        if(a < b){

            value1 = 1 + convert(2*a, b);

        }

        else if(a > b){

            value2 = 1 + convert(a-1, b); 

        }
    }
    else{

        if(a < b){


            value3 = 1 + convert(a*2, b);



            value4 = 1 + convert(a+1, b);

        }

        else if(a > b){

            value5 = 1 + convert(a/2, b);

        }
    }

    LL ans = std::min(value1, std::min(value2, std::min(value3, std::min(value4, value5))));

    dp[std::make_pair(a, b)] = ans;

    return ans;
} 

int main(){

    LL ans = convert(10, 95);
    if(ans == IMPOSSIBLE){
        std::cout<<"Impossible";
    }else{
        std::cout<<ans;
    }
    return 0;
}