日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

C語言中遞歸和排列組合詳解_C 語言

作者：布布要成為最強的人 ? 更新時間： 2022-03-28 編程語言

排列組合三大問題：

1.打印n個數的全排列
2.打印n個數中任意m個數的全排列
3.打印n個數中任意m個數的組合

1.打印n個數的全排列

這個題實際上是可以直接用STL中的next_permutation()函數，代碼如下：

#include<bits/stdc++.h>
using namespace std;
int main(){
	int data[4]={5,2,4,1};
	sort(data,data+4);//先排序得到字典序最小的序列
	do{
		for(int i=0;i<4;i++)
			cout<<data[i]<<" ";
		cout<<endl;
	}while(next_permutation(data,data+4));
}

這樣輸出出來的全排列是按照字典序輸出的，這是它的優點。

如果用遞歸求全排列呢？
假如給了n個數123…n，求其全排列的數量，應當如何解決呢，下面給出一個遞歸的思路：

一開始先按照字典序排列，然后把第一個數依次和后面的數交換：
1 2 3 4 5…n
2 1 3 4 5…n
.
.
.
n 2 3 4 5…1
這是第一層遞歸，只要第一個數不同，不需要管后面n-1個數

然后在上面的每個數列中去掉第一個數，對后面的n-1個數做如上操作，例如取第二組做該操作，則該第二層的遞歸為：
1 3 4 5…n
3 1 4 5…n
.
.
.
n 3 4 5…1

重復以上步驟，直到用完所有的數字。

這么講并不好理解，我從小規模到大規模來闡述這個思想：

假如只有兩個數1,2需要進行全排列工作：
先按字典序排成1,2，這是第一層遞歸的第一組
把1去掉，只留下一個數，那么只有1種情況。
第一層遞歸的第二組是2,1，這也是最后一組了
把2去掉，只留下一個數，那么只有1種情況
因此兩個數的全排列是兩種情況

假如有三個數1,2，3需要進行全排列工作：
直接看第一層遞歸的三種情況：
1、2、3；2、1、3；3、2、1
每一種情況都把第一個數去掉，就變成只有2個數的全排列了
而由上述所知，兩個數的全排列有兩種情況
那么第一層遞歸的三種情況都各自包含兩種情況即3×2=6

往后依舊借用前面的標準即可。
可是放到代碼實現的時候可不能做完一層刪一個數，只能實現的了保留那層遞歸的第一個數，然后繼續對下面的數做遞歸操作，這樣就完美符合了遞歸的思想。
代碼實現如下：

#include<bits/stdc++.h>
using namespace std;
#define Swap(a,b){int temp=a;a=b;b=temp;}
//也可以用STL的swap函數，但是速度慢一些
int data[]={1,2,3,4,5};
int num=0;
void Perm(int begin,int end){
    if(begin==end)num++;//遞歸到底了，自然只有一種情況，num++
    else{
        for(int i=begin;i<=end;i++){
        	//i要注意從begin開始，自己和自己換的也算是一種情況
            Swap(data[begin],data[i]);
            Perm(begin+1,end);//保留第一個數，進入下一層遞歸
            Swap(data[begin],data[i]);//要記得換回來
        }
    }
}
int main(){
	Perm(0,4);
	cout<<num<<endl;
}

如果想要輸出這個排列，直接在Perm函數中的if語句下面做循環輸出即可。
需要注意的是：這樣輸出出來的并不一定符合字典序。

2.打印n個數中任意m個數的全排列

這個只需要把上面if語句中的條件改一下就行，改成begin==m即可
思路是一樣的，從小規模列起就好了。

3.打印n個數中任意m個數的組合

這個和上面的第2個問題就不一樣了，組合問題只需要選m個數而無須做排列，應該怎么實現呢？
利用二進制的思想，原理如下：
設一個集合{a0,a1,a2,…,an-1}，子集共有2的n次方個，其中包括空集。
例如一個n=3的集合{a0,a1,a2}，其子集為{φ},{a0},{a1},{a1,a0},{a2},{a2,a0},{a2,a1},{a2,a1,a0}。為什么以這個順序來排呢？因為這樣非常符合二進制位權值的思想。剛好可以和二進制對應：

φ a0 a1 a1 a0 a2 a2 a0 a2 a1 a2 a1 a0
000 001 010 011 100 101 110 111

如何輸出這些子集？，還是利用二進制位權的思想，利用相與運算得出其二進制數中的每一個1，直接對應數字，完全代碼如下：

#include<bits/stdc++.h>
using namespace std;
void print_subset(int n){
    for(int i=0;i<(1<<n);i++){
        for(int j=0;j<n;j++)//打印子集，即打印i的二進制數中的每一個1
            if(i&(1<<j))
                cout<<j<<" ";
        cout<<endl;
    }
}
int main(){
	int n;
	cin>>n;
	print_subset(n);
}

回到問題3，要找到任意m個數的組合，只需要做一個判斷：確定一個子集對應的二進制數中1的數量。這是解題的關鍵。
有一個很巧妙的做法：kk=kk&(kk-1)
重復使用該式子，直到kk為0，即可得出1的數量。

完整代碼如下：

#include<bits/stdc++.h>
using namespace std;
void print_subset(int n,int k){
    for(int i=0;i<(1<<n);i++){
        int num=0,kk=i;
        while(kk){
            kk=kk&(kk-1);
            num++;
        }
        if(num==k){
            for(int j=0;j<n;j++)//打印子集，即打印i的二進制數中的每一個1
                if(i&(1<<j))
                    cout<<j<<" ";
            cout<<endl;
        }
    }
}
int main(){
	int n,k;
	cin>>n>>k;
	print_subset(n,k);
}

總結

原文鏈接：https://blog.csdn.net/m0_52380556/article/details/122461644

欄目分類
最近更新