codeup 100000608 problem B 【递归入门】组合数的输出

题目在这里：我是题目

题目就是输入两个数，一个n 一个r。实现类似Cnr（数学里面的排列组合，n在下面，r在上面）

这里可以用到递归，在网上看到了别人AC代码如下：（稍有改动）

#include int n, r;
int num[20];void combine(int count) {if(count == r +1) {			//递归出口for(int i = 1;i <= r; i++)printf("%d ", num[i]);printf("\n");return ;	//返回上一层}for(int i = num[count - 1] + 1;i <= n; i++) {		//依次枚举，这里初试条件改成i=count可以得到全排列num[count] = i;combine(count+1);	}
}int main() {scanf("%d%d", &n, &r);int count = 1;num[0] = 0;combine(count);return 0;
}

但是并不是很理解，所以我把每个时刻的状态打印出来，来理解递归：

以下都是n=5,r=3的情况下得出的推论

这是第1次进入函数,count=1
进入循环，i=1,将ans[1]赋值为1
这是第2次进入函数,count=2
进入循环，i=2,将ans[2]赋值为2
这是第3次进入函数,count=3
进入循环，i=3,将ans[3]赋值为3
这是第4次进入函数,count=4
1 2 3
进入循环，i=4,将ans[3]赋值为4
这是第5次进入函数,count=4
1 2 4
…此处省略一万字

为了方便自己复习递归，花了点功夫整理成图片了：

怎么说，一步一步整理下来之后有了新的感受，就是递归就是有点分治的思想吧。明确了一个方向之后，把路铺开，从后面(递归边界)一点点往前面算过来，最后就能得到自己想要的结果。就好比最经典的递归：计算n！中的return n*func(n-1) 然后边界是 if(n==0) return 1;也就是先调用一大堆函数(或者可以理解成一种状态),只有后面的状态明确了之后才能明确前面的状态。直到展开到边界了以后所有的状态都出来了才可以计算。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！