目前正在对递归函数进行赋值。被要求做一个斐波那契程序,这样做没有太多问题。但我需要为它做一个计数器,这就是我被卡住的地方。
我有这个功能
int fibonacci(int n)
{
if( n == 0 )
{
//my fibonacci code
}
else if( n == 1 )
{
//my fibonacci code
}
else
{
//my fibonacci code
}
}
那么我该如何添加计数器呢?每当我添加计数器时,它都会返回错误的数字。
编辑为了澄清,我的函数在生成斐波那契数时工作得很好。我只是想在函数中添加一个计数器,这样我就可以看到每次我想让它生成斐波那契数时,它被调用了多少次。
此后,我尝试了下面的一种方法,在主函数中初始化计数器,然后在递归中递增,但不知道数字是否正确。例如,它说如果我的斐波那契数是610,我将调用函数609次,这是正确的吗?
我猜您只需要用于演示的计数,对吧?通过引用传入一个计数器变量,并在每次调用开始时增加一次,计数调用应该很容易实现,如下所示:
#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;
}
您不需要任何计数器。你的代码已经快到了
int fibonacci(int n)
{
if( n == 0 )
{
return f_0
}
else if( n == 1 )
{
return f_1
}
else
{
return f_n using recursion
}
}
由于斐波那契数是通过递归定义的,最后一种情况是显而易见的。另外两个只需要关闭递归关系,即避免最后一种情况导致无限循环。
首先完成代码。我给你递归方程:
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(O)=0和F(I)=1。
如果你看上面的Erlang代码,你会发现产生函数调用次数的序列的计算也是Fibonacci类型的(加上序列的最后两个成员),但这个序列的起始值是1和1!:-)
使用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";