斐波那契数列

下列程序输出：67

#include<stdio.h>

int cnt = 0;

int fib(int n)
{
    cnt++;
    if(n == 0)
        return 1;
    else if(n == 1)
        return 2;
    else
        return fib(n-1) + fib(n-2);    
}    

void main()
{
    fib(8);
    printf("%d", cnt);
}

解析：

解法1：

f(n)=0, cnt自加一次，f(n)=1, cnt自加一次，即：

n=0    cnt = 1;

n=1    cnt = 1;

n=2    cnt = f(1) + f(0) = 1+1+1 = 3;

n=3    cnt = f(2) + f(1) = 3+1+1 = 5;

n=4    cnt = f(3) + f(2) = 5+3+1 = 9;

n=5    cnt = f(4) + f(3) = 9+4+1 = 15;

n=6    cnt = f(5) + f(4) = 15+9+1 = 25;

n=7    cnt = f(6) + f(5) = 15+25+1 = 41;

n=8    cnt = f(7) + f(6) = 41+25+1 = 67;

所以最后输出：67

解法2：

观察题目fib(n) = fib(n-1) + fib(n-2)，类似于斐波那契数列，所以也可直接写出答案：

数列为：1 ， 1 ， (1+1+1) ， (3+1+1) ， (5+3+1) ， (9+5+1) ， (15+9+1) ， (25+15+1) ， (41+25+1) = 67;

斐波那契数列

原文：https://www.cnblogs.com/MrRS/p/9071453.html