C語言青蛙跳台問題

一、問題

一隻青蛙跳n個台階，每次隻能跳1個台階或者2個台階，請問一個有多少種跳法？

二、分析

①當n=1時，青蛙隻有1種跳法，隻跳1步；

②當n=2時，青蛙有兩種跳法，跳2個1步據哦這跳2個1步；

③當n>2時，青蛙第一步有兩種跳法，要麼跳1步，要麼跳2步，

如果先跳1步，接下來的跳法數量與n-1個台階跳法相同；

如果先跳2步，接下來的跳法數量與n-2個台階跳法相同；

那麼n個台階的跳法，就等于n-1個台階跳法和n-2個台階跳法之和；

n-1又可以拆分成n-2和n-3；n-2又可拆分成n-3和n-4；

如此拆分下去，直到n-x=1，或者n-x=2，傳回值1或者2從此算出n個台階的跳法

三、算法

像這種拆分問題首先想到的就是函數的遞歸

先寫出主函數：

int main()
{
 int n = 0,m=0;//n來存放台階數，m來存放跳法數
  printf("請輸入台階數:<");
  scanf("%d",&n);
  m=fun1(n);//m的值用自定義函數fun1來算取
  printf("共有%d種算法\n",m);
  return 0;
}      

這時去寫自定義fun1函數

int fun1(int n)
{
if(n<=1)//友善n=2時計算
  return 1;
 else
   return fun1(n-1)+fun1(n-2);//根據分析的圈3
}      

這個問題其實也就是一個斐波那契數列，下一位數等于前兩位數相加；

1 1 2 3 5 8 13 21 34 55·········