mips斐波那契数列
斐波拉契数列（两种实现方式：迭代和递归）
1.说明设计思想，给出伪代码、寄存器使用对照表
2.有注释的程序源代码，注释和伪代码对应
以下是使用C语言实现斐波那契数列的迭代和递归两种方式的代码和说明。
- 迭代方式实现斐波那契数列
设计思想：
使用循环迭代的方式计算斐波那契数列。
通过迭代更新前两个斐波那契数，并计算下一个斐波那契数。
伪代码：
1. 初始化变量a = 0，b = 1，fib = 0
2. 输入斐波那契数列长度n
3. 打印斐波那契数列的前两个数字0和1
4. 循环从i = 2到n-1：
5. fib = a + b
6. 打印fib
7. a = b
8. b = fib
寄存器使用对照表：
a: 存储前一个斐波那契数
b: 存储当前斐波那契数
fib: 存储下一个斐波那契数
2. 迭代方式的源代码
#include <stdio.h>
void fibonacciIterative(int n) {
int a = 0, b = 1, fib;
printf("Fibonacci series: %d %d ", a, b);
for (int i = 2; i < n; i++) {
fib = a + b;
printf("%d ", fib);
a = b;
b = fib;
}
}
int main() {
int n;
printf("Enter the length of Fibonacci series: ");
scanf("%d", &n);
fibonacciIterative(n);
return 0;
}
注释和伪代码对应说明：
fibonacciIterative 函数实现了迭代方式计算斐波那契数列。
在 main 函数中，我们输入斐波那契数列的长度 n，然后调用 fibonacciIterative 函数打印斐波那契数列。
3. 递归方式实现斐波那契数列
设计思想：
使用递归的方式计算斐波那契数列。
基本情况是当序号为0或1时，直接返回对应的数字。
递归情况是通过递归调用前两个序号的斐波那契数的和来计算当前序号的斐波那契数。
伪代码：
1. 定义函数fibonacciRecursive(n)：
2. 如果n为0，返回0
3. 如果n为1，返回1
4. 否则，返回fibonacciRecursive(n-1) + fibonacciRecursive(n-2)
寄存器使用对照表：
无特定寄存器使用。
4. 递归方式的源代码
#include <stdio.h>
int fibonacciRecursive(int n) {
if (n == 0)
return 0;
else if (n == 1)
return 1;
else
return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}
int main() {
int n;
printf("Enter the length of Fibonacci series: ");
scanf("%d", &n);
printf("Fibonacci series: ");
for (int i = 0; i < n; i++) {
printf("%d ", fibonacciRecursive(i));
}
return 0;
}
注释和伪代码对应说明：
fibonacciRecursive 函数实现了递归方式计算斐波那契数列。
在 main 函数中，我们输入斐波那契数列的长度 n，然后通过循环调用 fibonacciRecursive 函数打印斐波那契数列。
以上是使用C语言实现斐波那契数列的迭代和递归两种方式的代码和说明。
- 这篇博客: 基于MIPS指令集的单周期处理器设计中的 三、汇编代码及机器码 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
根据C语言编写MIPS汇编程序如下所示：
add $t0,$zero,$zero #寄存器$t0代表变量i,并初始化为0 add $t1,$zero,$zero #寄存器$t1代表变量j,并初始化为0 addi $t2,$zero,0#寄存器$t2存储着字符数组array的基地址0 addi $t3,$zero,8 #寄存器$t3存储着字符数组new_array的基地址8 addi $t4,$zero,16 #寄存器$t4存储着int数组count的基地址16 addi $s0, $zero, 1 #$s0存放常数1 addi $s1, $zero, 4 #$s1存放常数4 #对数组array进行循环移位得到新的数组new_array loop1: add $t5, $t0, $t2 #将array[i]的地址放入$t5中 addi $t6, $t5, 1 #将array[i+1]的地址放入$t6中 add $t7, $t0,$t3 #将new_array[i]的地址放入$t7中 lb $t8, 0($t5) #将array[i]存入$t8的低8位 lb $t5, 0($t6) #将array[i+1]存入$t5的低8位 sllv $t8, $t8, $s1 #将array[i]逻辑左移4位后放入$t8中 srlv $t5, $t5, $s1 #将array[i+1]逻辑右移4位后放入$t5中 or $t5, $t5, $t8 #将移位后的array[i]和array[i+1]按位或后放入$t5中 sb $t5, 0($t7) #将$t5的低8位放入内存中new_array[i]位置上 addi $t0, $t0, 1 # i++ addi $a3, $zero, 6 slt $t5, $a3,$t0 #若6 < i即i > =7，则$t5置1 beq $t5, $zero,loop1 #若i <7,则继续循环 lb $t5, 7($t2) #将array[7]从内存中取出，放入$t5的低8位 lb $t6, 0($t2) #将array[0]从内存中取出，放入$t6的低8位 sllv $t5, $t5, $s1 srlv $t6, $t6, $s1 or $t5, $t5, $t6 sb $t5, 7($t3) #存入new_array[7]的值 #计算新数组new_array中每个字符的1的个数，并存入数组count add $t0,$zero,$zero #前一次循环中i的值被改变，现在要重新置0 loop2: add $t5, $t0, $t4 #将count[i]的地址放入$t5中 add $t6, $t0, $t3 #将new_array[i]的地址放入$t6中 add $s2, $zero, $zero #$s2寄存器暂时存放计数结果 add $t1, $zero, $zero #每次进入循环前将j置0 loop3: sllv $t7, $s0, $t1 #$t7存放1左移j位的结果 lb $t8, 0($t6) #将new_array[i]存入$t8的低8位 and $t7, $t7, $t8 beq $t7, $zero, else addi $s2, $s2, 1 #count++ else: sb $s2,0($t5) #将计数结果存入内存的count[i]对应的位置上 addi $t1, $t1, 1 #j++ addi $a3, $zero, 7 slt $t9, $a3, $t1#若j > 7,则$t9置1 beq $t9, $zero, loop3 addi $t0, $t0, 1 #i++ addi $a3, $zero, 7 slt $t5, $a3, $t0 #若i<8,则$t5置1 beq $t5, $zero, loop2为了能在MARS仿真器上运行上述MIPS汇编代码，需对汇编代码进行更改：将数组首地址更改为可访问的数据段，并加入将”a,b,c,d,e,f,g,h”存入内存中的汇编语言，具体修改内容如下：
add $t0,$zero,$zero #寄存器$t0代表变量i,并初始化为0 add $t1,$zero,$zero #寄存器$t1代表变量j,并初始化为0 addi $t2,$zero,0x10010000 #寄存器$t2存储着字符数组array的基地址0 addi $t3,$zero,0x10010008 #寄存器$t3存储着字符数组new_array的基地址8 addi $t4,$zero,0x10010010 #寄存器$t4存储着int数组count的基地址16 addi $s0, $zero, 1 #$s0存放常数1 addi $s1, $zero, 4 #$s1存放常数4 #依次将"a,b,c,d,e,f,g,h"存入数组array中 addi $a0, $zero, 0x61 #"a"的ASCII码 loop: add $t5, $t0, $t2 #将array[i]的地址放入$t5中 add $t6, $a0, $t0 #要存入array[i]的字符 sb $t6, 0($t5) #依次将"a,b,c,d,e,f,g,h"存入array[i]中 addi $t0, $t0, 1 #i++ addi $a3, $zero, 7 slt $t5, $a3, $t0 #若i<8,则$t5置1 beq $t5, $zero, loop #对数组array进行循环移位得到新的数组new_array add $t0,$zero,$zero #前一次循环改变了i的值,再次进入循环后重新将i置0 loop1: add $t5, $t0, $t2 #将array[i]的地址放入$t5中 addi $t6, $t5, 1 #将array[i+1]的地址放入$t6中 add $t7, $t0,$t3 #将new_array[i]的地址放入$t7中 lb $t8, 0($t5) #将array[i]存入$t8的低8位 lb $t5, 0($t6) #将array[i+1]存入$t5的低8位 sllv $t8, $t8, $s1 #将array[i]逻辑左移4位后放入$t8中 srlv $t5, $t5, $s1 #将array[i+1]逻辑右移4位后放入$t5中 or $t5, $t5, $t8 #将移位后的array[i]和array[i+1]按位或后放入$t5中 sb $t5, 0($t7) #将$t5的低8位放入内存中new_array[i]位置上 addi $t0, $t0, 1 # i++ addi $a3, $zero, 6 slt $t5, $a3,$t0 #若6 < i即i > =7，则$t5置1 beq $t5, $zero,loop1 #若i <7,则继续循环 lb $t5, 7($t2) #将array[7]从内存中取出，放入$t5的低8位 lb $t6, 0($t2) #将array[0]从内存中取出，放入$t6的低8位 sllv $t5, $t5, $s1 srlv $t6, $t6, $s1 or $t5, $t5, $t6 sb $t5, 7($t3) #存入new_array[7]的值 #计算新数组new_array中每个字符的1的个数，并存入数组count add $t0,$zero,$zero #前一次循环中i的值被改变，现在要重新置0 loop2: add $t5, $t0, $t4 #将count[i]的地址放入$t5中 add $t6, $t0, $t3 #将new_array[i]的地址放入$t6中 add $s2, $zero, $zero #$s2寄存器暂时存放计数结果 add $t1, $zero, $zero #每次进入循环前将j置0 loop3: sllv $t7, $s0, $t1 #$t7存放1左移j位的结果 lb $t8, 0($t6) #将new_array[i]存入$t8的低8位 and $t7, $t7, $t8 beq $t7, $zero, else addi $s2, $s2, 1 #count++ else: sb $s2,0($t5) #将计数结果存入内存的count[i]对应的位置上 addi $t1, $t1, 1 #j++ addi $a3, $zero, 7 slt $t9, $a3, $t1#若j > 7,则$t9置1 beq $t9, $zero, loop3 addi $t0, $t0, 1 #i++ addi $a3, $zero, 7 slt $t5, $a3, $t0 #若i<8,则$t5置1 beq $t5, $zero, loop2在Mars中运行汇编代码结果如下：
根据以上运行结果可知，编写的汇编程序实现了要求的功能。再将汇编语言转化位机器码，如下图所示：
存入的最后一条指令是ffff_ffff，是自定义的停机指令，当遇到停机指令时pc不再更新，数据存储器和寄存器堆也不能写入数据。