我不确定这是否是提出这个问题的正确位置,但由于它涉及编程和代码,希望这是正确的地方.
我曾尝试在程序员和计算机科学SE上发帖,但他们将我重定向到了这个网站.
问题是如何编写计算Fibonacci数的寄存器机器代码/程序.代码的语法实际上非常简单.
(以下仅供参考,对于长篇文章感到遗憾)
(有关更多说明,请参阅正式逻辑书:Richard Carl Jeffrey的范围和限制)
根据维基百科,注册机是一种类似于图灵机的抽象机的通用类.(处理器)寄存器是可用作CPU或其他数字处理器的一部分的少量存储器.
我们可以通过将寄存器建模为空桶来简化问题,我们可以将大理石或岩石放入寄存器("桶").规则是从存储桶中添加或移除弹珠以执行计算.
规则如下:
1.登记机器使用有限数量的桶和无穷无尽的大理石供应.
2.每个桶都可以单独识别.大理石无需区分.
3.寄存器机器程序是一组有限的指令:
- 将大理石添加到桶中(然后继续下一条指令).
- 或者从桶中取出大理石(如果可以的话,继续下一个指令,如果不能,则继续下一个指令).
4.程序可以用流程图或指令列表编写.
以下是执行添加的注册机程序的示例.
让A,B,C成为桶.
1.(-B; 2,4)表示从桶B中取出一个大理石,如果可以,则转到指令2,如果不能,则转到4个
.(+ 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中的5个弹珠和| B | + | C | 在桶B中= 2 + 4 = 6个弹珠
(我希望上面的例子足够清楚,仅用于说明目的)
(现在问题来了)
现在,我想编写一个寄存器机器代码,当在存储桶A中输入n时,返回(也在存储桶A中)第n个斐波纳契数.Fibonacci数字是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.
我一直想着这个日日夜夜,如果有人能帮助我,我将不胜感激.如果有任何不清楚的地方,请不要犹豫要求我澄清.
非常感谢提前!
我会尝试一下这个。既然你想要机器代码，最简单的事情就是编写相对较低级别的伪代码，然后从那里开始工作到机器代码。您需要考虑的主要事情是如何发出一条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