开封
乾学院 6 号会员
1 回帖  •  129 浏览  • 
     ...

斐波那契数列

 
习题(31)

问题

斐波那契数列指的是这样一个数列：1、1、2、3、5、8、13、21、……

这个数列从第三项开始，每一项都等于前两项之和。

请输出这个数列的前 N 项，分别使用递推和递归以及集算器的序列配合 insert 函数三种算法来实现。

思路

大致思路：定义一个序列，将前两项赋值为 1，然后循环 N 次，分别取倒数第一项和倒数第二项，将其相加的和合并到序列中，结果即为所生成的斐波那契数列。

  1. 定义斐波那契数列的个数。
  2. 使用递推算法，声明一个只有两个成员，成员值都为 1 的数列，循环 N 减 2 次，循环体中将数列的倒数第一项和倒数第二项相加的和追加到数列末尾。
  3. 使用递归算法，声明两个参数 a 和 b，分别赋值为 0 和 1，循环 N 次，递归计算 a 和 b，计算新 b= 旧 a+ 旧 b，把旧 b 赋给新 a，返回新 a 作为结果数列的成员。
  4. 使用集算器子程序，参数为 N，当数列个数小于等于 2 的时候返回 [1,1], 结束计算；当数列个数大于 2 时，递归调用子程序，将最后两项的和追加到数列的末尾，递归至数列个数等于 2 时结束。

代码

A B C
1 30 声明斐波那契数列的个数
2 / 递推法
3 =[1,1] 定义数列
4 for A1-2 =A3.m(-1)+A3.m(-2) >A3=A3|B4 循环 A1-2 次，将数列 A3 中的倒数第一项和倒数第二项相加，和追加到 A3 中
5 / 递归法
6 >a=0,b=1 声明两个参数，分别赋值为 0 和 1
7 =A1.((b=a+b,a=b-a)) 循环 A1 次，递归计算 a 和 b，计算新 b= 旧 a+ 旧 b，把旧 b 赋给新 a，返回新 a 作为结果数列的成员
8 / 集算器函数，参数为数列的个数
9 =func(A10,A1) 调用 A10 子程序，参数值为 A1
10 func if A10<=2 return A10*[1] 循环参数值，当参数值小于等于 2 时返回数列 [1,1]
11 =func(A10,A10-1) return B11 | (B11.m(-1) + B11.m(-2)) 递归调用 A10 子程序，把最后两项的和叠加到 B11 中，直到 A10 为 2 才停止

结果

imagepng

习题(31)