走楼梯

题目

  一个人从0阶开始上楼梯，楼梯一共有n阶，这个人每次可以走[1,剩余的阶数]，请计算走法总数并输出每种走法中每次走的阶数

数学证明

  由于这个人是任意走的，所以每个阶梯要么被踩到，要么不踩到，0到n阶一共有n-1个阶梯，所以走法总数为(2^{n-1})

代码

• r表示剩余阶数
• a用来存放走的阶数
• sub表示下标

#include <iostream>
using namespace std;
int num = 0;
void f(int r,int *a,int sub)
{
	if(r == 0)
	{
		cout << (++num) << ':';
		for(int i = 0;i < sub;++i)
			cout << a[i] << '	';
		cout << endl;
	}
	else
		for(int i =1;i <= r;++i)
		{
			a[sub] = i;
			f(r-i,a,sub+1);
		}
}
int main()
{
	int n;
	cin >> n;
	int *a = new int[n];
	f(n,a,0);
	delete[] a;
	return 0;
}