【经典问题】斐波纳契数列

1、题目

斐波纳契数列 1，1，2，3，5，8，13，21，34，55，89……这个数列则称为“斐波纳契数列”，其中每个数字都是“斐波纳契数”。

1.1 输入与输出

输入：一个整数N(N不能大于40)

输出：由N个“斐波纳契数”组成的“斐波纳契数列”。

1.2 样例输入与输出

样例输入：6

样例输出：1 1 2 3 5 8

2、代码

规律：当前数=前一个数+前前一个数。如2=1+1, 5=3+2, 8=5+3。有两种方法求解，一种方法是使用迭代法，另一种方法是通过递归的方式。完整代码如下：

/*******************************************************************************************************
** 题    目: 斐波纳契数列1，1，2，3，5，8，13，21，34，55，89……	
			 这个数列则称为“斐波纳契数列”，其中每个数字都是“斐波纳契数”。
** 输    入: 一个整数N(N不能大于40)
** 输    出: 由N个“斐波纳契数”组成的“斐波纳契数列”。
** 样例输入：6    
** 样例输出：1 1 2 3 5 8 
********************************************************************************************************/
#include <stdio.h>
#include <string.h>

#define  Method   0  // 1：迭代法  0：递归法

#if Method 
// 方法一：迭代法
long fibonacci(int n)
{
    if (n <= 2)
    {
        return 1;
    }

    long result;
    long pre_result;
    long pre_pre_result;
 
    pre_result = pre_pre_result = 1;
 
    while (n > 2)
    {
        result = pre_result + pre_pre_result;
        pre_pre_result = pre_result;
        pre_result = result;
        n--;
    }

    return result;
}
#else 
// 方法二：递归法
long fibonacci(int n)
{
    if (n <= 2)
	{
        return 1;
	}

    return fibonacci(n - 1) + fibonacci(n - 2);

}
#endif

// 主函数
int main(void)
{
    int N;

    scanf("%d", &N);
    int i;

    for (i = 1; i <= N; i++)
    {
        printf("%ld ", fibonacci(i));
    }

    return 0;
}

运行结果为：