如何编写反向斐波那契生成器

Question

我正在尝试用 MIPS 汇编语言编写一个反向斐波那契生成器，但我真的只是在寻找逻辑，所以低级别的答案 Java 或 C++ 对我来说是可以理解的。

我只能使用一个子例程（function/method）并且不能存储序列中的任何值。该函数需要计算并打印序列。基本上，我需要使用递归函数。用户将提供一个斐波那契数，我需要生成从该数开始向下的输出。对于用户输入的任何值，我都可以访问该数字在序列中的第 n 个位置。（即 55 是第 10 个斐波那契数）

我可以使用多个函数调用在 C++ 中对此进行编码，但我很难将其简化为 MIPS 汇编语言。有没有我缺少的简单方法？

Answer 1

由于朴素的斐波那契计算是递归的，因此您需要存储数字。

不可能在第 n 个 F(n) 元素计算中途获得 F(n-2) 和 F(n-1) 元素，因为这些元素的计算将使用相同的 CPU/registers，因此CPU的中间状态必须在F(n-2)/F(n-1)调用之前存储，并在之后恢复，以继续F(n)计算。

通常在这种情况下使用堆栈，但无论如何它都是一个内存和存储中间结果。即使您只将数字保存在 CPU 寄存器中，它仍然是值的存储。所以我不确定你在任务描述中的真正限制是什么，它可能是禁止的一些特定的数字存储方式，否则对我来说没有意义。

要反转这个过程，比如 55 输入的输出 10（这就是你想要的？），你实际上可以从 F(1) 向上，只缓存最后两个结果，并且看看你什么时候 hit/overrun 输入值。

我们将序列定义为：F(n) = F(n-1) + F(n-2), F(1) = 1, F(2) = 1

算法可以是这样的：

读取输入
;计算初始化
假结果 F(n) = 1
F(n-1) = 0
F(n-2) 未初始化（在 ASM 中只需决定使用哪个寄存器来存储它并写注释）
n = 1
fibonacciLoop:;主循环
if (input == F(n))，输出 "n" 作为结果，退出（在 ASM 中执行 "go to outputFound" 并在那里写入其余代码，保持 fibonacciLoop 简短)
if (input < F(n)), output "input is between n-1 and n-th Fib number", exit (在 ASM 中做 "go to outputBetween"... 和上一步一样)
F(n-2) = F(n-1)
F(n-1) = F(n)
F(n) = F(n-1) + F(n-2)（实际上是F(n) += F(n-2)复用F(n)旧值）
incn（增量：n=n+1）
转到fibonacciLoop

尝试在头部验证算法看起来正常并做你想做的事，然后将其写入 ASM，检查 CPU 寄存器，如果你能适应这些中间值（[input , n, F(n), F(n-1), F(n-2)] ) 写入寄存器 ("allocate" 它们在你的脑海中), 然后编写指令来执行每个描述的步骤 (我想他们中的大多数已经可以通过 1-2 CPU 指令来实现了。

这个算法当然存储了 F(n-2) 和 F(n-1) 值，所以它打破了你的描述，如果从字面上看，但你可以只将它们保存在寄存器中，而不是将它们存储到内存。

编辑：输入“1”总是输出“1”，不可能输出“2”。其余的斐波那契数是唯一的。

edit2：关于 "increment"，后来我才意识到你在谈论 MIPS，它类似于 RISC（精简指令集计算），因此没有专门的 +1 inc 指令，所以你确实应该像 add r_with_n, r_with_n, #1 这样的通用加法来做 "n = n + 1".

Answer 2

static void printReverseFib(const int max, const int f1 = 0, const int f2 = 1) {
    if (f2 <= max)
        printReverseFib(max, f2, f1 + f2);
    std::cout << f1 << ' ';
}

int main() {
    printReverseFib(55);
    return 0;
}

55 34 21 13 8 5 3 2 1 1 0

如何编写反向斐波那契生成器

How to program a Reverse Fibonacci generator

java

assembly

mips