C++ Stack Fibinacci Hw 问题澄清

Question

大家好。我需要帮助来理解我的硬件分配。我刚开始使用 C++，不太了解。我确实知道堆栈和斐波那契数列的基础知识。但是我并不完全理解给我的问题，不需要解决问题的代码，而是帮助澄清一些步骤。这是硬件:

“通过完成此项目，您将熟悉在 C++ 中使用递归和创建 ADT。

创建一个整数堆栈 ADT(您可以修改讲义中给您的 IntStack ADT)，使其最大容量至少为 256 个元素。如果它被打印到 C++ ostream - 例如 cout)，还要添加任何需要的内容，以便它打印出它的内容(从左到右，堆栈的顶部在右边)。该堆栈的设计应使其仅包含大于零的有意义的值。小于或等于零的值应打印为“?”。

编写类里面讨论的斐波那契数列的递归实现。另外 - 创建一个在调用之间持续存在的堆栈 ADT 实例(它不能是局部变量)，并在每个步骤中将一个无意义的值插入其中，直到确定该阶段的值，然后将其弹出, 并在返回前压入确定的值并打印整个堆栈。

您的程序应该要求确定斐波那契数列中的位置 N，然后它应该输出函数调用的结果。示例输出(包括递归函数的输出)如下:

输入斐波那契数列中的位置来确定:5

?-?-?-1
?-?-?-1
?-?-2
?-?-1
?-3
?-?-1
?-?-1
?-2
5

Fibonacci(5) = 5

这里的输出到底是什么？它是否在计算第 5 个位置时打印出堆栈？还有关于如何在 C++ 中将 Fibonacci 实现到堆栈中的任何想法？这些值应该存储在数组、列表中还是无关紧要？我是菜鸟，所以任何帮助将不胜感激。谢谢

Answer 1

是的，它正在计算第 5 个斐波那契数(恰好是 5，这有点令人困惑)，但是看看您调用 fibonacci(5) 时计算的内容，假设斐波那契的代码如下:

int fibonacci(int n) {
    if (n <= 1) return n;
    else if (n == 2) return 1;
    else return fibonacci(n-1) + fibonacci(n-2);
}

这里是计算 fibonacci(5) 的函数调用:

f(5)
 -> f(4)
     -> f(3)
         -> f(2)
         -> f(1)
     -> f(2)
 ->f(3)
    -> f(2)
    -> f(1)

如果您将其视为一棵二叉树，他们给您的输出是后序树遍历，数量为？是该堆栈的深度，数字是该节点的值。

所以只需执行函数的操作，每次看到返回时，写下返回的内容(前面有 ?):

• 第一个返回的函数是第一个 f(2)，深度为 4:print ?-?-?-1
• 第二个返回是它下面的 f(1):print ?-?-?-1
• 第三个返回是 f(2) 和 f(1) 的父级，深度为 3，值 f(2)+f(1)=2:print ?-?-2
• 依此类推，直到返回深度为 0 且值为 5 的 f(5)