博客

#include<stdio.h>
int com(int a, int b)//高中学的排列组合中的组合C(a b)，下面有一张图。
{
	int mother = 1, son = 1;//mother是图片中分母的值。son是图片中分子的值。
	int k = a;//因为a存的值，既要用来决定循环次数，又要参与分母的运算，所以用另一个变量k保存a的值来判断循环次数。
	for (int i = 0; i < k; i++)//求分母的值，分母中有几个数相乘就循环几次。
	{
		mother = mother * a;
		a--;
	}
	for (int i = 0; i < k; i++)//求分子的值，分母中有几个数相乘就循环几次。
	{
		son = son * b;
		b--;
	}
	return son / mother;//因为是组合，所以不可能为小数。
}
int main()
{
	int n = 0, sum = 0;//sum表示走的方法数。
	scanf("%d", &n);//总共n个台阶
	int T1 = n % 2;//走1个台阶的步数
	int T2 = n / 2;//走2个台阶的步数
	int k = T2;//T2存的值既要参与sum的运算，又要决定循环次数，所以用另一个变量k存T2的值来决定循环次数。
	for (int i = 0; i < k + 1; i++)//k之所以加1，是因为在最初时，没有拆【2台阶】情况下，可能存在有一个【1台阶】的情况。也可能存在没有【1台阶】的情况，没有【1台阶】com函数返回的是1，表示全是【2台阶】的一次走法。
	{
		sum = sum + com(T1, T1 + T2);//T1为0时，sum就为1。T1不为0，com就算有几种插入方式。
		T2--;
		T1 += 2;
	}
	printf("%d", sum);
	return 0;
}
//将 一步走一个台阶 表示为【1台阶】，将 一步走两个台阶 表示为【2台阶】。
//假设走T1个【1台阶】再走T2个【2台阶】就能走完。
//那么把每走一步，假设成一个【】，【】中可以存放 1台阶，也可以存放 2台阶。
//总共有T1+T2个【】，将T1个 1台阶 插入到T1+T2个【】中去，剩下的【】全部放 2台阶
//com（a,b）就是计算 有b个【】时，插入a个 1台阶 会有几种插法。

//先从【2台阶】最多的走法开始算sum，然后再把【2台阶】拆掉一个变成两个【1台阶】计算com加到sum中，依次拆【2台阶】

1.n个台阶比作n个格子

2.一步走1台阶类比为走1个格，一步走2台阶类比为走2个格子。

3.将1个格子作为一组，用“【1格】“来表示。将2个格子作为一组，用“【2格】“来表示。

4.那么占用n个格子就需要 多个【1格】和多个【2格】

5.假设需要T1个【1格】和T2个【2格】。

6.那么就是对T1个【1格】和T2个【2格】进行排列组合。

7.但是首先得先确定T1和T2的值。

8.先从T2是最大值的时候开始。

例，若n=14

T2取到的最大值为7，此时T1的值为0。

表示：走14个格子，共走7步，每一步都是走2格。

7个【2格】和0个【1格】，计算他们有几种排列方式：C(7 7)==1。

这种走法只有1种。

T2取的值为6时，T1的值只能是2。

表示：走14个格子，共走8步，其中有6步是走两格，2步是走一格。

6个【2格】和2个【1格】，计算他们有几种排列方式：C(8 6)==C(8 2)==28。

这种走法有28种。

以此类推…..

T2取的值为0时，T1的值只能是14。

表示：走14个格子，共走14步，每一步都是走一格。

0个【2格】和14个【1格】，计算他们有几种排列方式：C(0 14)==C(14 14)==1。

这种走法有1种。

最后将所有走法加起来。