注册 登录
编程论坛 C++教室

NYOJ上的题目:组合数

Theblueman 发布于 2018-05-26 21:55, 1868 次点击
找出从自然数1、2、... 、n(0<n<10)中任取r(0<r<=n)个数的所有组合。
按特定顺序输出所有组合。
特定顺序:每一个组合中的值从大到小排列,组合之间按逆字典序排列。


他给的答案没有一点注释,我根本看不懂啊!!!
程序代码:
#include<algorithm>
#include<iterator>
#include<iostream>
using namespace std;
int selected[10];
int data[]={10,9,8,7,6,5,4,3,2,1};
void myfind(int start,int step,int M,int N)
{
   
   
    if(step==N) {
    copy(selected,selected+N,ostream_iterator<int>(cout,""));
    cout<<endl;
    return;
    }
   
   
    for(int i=start;i<=M;i++)
    {
        selected[step]=data[9-M+i];
        myfind(i+1,step+1,M,N);
    }
   
   
}
int main()
{
    int m,n;
    cin>>m>>n;
    myfind(1,0,m,n);
}
4 回复
#2
林月儿2018-05-26 23:15
程序代码:
#include<iterator>
#include<iostream>
using namespace std;
int selected[10];
int data[]={10,9,8,7,6,5,4,3,2,1};
void myfind(int start,int step,int M,int N){
    if(step==N){
        //通过流迭代器将向量中的变量放到输出流中
        copy(selected,selected+N,ostream_iterator<int>(cout,","));
        //换行
        cout<<endl;
           return;
    }
    // 这里用了递归,收敛条件为step==N,
   
// 建议改为step>=N. 或者对入参校验。
    for(int i = start;i <= M; i++) {
        // 1.考虑重复可能性
        
// 首先,下一层的selected存储下标step是逐层递增,
        
// 其次,selected的存放对象在上一层的下标为9-M+i,
        
// 那么根据调用myfind传参可知,下一层就是起始下标是当前下标+1.所以不存在重合的场景。
        
// 2.分析遗漏场景
        
// 根据每一层从新的起始值到selected的赋值次数为N结束。赋值范围都是从当前轮回的值当前最后的1全覆盖。
        
// 由上分析,流程不重复不遗漏.满足递减的组合算法。
        selected[step]=data[9-M+i];
        myfind(i+1, step+1, M, N);
    }
}
int main(){
    int m,n;
    cin>>m>>n;
    myfind(1,0,m,n);
}
#3
Theblueman2018-05-27 00:26
回复 2楼 林月儿
谢谢
#4
静水且流深2018-06-02 11:45


[此贴子已经被作者于2018-6-2 11:47编辑过]

1