題目

有39級(jí)臺(tái)階，每一步只能走1階或者2階。
如果需要走偶數(shù)步，求上臺(tái)階的方案數(shù)。

分析

拿到題目就是一通分析，39是奇數(shù)，一次走1階或者兩階。。。
那么就有：1*x+2y=39，x得是個(gè)奇數(shù)。。。
要求走偶數(shù)步，那y也得是奇數(shù)。。。

代碼

#include <stdio.h>
int main()
{
    // 39個(gè)臺(tái)階, 分類(lèi)數(shù), 方案數(shù)
    int number = 39, count = 0;
    // 走了1階的次數(shù)
    for(int i=0; i<=number; i++)
    {
        // 1階偶數(shù)次的排除
        if(i%2==0)
            continue;
            
        // 2階奇數(shù)次的留下
        if((number-i)%4!=0)
        {
            count++;
        }
    }
    printf("共有%d套方案可選擇\n", count);
}

天才有木有→_→

后來(lái)才發(fā)現(xiàn)，自己想簡(jiǎn)單了，題目要求上臺(tái)階的方案數(shù)，上面的結(jié)果明顯不是。
上面的結(jié)果只是一階和二階的數(shù)目，還需要對(duì)他們進(jìn)行排序。。。比如：

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

是兩個(gè)不同的方案。

后悔數(shù)學(xué)沒(méi)學(xué)好

m個(gè)1和n個(gè)0進(jìn)行排序，有多少排序方式。。。
當(dāng)時(shí)就難住我了，后來(lái)求助得到答案:

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個(gè)臺(tái)階, 分類(lèi)數(shù), 方案數(shù)
    int number = 39, count = 0, sum = 0;
    // 走了1階的次數(shù)
    for(int i=0; i<=number; i++)
    {
        // 1階偶數(shù)次的排除
        if(i%2==0)
            continue;
            
        // 2階奇數(shù)次的留下
        if((number-i)%4!=0)
        {
            count++;
            // 1階i次, 2階(number-i)/2次
            int ber = func(i, (number-i)/2);
            sum += ber;
            printf("分類(lèi)%2d:1階%2d次, 2階%2d次. 共%3d種方法\n", count, i, (number-i)/2, ber);
        }
    }
    printf("共有%d類(lèi), %d套方案可選擇\n", count, sum);
}

結(jié)果

圖片發(fā)自簡(jiǎn)書(shū)App