比较递归和迭代之间的执行时间（使用堆栈类模板）Fibonacci实现 [英] Comparing execution time between recursive and iterative (using stack class template) Fibonacci implementation

问题描述

大家好，我是C ++的新手，并尝试编写我的第一个程序来比较递归和迭代之间的持续时间（使用堆栈类模板）。 众所周知，Fibonacci表示为：

f< sub> n< / sub> = f< sub> n-1< / sub> + f< sub> n-2< / sub>   
其中n> 1， f< sub> 1< / sub> = 1，
f< sub> 0< / sub> = 0.

我正在尝试使用3个堆栈实现堆栈版本Fn，Fn-1和Fn-2的值。

我的代码（如下所示）不会给我任何编译器错误但是没有按预期工作。 我想产生如下输出：

序列0,1,1,2,3,5,8 ......

迭代需要  ; xxxx秒

递归需要xxxx秒

请帮助：

#include< iostream>

#include< Windows.h>

#include< mmsystem.h>

解决方案

好吧，我能看到的两个最明显的问题是：

1）使用警告级别4进行编译，我得到的负载为：

1> ; ------重建全部开始：项目：meh，配置：调试x64 ------
$
1> main.cpp

1> c： \users\darran\source\repos\meh\meh\main.cpp（111）：警告C4702：无法访问的代码

1> c：\ usersrs \ divar \ thesource \repos\meh\meh\main.cpp（64）：警告C4702：无法访问的代码

1> c：\ usersrs \ divarn \ source \\ \meh\meh\main.cpp（67）：警告C4702：无法访问的代码

1> c：\ usersrs \ darran\source \repos\meh \ meh \main.cpp（113）：警告C4702：无法访问的代码

1> c：\ usersrs \ darran\source \repos\meh \meh \ main.cpp（81）：警告C4702：无法访问的代码

1> c：\ usersrs \ darran \source \repos\meh \meh \\\ main.cpp（114）：警告C4702：无法访问的代码

1> c：\users\darran\source\repos\meh\meh\main.cpp（118）：警告C4702：无法访问的代码

1> c：\ usersrs \\ \\ darran\source\repos\meh\meh\main.cpp（119）：警告C4702：无法访问的代码

1> c：\ usersrs \\\\\\\\\\\\\\\ \\ repos\meh\meh\main.cpp（120）：警告C4702：无法访问的代码

1> c：\ usersrs \ darran \ source \ times \ meh \\ meh\main.cpp（123）：警告C4702：无法访问的代码

1> c：\ usersrs \ darran\source \repos\meh \meh \ main。 cpp（56）：警告C4701：使用了未初始化的局部变量'duration'
1> meh.vcxproj - > C：\ Users \Darran \source \repos\meh \ x64 \Debug\meh.exe

1>完成建筑项目"meh.vcxproj"。

==========重建全部：1成功，0失败，0跳过==========

这是与main中间的return语句相关。返回后的代码将永远不会执行，因为返回告诉函数退出。

2）行：

 cout << pfib<< "，" << endl; 

实际上会打印出函数的地址，而不是调用它。实际上，您需要在循环中使用函数调用，因此，您还需要三个堆栈变量，每个参数对应一个。对于fiber_iter函数原型，你还需要
来生成这些参数：

 int fiber_iter（Stack< int>& a，Stack< int> ;& b，Stack< int>& c）

否则您只会将堆栈对象的副本传递给函数，并且任何更改都将在返回时丢失。

Hi everyone, I am new to C++ and trying to write my first program to compare the duration times between recursive and iterative (using stack class template).  As you all know, Fibonacci is represented as:

f_n= f_n-1+ f_n-2   where n > 1, f₁= 1, f₀= 0.

I am trying to implement the stack version using 3 stacks that will store values for Fn, Fn-1 and Fn-2.

My code, shown below, does not give me any compiler errors but does not work as expected.  I want to produce an output like:

The Sequence 0, 1, 1, 2, 3, 5, 8 ...

Iterative takes  xxxx seconds

Recursive takes xxxx seconds

Please help:

#include <iostream>
#include <Windows.h>
#include <mmsystem.h>

解决方案

Well, the two most obvious problems that I can see are:

1) Compiling with warning level 4, I get a load of:

1>------ Rebuild All started: Project: meh, Configuration: Debug x64 ------
1>main.cpp
1>c:\users\darran\source\repos\meh\meh\main.cpp(111): warning C4702: unreachable code
1>c:\users\darran\source\repos\meh\meh\main.cpp(64): warning C4702: unreachable code
1>c:\users\darran\source\repos\meh\meh\main.cpp(67): warning C4702: unreachable code
1>c:\users\darran\source\repos\meh\meh\main.cpp(113): warning C4702: unreachable code
1>c:\users\darran\source\repos\meh\meh\main.cpp(81): warning C4702: unreachable code
1>c:\users\darran\source\repos\meh\meh\main.cpp(114): warning C4702: unreachable code
1>c:\users\darran\source\repos\meh\meh\main.cpp(118): warning C4702: unreachable code
1>c:\users\darran\source\repos\meh\meh\main.cpp(119): warning C4702: unreachable code
1>c:\users\darran\source\repos\meh\meh\main.cpp(120): warning C4702: unreachable code
1>c:\users\darran\source\repos\meh\meh\main.cpp(123): warning C4702: unreachable code
1>c:\users\darran\source\repos\meh\meh\main.cpp(56): warning C4701: potentially uninitialized local variable 'duration' used
1>meh.vcxproj -> C:\Users\Darran\source\repos\meh\x64\Debug\meh.exe
1>Done building project "meh.vcxproj".
========== Rebuild All: 1 succeeded, 0 failed, 0 skipped ==========

This is related to the return statement in the middle of main. The code after that return will never execute because the return tells the function to exit.

2) The line:

cout << pfib << "," << endl;

Will actually print out the address of the function, not call it. You will actually need to use a function call in a loop, and as such, you will also need three stack variables, one for each parameter. For the fiber_iter function prototype, you will also need to make these parameters references:

int fiber_iter(Stack<int> &a, Stack<int> &b, Stack<int> &c)

otherwise you will only pass copies of the stack objects to the function and any changes will be lost on return.

这篇关于比较递归和迭代之间的执行时间（使用堆栈类模板）Fibonacci实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！