4

現在、再帰関数の割り当てを行っています。フィボナッチ プログラムを実行するように依頼されましたが、問題なく実行できました。しかし、私はそれに対するカウンターを作る必要があり、ここで私は立ち往生しています。

私はこの機能を持っています

int fibonacci(int n)
{
    if( n == 0 )
    {
        //my fibonacci code 
    }
    else if( n == 1 )
    {
        //my fibonacci code
    }
    else 
    { 
        //my fibonacci code
    }
}

では、これにカウンターを追加するにはどうすればよいですか? カウンターを追加するたびに、間違った数値が返されます。

編集 明確にするために、私の関数は正常に動作し、フィボナッチ数を生成します。関数内にカウンターを追加して、フィボナッチ数を生成するたびに呼び出される回数を確認したかっただけです。

それ以来、メイン関数でカウンターを初期化し、再帰でインクリメントする以下の方法のいずれかを試しましたが、数値が正しいかどうかはわかりません。たとえば、フィボナッチ数が 610 の場合、関数を 609 回呼び出していると言っていますが、それは正しいですか?

4

4 に答える 4

4

デモンストレーションのためにカウントが必要なだけだと思いますよね？呼び出しのカウントは、参照によってカウンター変数を渡し、次のように各呼び出しの開始時に一度増加させることで簡単に達成できるはずです。

#include <iostream>

// ...

int fibonacci(int n, int &count)
{
    ++count;
    // other code ...

    // and every time you call fibonacci recursively,
    // simply pass in the same reference, like so:
    if (...) {
        fibonacci (new_n, count);
    }
}

int main(int argc, char** argv)
{
    // call it with an int variable initialized to 0:
    int fibCnt = 0;
    fibonacci(10, fibCnt);
    std::cout << "Function was called "<<fibCnt<<" times"<<std::endl;
}
于 2013-08-27T13:26:37.760 に答える
1

カウンターは必要ありません。あなたのコードはすでにほとんどそこにあります

int fibonacci(int n)
{
    if( n == 0 )
    {
        return f_0
    }
    else if( n == 1 )
    {
        return f_1
    }
    else 
    { 
        return f_n using recursion
    }
}

フィボナッチ数は再帰によって定義されるため、最後のケースは明らかです。残りの 2 つは、再帰関係を閉じるためだけに必要です。つまり、最後のケースが無限ループに陥らないようにするためです。

于 2013-08-27T13:17:07.370 に答える
0

構造体を使用することが答えになる可能性があります。

struct factorial
{
  factorial() : counter(0)
  {}

  uint64_t foo(uint64_t x) {
    ++counter;

    if(x < 2)
      return 1;
    else
      return x * foo(x - 1);
  }

  template <class T>
  T operator()(const T& x) {
    return foo(x);
  }

  uint64_t counter;
} factorial;

この場合、fooは階乗関数です。しかし、構造体の使用法があるため、その名前はありません。

// output and calls
struct factorial foo;
std::cout << foo(5) << "\n";
std::cout << foo.counter << "\n";

// output
std::cout << factorial(5) << "\n";
于 2018-05-08T19:12:53.780 に答える
0

最初にコードを完成させます。再帰方程式を示します。

fib(0) = *deleted*
fib(1) = *deleted*
fib(n) = *deleted*

カウンター（質問で指定する必要があります）は、通常、関数の外部で定義されたグローバル変数によって実装できますが、関数内で変更できます。

質問の編集を参照してください：

あなたの番号は良くありません。あなたのタスクをこれ以上台無しにしないために、私は Erlang で答えを提供します。そのため、C++ タスクでそれを正しく行う方法を理解するために、まだいくつかの作業が残っています。:-)

-module(fib).

-export([f/1]).

%% returns a tupel { fibonacci value, number function calls }
f(0) -> {0, 1};
f(1) -> {1, 1};
f(X) -> 
    {F1, C1} = f(X - 1),  %% decompose tuple
    {F2, C2} = f(X - 2),
    {F1 + F2, C1 + C2}.  %% return value

これをシェルから実行すると、次のようになります。

Eshell V5.10.1  (abort with ^G)
1> c("q:/doc/erlang/fib", [{outdir, "q:/doc/erlang/"}]).
{ok,fib}
2> fib:f(0).
{0,1}
3> fib:f(1).
{1,1}
4> fib:f(2).
{1,2}
5> fib:f(3).
{2,3}
6> fib:f(4).
{3,5}
7> fib:f(5).
{5,8}
8> fib:f(6).
{8,13}
9> fib:f(7).
{13,21}
10> fib:f(15).
{610,987}
11>

したがって、F(15) = 610 の値を取得するために 987 回の関数呼び出しが行われます。

ここで興味深いのは、フィボナッチ再帰 F の適切な開始条件について説明したコメントです (状況は微分方程式に似ており、開始点が異なると、別の軌道/解が得られます)。

私は F(0) = 1 と F(1) = 1 を間違えましたが、@WhozCraig は F(0) = 0 と F(1) = 1 であるべきだと正しく指摘しました。

上記の Erlang コードを見ると、関数呼び出しの数を生成する級数の計算もフィボナッチ型 (級数の最後の 2 つのメンバーを追加) であることがわかりますが、その 1 つは最初の値 1 と 1! :-)

于 2013-08-27T13:12:06.963 に答える