題目
有39級臺階山析，每一步只能走1階或者2階堰燎。
如果需要走偶數(shù)步，求上臺階的方案數(shù)笋轨。
分析
拿到題目就是一通分析秆剪，39是奇數(shù)，一次走1階或者兩階爵政。仅讽。。
那么就有：1*x+2y=39钾挟，x得是個奇數(shù)洁灵。。掺出。
要求走偶數(shù)步徽千，那y也得是奇數(shù)。汤锨。双抽。
代碼
#include <stdio.h>
int main()
{
// 39個臺階, 分類數(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);
}
天才有木有→_→
后來才發(fā)現(xiàn)，自己想簡單了闲礼，題目要求上臺階的方案數(shù)荠诬，上面的結(jié)果明顯不是。
上面的結(jié)果只是一階和二階的數(shù)目位仁，還需要對他們進(jìn)行排序柑贞。。聂抢。比如：
- 1222222....
- 2122222....
是兩個不同的方案钧嘶。
后悔數(shù)學(xué)沒學(xué)好
m個1和n個0進(jìn)行排序，有多少排序方式琳疏。有决。闸拿。
當(dāng)時就難住我了，后來求助得到答案:
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個臺階, 分類數(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("分類%2d:1階%2d次, 2階%2d次. 共%3d種方法\n", count, i, (number-i)/2, ber);
}
}
printf("共有%d類, %d套方案可選擇\n", count, sum);
}
結(jié)果
圖片發(fā)自簡書App
