求第n个斐波那契数列(不考虑溢出)

斐波那契数列是列如:1,2,1,3,5,8,13,21,34```````````````的数列
(1)用递归方式实现
#include <stdio.h>
#include <stdlib.h>
int Fib(int n){
if (n == 1 || n == 2){
return 1; //如果第一项和第二项是1和2,就返回1
}
return Fib(n - 1) + Fib(n - 2);
}
int main(){
printf("%d\n", Fib(6));
system(“pause”);
return 0;
}
运行结果为

用递归方式实现斐波那契数列的弊端:
1.运算速度慢,运算效率低
2.如果选择计算第100项的斐波那契数列,运算效率低,因为数列是以指数形式增长的,增长速度非常快

优化斐波那契数列(减少重复计算的次数)
(2)非递归方式(循环方式)
#include <stdio.h>
#include <stdlib.h>
int Fib(int n){
if (n == 1 || n == 2){
return 1;
}
int num1 = 1; //表示i-2项和i-1项的内容
int num2 = 1;
int result = 0; //最终第n项的结果
for (int i = 3; i <= n; ++i){
result = num1 + num2;
num1 = num2;
num2 = result;
}
return result;
}
int main(){
printf("%d\n", Fib(6));
system(“pause”);
return 0;
}
经过优化的代码,用循环方式实现的优点:
计算速度快,运行效率高
运行结果为