如何编程反向Fibonacci生成器

由于朴素的Fibonacci计算是递归的,因此需要存储数字。

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

通常在这种情况下使用堆栈,但它是一个内存,用于存储中间结果。即使您只在CPU寄存器中保存数字,它仍然是值的存储。因此,我不确定任务描述中的真正约束是什么,可能是某种特定的数字存储方式被禁止,否则对我来说没有意义。

反转过程,如输出 10 对于 55 输入(这就是你想要的?),实际上,您可以从F(1)向上,只缓存最后两个结果,并查看何时命中/超出输入值。

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

算法可以是这样的:

1. 读取输入
2. ; 计算初始化
3. 假结果F(n)=1
4. F(n-1)=0
5. F(n-2)未初始化(在ASM中,只需决定将使用哪个寄存器存储它并编写注释)
7. fibonacciLoop: ; 主回路
8. 如果(input==F(n)),则输出“n”作为结果,退出(在ASM中执行“转到outputFound”并在那里编写其余代码,保持 fibonacciLoop 短)
9. 如果(输入
10. F(n-2)=F(n-1)
11. F(n-1)=F(n)
12. F(n)=F(n-1)+F(n-2)(实际上,F(n)+=F(n-2)重复使用F(n)旧值)
13. inc n(增量:n=n+1)
14. 去 纤维环

尝试在头中验证算法看起来正常,并执行您想要的操作,然后将其写入ASM,检查CPU寄存器,如果您可以匹配这些中间值([ input , n , F(n) , F(n-1) , F(n-2) ])写入寄存器(“在您的头脑中分配”),然后编写指令以执行所描述的每个步骤(我认为其中大部分可以通过1-2个CPU指令实现)。

编辑:对于输入“1”,它将始终输出“1”,不可能输出“2”。其余的斐波那契数是唯一的。

edit2:关于“增量”,后来我意识到你在谈论MIPS,它类似于RISC(精简指令集计算),因此没有专门的+1 股份有限公司 指令,因此实际上您应该像 add r_with_n, r_with_n, #1 做“n=n+1”。

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