三种方法求第n个斐波那契数:递归,数组,循环
斐波那契数列:
1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,418…
第一第二项是1,第三项是前两项的和1+1=2,第四项是第二第三项的和1+2=3,所以第n项是第n-1项与n-2项的和。
1.用递归求第n个斐波那契数
我们先写代码主要框架,输入一个数n,创建中间变量i,我们要一直重复 n-1项 + n-2项,直到n被求出来为止。我们可以运用for循环,循环内部调用实现相加的函数,最后将第n个数打印出来。
for(i=1;i<n;i++) { fun(i)); } printf("%d",fun(n));
接下来需要将调用函数实现写出来
int fun(int n) { if (n == 1 || n == 2) { return 1; } else { return fun(n - 1) + fun(n - 2); } }
#include<stdio.h> int fun(int n) { if (n == 1 || n == 2)//通过数列的规律发现,前两项都为1,作为递归的终止条件 { return 1; } else { return fun(n - 1) + fun(n - 2);//要求第n项,就是求n-1项和n-2项的和 } } int main() { int i, n; printf("请输入你要打印第n个斐波那契数:"); scanf("%d", &n);//n为打印的项数 printf("第n个斐波那契数:"); for (i = 1; i <= n; i++) { fun(i);//fun函数返回的是第i项,所以用for循环打印每一项 } printf("%d", fun(n)); return 0; }
2.用数组求第n个斐波那契数
由于数组下标从0开始,所以第n个数的下标是n-1
#include<stdio.h> int main() { printf("求第n个斐波那契数:"); int i = 0; int sz = 0; int n = 0; scanf("%d", &n); int a[20] = { 1,1 }; sz = sizeof(a) / sizeof a[0]; for (i = 2; i < sz; i++) { a[i] = a[i - 1] + a[i - 2]; } printf("第n个斐波那契数是:"); printf("%d", a[n-1]); return 0; }
3.用循环求第n个斐波那契数
创建一个中间变量count
n<2时,返回1,此时count为1,n==3时,count++,count为2
#include<stdio.h> int count = 0; int fib(int n) { if (n == 3) count++; if (n <= 2) return 1; else return fib(n - 1) + fib(n - 2); } int main() { printf("求第n个斐波那契数:n="); int n = 0; scanf("%d", &n); int ret = fib(n); printf("第n个斐波那契数:"); printf("%d ", ret); return 0; }
下一篇:
树、森林与二叉树的相互转换