©2020-2024 ioDraw All rights reserved,
Privacy Policy
习题 使用函数输出指定范围内的Fibonacci数
本题要求实现一个计算Fibonacci数的简单函数，并利用其实现另一个函数，输出两正整数m和n（0<m≤n≤10000）之间的所有Fibonacci数。所谓Fibonacci数列就是满足任一项数字是前两项的和（最开始两项均定义为1）的数列。
函数接口定义：
int fib( int n ); void PrintFN( int m, int n );
其中函数fib须返回第n项Fibonacci数；函数PrintFN要在一行中输出给定范围[m,
n]内的所有Fibonacci数，相邻数字间有一个空格，行末不得有多余空格。如果给定区间内没有Fibonacci数，则输出一行“No Fibonacci
number”。
迭代法：使用循环结构
#include <stdio.h> int fib( int n ); void PrintFN( int m, int n ); int
main() { int m, n, t; scanf("%d %d %d", &m, &n, &t);
printf("fib(%d) = %d\n", t, fib(t)); PrintFN(m, n); return 0; } int
fib( int n ) { int front=1,back=1,sum=0; if(n==1||n==2)
return 1; for(int i=3;i<=n;i++) { sum=front+back;
front=back; //相当于两个指针，往后移 back=sum; } return sum;
//若用递归，则很快：return fib(n-1)+fib(n-2) } void PrintFN( int m, int n ) {
int i=1; int count=0; while(fib(i)<=n)
//使用fib(i)判断可以大大减少检验的数 { if(fib(i)>=m&&fib(i)<=n)
{ count++; if(count==1)
printf("%d",fib(i)); else printf(" %d",fib(i));
} i++; } if(count==0) printf("No Fibonacci
number\n"); }
递归法：
//省区main函数和print函数 int fib(int n) { /*if(n==0) return 0; else if(n==1) return
1; */ if(n<2) return n==0?0:1; return fib(n-1)+fib(n-2); }
时间复杂度：
总结：
对比两种实现斐波那契的代码----迭代法和递归法
两者的区别是：迭代使用的是循环结构，递归使用的是选择结构。递归能使程序的结构更消晰、更简洁、更容易让人理解，从而减少读懂代码的时间。
但是大量的递归调用会建立函数的副本，会耗费大量的时间和内存。迭代则不需要反复调用函数和占用额外的内存。因此我们应该视不同情况选择不同的代码实现方式。