求斐波那契数列

  • 使用递归的方法 
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
//求第 n 个斐波那契数列：1 1 2 3 5 8 13 21 34 55 89 .。。。
//  递归法：                    fib(n)     n<2     1
//                                        n>2     fib(n-1)+fib(n-2)
#include <stdio.h>
#include <stdlib.h>
int to_fib(int n)
{
	if (n <= 2) 
	{
		return 1;
	}
	else 
	{
		return to_fib(n - 1) + to_fib(n - 2);
	}
}
int main() 
{
	int n=0;
	int ret=0;
	scanf("%d",&n);
    ret = to_fib(n);
	printf("%d\n", ret);
	system("pause");
	return 0;
}

  • 非递归法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    int   to_fib(n)
    {
    	int i;
    	int a = 1;
    	int b = 1;
    	int c = 1;
    	for (i = 0; i < n - 2; i++)
    	{
    		c = a + b;
    		a = b;
    		b = c;
    	}
    	return c;
    }
    int main()
    {
    	int n = 0;
    	int ret = 0;
    	scanf("%d", &n);
    	ret = to_fib(n);
    	printf("%d\n", ret);
    	system("pause");
    	return 0;
    }