洛谷P1157 组合的输出

本文主要是介绍洛谷P1157 组合的输出，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

与排列差不多但是又差的多，详情看题：

题目描述

排列与组合是常用的数学方法，其中组合就是从nn个元素中抽出rr个元素(不分顺序且r \le n)r≤n)，我们可以简单地将nn个元素理解为自然数1,2,…,n1,2,…,n，从中任取rr个数。

现要求你输出所有组合。

例如n=5,r=3n=5,r=3，所有组合为：

12 3 , 1 2 4 , 1 2 5 , 1 3 4 ,1 3 5 , 1 4 5 , 2 3 4 , 2 3 5 , 2 4 5 , 3 4 5123,124,125,134,135,145,234,235,245,345

输入格式

一行两个自然数n,r(1<n<21,0 \le r \le n)n,r(1<n<21,0≤r≤n)。

输出格式

所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。

分为两个办法

首先用比较熟悉的STL，方法如下：

#include<bits/stdc++.h>
using namespace std;
int n,r;
int a[25];
int main()
{
    cin>>n>>r;
    for(int i=r+1;i<=n;i++)//因为是从1~5进行组合排列 
    {
        a[i]=1;//用1来表示不选 
    }
    do
    {
        for(int i=1;i<=n;i++)
        {
            if(a[i]==0)//用0来表示选中了 
            {
                printf("%3d",i);
            }
        }
        cout<<endl;
    }while(next_permutation(a+1,a+n+1));//同理 
    return 0;
}

另外一种就是暴力搜索的递归——dfs，虽然我不喜欢用但是这种方法具有普遍性；

附上代码：

#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[25];
void dfs(int step)//step表示到了那一层 
{
    if(step==k+1)
    {
        for(int i=1;i<=k;i++)
        {
            printf("%3d",a[i]);
        }
        printf("\n");
     
     }
     for(int i=a[step-1]+1;i<=n;i++)//只要从a[step]大 即a[step]+1就行 
     {
         a[step]=i;//存值 
         dfs(step+1);//进入下一层 
      } 
}
int main()
{
    cin>>n>>k;
    dfs(1);//照应step-1    
    return 0;
}

并且推荐一下讲的很好的讲解视频：https://www.bilibili.com/video/BV1JK41137b9?from=search&seid=3290462022916294689&spm_id_from=333.337.0.0

就这样吧。

这篇关于洛谷P1157 组合的输出的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！