1

2 つの整数 (>0) (n1,n2) を取得する関数 (C++) を作成する必要があります。私ができることは次の 2 つだけです。

  • 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

問題を好転させるのが最善だと思います: 次の 2 つの設定で n2 から n1 に移動します。

  • 1を引く
  • 2 で割る (結果が整数の場合のみ)

このようにして、最初に数値を 2 で割ろうとするときに最大のステップを見つけることができます。それが不可能な場合は、1 で減算します (その後、除算が機能します)。n1に到達するまでこれを続けます（またはそれより低い値。その後は「減少ステップ」のみを使用できるため、基本的に必要なステップ数がすでにわかっています）

このアルゴリズムを自分で実装できると思います...

于 2013-01-26T12:29:36.910 に答える
2

一歩ずつ考えてみてください。

n1isstartとn2isとしましょうend。

すでにある場合はend、手順は必要ありません。startより大きい場合はend、できません。

それ以外の場合は、2 つのオプションがあります..

  • に 1 を追加しstartてプロセスを再帰的に繰り返す - ステップ数をadd
  • 2 を掛けstartてプロセスを再帰的に繰り返す - ステップ数をmult

両方が可能な場合は、2 つのうち最も低い方が答えになります。

削除される前に私のコードを入手した場合は、時間をかけてステップを踏んでみてください。

ps 多数のステップの場合、これを末尾再帰アルゴリズムとして実装して、<insert name of the website here>.

pps 各ブランチを探索するため、これは非常に非効率的なアルゴリズムです。あなたはそれを改善し、必要なブランチの数を減らすことを試みることができます。おそらく、mult がうまくいかない場合にのみ追加してください..

于 2013-01-26T12:31:06.947 に答える
1

前述のように、n2 から n1 に逆に進むことで、貪欲な選択を認める問題に問題を変換できます。もちろん答えは同じです。

しかし、さらにいくつかの観察を行うことができます。

  • シフトの結果が小さすぎる数値になる場合、これから実行する必要があるステップの数は ですcurrent - n1。これらすべてのステップを 1 つずつカウントする必要はありません。
  • シフトの結果が小さすぎない数値になる場合は、現在の数値が奇数か偶数かに関係なく、いつでもシフトできます (ただし、実行したステップ数に最下位ビットを追加します。それは一歩を踏み出しただろう）
  • 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 に答える