锐客网

  1. 首页 > it技术 > >

回溯法实现求1-n个自然数中r个数的组合

采用回溯法找问题的解，将找到的组合以从小到大顺序存于a[0]，a[1]，…，a[r-1]
中，组合的元素满足以下性质：
（1）a[i+1]>a[i]，后一个数字比前一个大；
（2）a[i]-i<=n-r+1。
算法具体实现如下（以求5个自然数中3个数的组合）：
回溯法实现求1-n个自然数中r个数的组合
文章图片

如图所示：为一个求组合问题的解空间，以深度优先的方式对该树进行遍历，到叶节点是输出一个解，当整棵树遍历完成之后就可以得到问题的所有解：
算法的具体实现如下：

#include #include #include int n; //自然数的个数 int r; int *com; //存放一个生成的组合用于输出void backtrack(int k); void output(); int main(int argc,char **argv) { printf("请输入自然数的个数n和组合个数r\n"); scanf("%d%d",&n,&r); if (r>n) { printf("输入数据错误!"); return 0; } com=(int*)malloc(r*sizeof(int)); com[0]=1; //组合数是从1开始的 backtrack(0); return 1; }void backtrack(int k) { int i=0; int j=0; if(k>=r) { output(); //到达叶节点输出结果 return; }else{ for(j=1; j

【回溯法实现求1-n个自然数中r个数的组合】转载于:https://www.cnblogs.com/liwenzhu/p/3504292.html

    推荐阅读


    上一篇：禅霏|禅霏 2018-07-15

    下一篇：Game|Game of Peace