0

大家好。我需要帮助理解我的硬件任务。我从 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++ 中将斐波那契实现到堆栈中的任何想法？这些值应该存储在数组、列表中还是无关紧要？我是一个菜鸟，所以任何帮助将不胜感激。谢谢

4

3 回答 3

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

以下是计算斐波那契（5）的函数调用：

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

如果你把它看成一棵二叉树，他们给你的输出是一个后序树遍历，数量为 ? 是该堆栈的深度，而数字是该节点的值。

因此，只需执行函数所做的事情，每次看到 return 时，写下您返回的内容（前面有 ?）：

  • 返回的第一个函数是第一个 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)
于 2011-02-16T15:27:49.457 回答
0

将你的整个问题分解成更小的部分，这些部分可以自己解决/实施。在这种情况下，有两个主要部分：

  1. Stack -- 根据问题中给出的细节实现一个标准的堆栈类。以点的形式列出它们可能会有所帮助。
  2. 斐波那契——使用堆栈类递归地生成斐波那契数列。堆栈是本练习的存储机制。

示例输出?-?-?-1可以理解为以下堆栈操作：

push 0
push 0
push 0
push 1
print
于 2011-02-16T15:36:57.337 回答
0

我将堆栈打印留给您，并解决使用堆栈存储标记（“无意义”数字）和结果的令人困惑的部分。这是部分伪代码：

procedure fib(n)
    push a marker (say a zero) to a global stack
    if n is 1 or 2 then
        result = you_know_what
    else
        calculate fib(n-1)
        pop the stack ==> fib_n_minus_1
        calculate fib(n-2)
        pop the stack ==> fib_n_minus_2
        result = fib_n_minus_1 + fib_n_minus_2
    endif

    pop the marker off the stack and discard
    push the result into the stack
    print the stack
end fib

这里要注意的关键是 fib() 不返回值。相反，它将返回值推送到全局堆栈中。

于 2011-02-16T16:01:35.057 回答