斐波那契数列

l  问题

斐波那契数列指的是这样一个数列:1123581321、……

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

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

l  思路

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

1.  定义斐波那契数列的个数。

2.  使用递推算法,声明一个只有两个成员,成员值都为1的数列,循环N2次,循环体中将数列的倒数第一项和倒数第二项相加的和追加到数列末尾。

3.  使用递归算法,声明两个参数ab,分别赋值为01,循环N次,递归计算ab,计算新b=a+b,把旧b赋给新a,返回新a作为结果数列的成员。

4.  使用集算器子程序,参数为N,当数列个数小于等于2的时候返回[1,1],结束计算;当数列个数大于2时,递归调用子程序,将最后两项的和追加到数列的末尾,递归至数列个数等于2时结束。

l  代码

 

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

 

 

声明两个参数,分别赋值为01

7

=A1.((b=a+b,a=b-a))

 

 

循环A1次,递归计算ab,计算新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中,直到A102才停止

 

l  结果