11

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

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

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

（以下仅供参考，长帖见谅）
（更多解释见Richard Carl Jeffrey的Formal Logic: Its Scope And Limits一书）

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

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

规则是：
1. 一台注册机使用有限数量的桶，以及无休止的弹珠供应。
2.每个桶都可以单独识别。弹珠不需要是可区分的。
3. 注册机程序是一组有限的指令：
- 将弹珠添加到桶中（然后继续执行下一条指令）。
- 或者从桶中取出一颗弹珠（如果可以的话，继续下一条指令，如果不能，则继续下一条指令）。
4. 程序可以写成流程图或指令列表。

下面是一个执行加法的寄存器机器程序的例子。
设 A、B、C 为桶。
1. (-B; 2,4) 表示从B桶中取出一颗弹子，如果可以则执行指令2，如果不能则
执行4 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(0)=0 和 F(1)=1，斐波那契递归关系为 F(n)=F(n-1)+F(n-2)。

这是我的尝试和代码：
我的想法是使用存储桶 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。

我一直在考虑这个日日夜夜，如果有人能帮助我，我将不胜感激。如果有任何不清楚的地方，请随时要求我澄清。

非常感谢提前！

4

4 回答 4

4

下面是一些 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)
于 2013-05-28T19:14:54.547 回答
2

我会对此进行破解。既然你想要机器码，最简单的事情就是编写相对低级的伪代码，然后从那里工作到机器码。您需要考虑的主要事情是如何进行if声明，如何设置一个寄存器等于另一个寄存器以及如何执行循环。

我实际上可以保证有更有效的方法来做到这一点，但这应该是一个开始。

这是我要做的伪代码，假设您已经在寄存器“n”中拥有了预期的迭代次数 > 2：

A = 0
B = 1
C = 1
DO
  A = B + C // Note, this is really A = 0, A += B, A += C
  C = B  // Similarly, C = 0, C += B
  B = A  // B = 0, B += A
WHILE N- > 0

这应该不难变成注册码：

1.   B+, 2 // B = 1
2.   C+, 3 // C = 1
3.   A-, 3, 4 // Get A down to 0 - not necessary, just here for clarity
4.   D-, 4, 5 // Get temporary variable D down to 0. - not necessary, just here for clarity
5.   B-, 6, 8 // Copy B into A (part of adding) and temporary variable D
6.     A+, 7  // A = B
7.     D+, 5  // D = B
8.   C-, 9, 10 // Add C into A = B
9.     A+, 8  // A += C
10.  N-, 11, -// Check your N count
11.    D-, 12, 13 // Copy D (the old B) into C
12.      C+, 11  // C = D
13.    A-, 14, 5 // Copy A into B
14.      B+, 13  // B = A

你可以看到我保留了两行我不需要的行，我在其中初始化了 A 和 D。由于它们从 0 开始并在每个循环中读取到 0，因此这些行是不必要的，最终结果如下：

1.   B+, 2                       // B = 1
2.   C+, 3                       // C = 1
3.   B-, 4, 6 // Copy B into A (part of adding) and temporary variable D
4.     A+, 5                     // A = B
5.     D+, 3                     // D = B
6.   C-, 7, 8 // Add C into A = B
7.     A+, 6                     // A += C
8.   N-, 9, -// Check your N count, or exit
9.     D-, 10, 11 // Copy D (the old B) into C
10.      C+, 9                   // C = D
11.    A-, 12, 3 // Copy A into B
12.      B+, 12                  // B = A

同样，我确信它并不完美，但它应该让你接近。希望这可以帮助！

编辑

重新阅读这个问题，我看到“N”以 A 开头。我的算法不适用于它，所以我需要在前面加上两行来移动它。另外，我看到我的格式与原始 OP 不匹配，所以我修改了我的格式以匹配（给出或接受间距和注释）：

1.   (-A; 2, 3) // Move the "N" value out of A into N
2.     (+N; 1)                     // N = A
3.   (+B; 4)                       // B = 1
4.   (+C; 5)                       // C = 1
5.   (-B; 6, 8) // Copy B into A (part of adding) and temporary variable D
6.     (+A; 7)                     // A = B
7.     (+D; 5)                     // D = B
8.   (-C; 9, 10) // Add C into A = B
9.     (+A; 8)                     // A += C
10.  (-N; 11, -)// Check your N count, or exit
11.    (-D; 11, 13) // Copy D (the old B) into C
12.      (+C; 11)                   // C = D
13.    (-A; 14, 5) // Copy A into B
14.      (+B; 13)                   // B = A
于 2013-05-28T19:08:31.673 回答
0

好的，我认为这会起作用（如果它没有让我知道，我会尝试修复它。）函数运行后，继续下一行（所以在 F1 运行并返回后，立即从 F2 开始）

Buckets:
A: Initial Value and Final Answer
B: First Counter
C: Second Counter
D: Adding bucket
I: Copy of C for next iteration
J: temporary bucket used for copying

1: +B,3 //loads the first counter
2: +C,4 //loads the second counter
3: -A,3,L
4: F1, 4
5: F2, 5
6: F3, 3

F1:: //makes a copy of C
  Fa: -C,Fb,Fd
  Fb: +I,Fcv //I is now the copy of C
  Fc: +J,Fa
  Fd: -J,Ff,Fg
  Ff: +C,fd
  Fg: return

F2:: //Sums B and C
  Fa: -B,Fc,Fb //adds up B 
  Fb: -C,Fd,Fe //adds up C
  Fc: +D,Fa
  Fd: +D,Fb 
  Fe: -D,Ff,Fg
  Ff: +C,Fe //Copies result to C
  Fg: return

F3:: //copys old C into B
  Fa: -I,Fb,Fc
  Fb: +B,Fa
  Fc: //return

L:: //puts value of C into A for result
  Fa: -C,Fb,DONE
  Fb: +A,Fa
于 2013-05-28T19:22:22.620 回答
0

用你可以实现的宏指令来写。

事实上，你只需要一个宏指令来完成这个任务，而且你已经有了它（加法）。将存储桶清零很简单（一个接一个地删除弹珠），将存储桶的内容复制到另一个存储桶（先清零然后添加）也是如此。

于 2013-05-28T20:46:25.267 回答