1

我需要编写一个函数（在 C++ 中）获取两个整数（>0）（n1，n2）。我只能做两件事：

  • n1 加 1。
  • 将 n1 乘以 2。

该函数返回从 n1 到 n2 的最短路径的步数。你能给我一些想法吗？

谢谢！

PS如果不可能，该函数返回-1。

这里我尝试了什么：

if (n1<n2)
{
    n1++;
    if ((n1)*2<=n2)
        return 2+f(n1*2,n2);
    else
        return 1+f(n1,n2);
}
4

5 回答 5

3

我想最好扭转这个问题：从 n2 到 n1 用这两个 tings ：

  • 减 1
  • 除以 2（仅当结果为整数时）

这样，当您第一次尝试将数字除以 2 时，您可以找到最大的步骤，如果不可能，则减去 1（之后除法有效）。继续这样做，直到达到 n1（或更低的值，之后您只能使用“减少步长”，因此基本上已经知道所需的步数）

我想你可以自己实现这个算法......

于 2013-01-26T12:29:36.910 回答
2

一步一步想一想。

可以说n1是start和n2是end。

如果你已经在end，那么你不需要步骤。如果start大于end，你不能这样做。

否则你有两个选择..

  • 添加 1start并递归地重复该过程 - 将步骤数存储为add
  • 乘以start2 并递归地重复该过程 - 将步骤数存储为mult

如果两者都可能，那么两者中最低的就是你的答案。

如果你在我的代码被删除之前得到了我的代码，我希望你能花点时间来逐步完成它，否则你可以试着把它写出来..大约需要一分钟左右..

ps 对于大量步骤，您可能希望将其实现为尾递归算法以防止<insert name of the website here>.

pps 这是一个非常低效的算法，因为它会探索每个分支。您可以尝试改进它并尝试减少所需的分支数量，也许只有在 mult 不这样做时才添加..

于 2013-01-26T12:31:06.947 回答
1

如前所述，您可以通过逆向从 n2 到 n1 将问题转换为允许贪婪选择的问题。答案当然是一样的。

但可以进行更多观察：

  • 如果换档会导致数字太低，那么从现在开始您必须采取的步数是current - n1，您不必逐个计算所有这些步数。
  • 如果移位会导致一个不太低的数字，那么无论您当前是奇数还是偶数都没有关系，您总是可以移位（但将最低位添加到所采取的步数中，因为它会迈出一步）
  • 使用 n1 和 n2 中最高设置位的位置，可以一次执行多个移位（将移位量和要移出的位的汉明权重添加到步数）。您可以进行的班次数量是bsr(n2) - bsr(n1) - 1，但要注意极端情况。这并不总是最大的换档步数，它可能需要多一个（但不能超过这个）。
于 2013-01-26T12:56:06.727 回答
0 
int numOfSteps(int n1, int n2) {
    if (n1 > n2) return -1;
    if (n1 == n2) return 0;
    int result = 0;
    while (n1 * 2 <= n2) {
            n1 *= 2;
            result ++;
    }
    while (n1 < n2) {
            n1 ++;
            result ++;
    }
    return result;
}
于 2013-01-26T12:31:53.667 回答
0

我解决它！（我向我的朋友寻求建议......）

这是代码：

int f(unsigned int n1, unsigned int n2){

int num1,num2;

if (n1==n2)
        return 0;
if (n1>n2)
    return -1;
num1=f(n1+1,n2)+1;
num2=f(n1*2,n2)+1;
return min(num1,num2);}

这是“分钟”：

int min (unsigned int n1, unsigned int n2){
if (n1*n2==0) //If one of them is zero then (n1+n2) return the non-zero
              //number.
    return n1+n2;
else
    if (n1>n2)
        return n2;
    else
        return n1;}

谢谢！！

于 2013-01-26T20:02:22.623 回答