1

再帰関数について読んでいて、この関数の数式を理解しようとしています。対数関数かと思いましたが、そうではないようです。誰かが私を正しい方向に向けることができれば、私はそれを感謝します.

unsigned f(unsigned n){
    if(n<2)
    return 1;

    return 1 + f(n/2);
}
4

5 に答える 5

4

これは、2 を底とする対数関数です。より具体的には、.ceil 1 + floor(log2(n))

于 2013-05-10T01:56:39.453 に答える
1

関数が基づいている数式が気になるので:

ここにあります:fの関数ですn:

f(n) = 1 + f(n/2) if n >=2
f(n) = 1          if n <=1  //n is unsigned so n >=0

上記の式を念頭に置いて、基礎となるアルゴリズムは対数の複雑さを持ちます。その理由は、すべてのステップで のサイズが半分に縮小され、1 に到達nするのに(基数 2) のステップが必要になるためです。したがって、 の対数複雑度です。log(n)O(logn)

于 2013-05-10T01:54:23.743 に答える
1

あなたが「数学関数」と言ったことは知っていますが、それは既存の回答のパースペクティブを設定していますが、別のパースペクティブを示すために、次を返します。

  • 格納に必要なビット数n(数値 0 を意味のある符号化するために 1 ビットが必要であると考える場合、数値がまったくない場合とは異なります)
  • で設定された最上位ビットの 1 から始まるインデックスn|1、別名
  • (1) および ( で設定された最上位ビットの 1 ベースのインデックス) の最小n値

コードを見ているときに、関数が異なる意図で使用できることを確認すると役立つ場合があります。どちらの観点からも、使用のコンテキストを理解しやすくなる場合があります。

于 2013-05-10T02:29:35.390 に答える
0

より正確には、これは floor(logbase2(n)) を実装します

于 2013-05-10T01:55:31.547 に答える
0

この関数は、ゼロになるまで整数を 2 で割って、関数が実行された回数を返します。

元：

f(8)-

return f(4) //continue on
return f(2) //continue on
return f(1) //we know this is 1
return f(2) //now we can do this one, 2
return f(4) //and this one, 3
于 2013-05-10T01:53:26.367 に答える