C语言面试经典题目：[1]斐波那契数列

1、一、斐波那契数列。

      斐波那契数列是什么这里就不再赘述了，我介绍一下经常见到的其衍生题。比如一次登一个或两个台阶，问登n个台阶有多少种可能？青蛙一次跳一下或两下，问跳n下有几种可能？铺地砖问题等等都是使用斐波那契数列解决。

2、二、斐波那契数列的求解。

      对于斐波那契数列，我们往往采用递归的思想进行求解，求解方案很简单，编码如下：

3、三、n种解法的列举。

      对于斐波那契数列，求出其种类数比较简单，如何列举出每种可能的组合呢？

4、四、n种解法的实现。

      在这里我们用回溯法对n种解法进行列举，具体实现代码如下：

5、五、综合解析。

      整体代码的实现：

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

static int step[128];

static int m = 1;

int count(unsigned int n);

void cout(int n,int t);

int main()

{

int a;

    unsigned int n;

    while(1){

printf("请输入需要登上的台阶数量：");

scanf("%d",&n);

a = count(n);

printf("登上%d个台阶共有%d种方法！分别如下：\n",n,a);

cout(n,0);

                m=1;

    }

system("pause");

return 0;

}

int count(unsigned int n)

{

    if(n == 1)

        return 1 ;

    if(n == 2)

        return 2 ;

    else 

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

}

void cout(int n,int t)

{

    int i,j;

    if(n<0)

    return ;

if(n == 0)

    {

printf("第%d种方法：",m);

for(j=0;j<t;j++)

            printf("%d ",step[j]);

m++;

printf("\n");

    }

    else

    {

for(i=1;i<=2;i++)

{

step[t] = i;

cout(n-i,t+1);

}

    }

}

6、六、运行情况一。

7、七、运行情况二。