ACM题目 英雄护美（递归）

/*
                               英雄护美    英雄救美，可以理解；英雄护美，亦可理解。m（1<=m<=54）个英雄和美晚上行军，路
过大峡谷，只能以纵队的方式前行。为确保美的绝对安全，纵队中每两个美之间必须至少有
一个以上的英雄。如m为3时，有5种行军方式，分别为：美-英雄-美、美-英雄-英雄、英雄
-美-英雄、英雄-英雄-美、英雄-英雄-英雄。若给出欲穿越大峡谷的人数，有多少种英雄
护美的行军方式？
    输入第一行为一个整数n，表示测试的个数，接下来为n个测试，每个测试占一行，为1
 个整数m，表示欲穿越大峡谷的人数。
     每个测试输出一行，为一个整数，即英雄护美的不同行军方式的数量。Sample Input：
 2
 3
 1Sample Output：
 5
 2解答：
 题目好像有问题，暂且认为只有一个美女的时候她不需要人陪 
 0表示美女 1表示帅哥  m表示总人数 
 m：  1  2  3  4
   0  00  000  0000
   1  01  001  0001
       10  010  0010
             100  0100
             101  0101
                    1000 
                    1001
                    1010
 从小到大找，不能出现两个1相邻的情况 
 每次增加一个人，增加的人可能是帅哥（0）也可能是美女（1） 
 如果是0，可以加在m-1的前面，所有的情况都符合条件
 如果是1,1的下一位一定是0，加在m-2的前面 
 这些就是所有的情况        
 */
 #include <stdio.h>
 int fun(int m) ;
 int main()
 {
     int test;
     int m;
     scanf("%d",&test);
     while(test--)
       {
           scanf("%d",&m);
           printf("%d\n",fun(m));
       }
     return 0;
 }
 int fun(int m)
 {
     if(m==1) return 2;
     if(m==2) return 3;
     else return fun(m-1)+fun(m-2);
 }