斐波纳契数列 1,1,2,3,5,8,13,21,34,55,89……这个数列则称为“斐波纳契数列”,其中每个数字都是“斐波纳契数”。
输入:一个整数N(N不能大于40)
输出:由N个“斐波纳契数”组成的“斐波纳契数列”。
样例输入:6
样例输出:1 1 2 3 5 8
规律:当前数=前一个数+前前一个数。如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;
- }
-
运行结果为: