题目

有39级台阶，每一步只能走1阶或者2阶。
如果需要走偶数步，求上台阶的方案数。

分析

拿到题目就是一通分析，39是奇数，一次走1阶或者两阶。。。
那么就有：1*x+2y=39，x得是个奇数。。。
要求走偶数步，那y也得是奇数。。。

代码

#include <stdio.h>
int main()
{
    // 39个台阶, 分类数, 方案数
    int number = 39, count = 0;
    // 走了1阶的次数
    for(int i=0; i<=number; i++)
    {
        // 1阶偶数次的排除
        if(i%2==0)
            continue;
            
        // 2阶奇数次的留下
        if((number-i)%4!=0)
        {
            count++;
        }
    }
    printf("共有%d套方案可选择\n", count);
}

天才有木有→_→

后来才发现，自己想简单了，题目要求上台阶的方案数，上面的结果明显不是。
上面的结果只是一阶和二阶的数目，还需要对他们进行排序。。。比如：

• 1222222....
• 2122222....

是两个不同的方案。

后悔数学没学好

m个1和n个0进行排序，有多少排序方式。。。
当时就难住我了，后来求助得到答案:

int func(int m, int n)
{
   if(m==0 || n==0) return 1;
   return func(m-1, n) * (n+m)/m;
}

最终代码

#include <stdio.h>

int func(int m, int n)
{
   if(m==0 || n==0) return 1;
   return func(m-1, n) * (n+m)/m;
}

int main()
{
    // 39个台阶, 分类数, 方案数
    int number = 39, count = 0, sum = 0;
    // 走了1阶的次数
    for(int i=0; i<=number; i++)
    {
        // 1阶偶数次的排除
        if(i%2==0)
            continue;
            
        // 2阶奇数次的留下
        if((number-i)%4!=0)
        {
            count++;
            // 1阶i次, 2阶(number-i)/2次
            int ber = func(i, (number-i)/2);
            sum += ber;
            printf("分类%2d:1阶%2d次, 2阶%2d次. 共%3d种方法\n", count, i, (number-i)/2, ber);
        }
    }
    printf("共有%d类, %d套方案可选择\n", count, sum);
}

结果

图片发自简书App