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
    }
}

由于斐波那契数是通过递归定义的，最后一种情况是显而易见的。其他两个仅用于关闭递归关系，即避免最后一种情况导致无限循环。

于 2013-08-27T13:17:07.370 回答
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

从 shell 运行它会给出：

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>

因此我得到了 987 个函数调用来获得 F(15) = 610 的值。

这里有趣的一点是，在评论中我们谈到了斐波那契递归 F 的正确开始条件（情况类似于微分方程，不同的起点让您获得不同的轨迹/解决方案）。

我弄错了 F(0) = 1 和 F(1) = 1，而 @WhozCraig 正确指出它应该是 F(0) = 0 和 F(1) = 1。

如果您查看上面的 Erlang 代码，您会看到产生函数调用次数的系列的计算也是斐波那契类型之一（添加系列的最后两个成员），但那个是开头的那个值 1 和 1！:-)

于 2013-08-27T13:12:06.963 回答
0

使用 struct 可能是答案。

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 回答