1、斐波那契数列:
又称黄金分割数列,指的是这样一个数列:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
在数学上,斐波纳契数列以如下被以递归的方法定义:F0=0,F1=1,Fn=F(n-1)+F(n-2)(n>=2,n∈N*),
即这个数列从第二项开始,每一项都等于前两项之和
特别指出:0是第0项,不是第1项
2、递归算法:
说明:程序调用自身的编程技巧称为递归( recursion)。
一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。
注意:
(1) 递归就是在过程或函数里调用自身;
(2) 在使用递增归策略时,必须有一个明确的递归结束条件,称为递归出口。
(1)用递归法求斐波那契数列并列出所有项:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
#include<stdio.h> int fun( int n) //n代表第几项。特别指出:0是第0项,不是第1项。 { if (n <= 1 ) //终止条件// return n; else return fun(n- 1 ) + fun(n- 2 ); } int main() { int n; printf( "请输入要输出多少项(自然数)斐波那契数列:" ); scanf( "%d" ,&n); //int *a = (int *)malloc((n+1)*sizeof(int));//如需存储,使用动态内存分配n+1个空间进行存储 int i; for (i = 0 ; i < n+ 1 ; i++) //输出所有项 { printf( "%d, " , fun(i)); if (i != 0 && i% 5 == 0 ) //每五项进行一次换行(第一行多一个第0项) printf( "
" ); } printf( "第 %d 项是:%d
" , n, fun(n)); //输出要求的项 return 0 ; } |
(2)用非递归算法实现:
#include<stdio.h>
int main()
{
int f[20]={1,1},i;
for(i=2;i<20;i++)
f[i]=f[i-1]+f[i-2];
for(i=0;i<20;i++)
{
printf("%d ",f[i]);
if((i+1)%5==0) //输出5个数换行//
printf("
");
}
getchar();//起延时作用 getchar是一个字符输入函数 只能接收一个字符 与之对应的是putchar 用于输出一个字符//
return 0;
}