algorithm - 如何为 Fibonacci 编写寄存器机器代码

Question

我不确定在这里问这个问题是否合适，但由于它涉及编程和代码，希望这是正确的地方。

我曾尝试在 Programmers 和 Computer Science SE 上发帖，但他们将我重定向到此站点。

问题是关于如何编写计算斐波那契数的寄存器机器代码/程序。代码的语法实际上非常简单。

(以下内容仅供引用，文章过长请见谅)
(有关更多解释，请参阅 Richard Carl Jeffrey 的《形式逻辑:它的范围和限制》一书)

根据维基百科，寄存器机是抽象机的通用类，其使用方式类似于图灵机。 (处理器)寄存器是作为 CPU 或其他数字处理器的一部分可用的少量存储空间。

我们可以通过将寄存器建模为空桶来简化问题，我们可以将弹珠或石头放入寄存器(“桶”)中。规则是从桶中添加或移除弹珠以执行计算。

规则是:
1. 注册机使用有限数量的桶和源源不断的弹珠。
2.每个桶都可以单独标识。弹珠不需要区分。
3. 寄存器机程序是一组有限的指令:
- 将大理石添加到桶中(然后继续执行下一条指令)。
- 或者从桶中取出一颗弹子(然后继续下一个 如果可以，请提供指导；如果不能，请提供其他指导)。
4. 程序可以写成流程图或指令列表。

下面是一个执行加法的寄存器机程序的例子。
设 A、B、C 为桶。
1. (-B; 2,4) 表示从桶B中拿走一颗弹子，如果可以则转到指令2，如果不能则转到指令4
2. (+A; 3) 表示向桶A中添加一颗弹子，然后转到指令3
3. (+C; 1) 表示向桶C中添加一颗弹子，然后转到指令1
4. (-C; 5,-)表示从C桶中拿走一颗弹子，可以走指令2，不行就退出
5. (+B; 4) 表示向桶B中添加一颗弹子，然后转到指令4

很容易证明，假设我们在桶A中有3个弹珠，在桶B中有2个弹珠，在桶C中有4个弹珠。执行此算法后，将有|A|+|B|。 = 3+2 = 桶 A 和 |B|+|C| 中有 5 个弹珠= 2+4 = B 桶中有 6 个弹珠。

(我希望上面的例子足够清楚以供说明)

(问题来了)

现在，我想编写一个寄存器机器代码，当在桶 A 中输入 n 时，返回(也在桶 A 中)第 n 个斐波那契数。斐波那契数是 0(第 0 个)、1(第 1 个)、1 = 0 + 1(第 2 个)等。我们可以使用任意数量的桶，目标是编写尽可能简单的代码(即使用最少的指令)。斐波那契递归关系是 F(n)=F(n-1)+F(n-2)，给定 F(0)=0 和 F(1)=1。

这是我的尝试和代码:
我的想法是使用桶 A 作为输入，最后作为输出 F(n)(因为问题需要桶 A 中的输出)，桶 B 作为“计数器”，桶 C 作为 F(n-1) 和桶 D作为 F(n-2)。
1. (+C; 2)
2. (-A; 3,4)
3. (+B; 2)
4. (-D; 5,7)
5. (+A; 4)
6. (-C; 5,7)
7. (-B; 6,-)

但遗憾的是，我的代码最多只适用于 n=2，我正在努力使代码适用于任何 n>2。

这几天几夜我都在想，如果有人能帮我解决这个问题，我将不胜感激。如果有任何不清楚的地方，请随时向我询问。

非常非常感谢!

Answer 1

下面是一些示例 Python 代码，用于模拟在 11 条指令中完成任务的寄存器机:

# Store loop counter in 4
# Store F(n) in 1
# Store F(n+1) in 2
# Redistribute 2 to 1 and 3 to get F(n+1)+F(n),0,F(n+1)
# then move back to the order F(n+1),F(n+1)+F(n),0
code={1:(-1,2,3),   # Move n to 
      2:(+4,1),     #    bin 4 to act as loop counter
      3:(+2,4),     # Initialise bin 2 with F(1)=1
      4:(-4,5,0),   # Check for completion
      5:(-2,6,8),   # redistribute F(n+1)
      6:(+1,7),     #    to bin 1
      7:(+3,5),     #    and bin 3
      8:(-1,9,10),  # Move bin 1 to
      9:(+2,8),     #    bin 2
      10:(-3,11,4), # and bin 3
      11:(+1,10)}   #    to bin 1

def fib(n):
    buckets=[0,n,0,0,0]
    instruction_pointer = 1
    while instruction_pointer:
        ins = code[instruction_pointer]
        x = ins[0]
        if x>0:
            buckets[x]+=1
            instruction_pointer = ins[1]
        else:
            x=-x
            if buckets[x]>0:
                buckets[x]-=1
                instruction_pointer = ins[1]
            else:
                instruction_pointer = ins[2]
    return buckets[1]

for n in xrange(10):
    print n,fib(n)