亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

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

 更新時(shí)間:2022年01月13日 10:08:04   作者:布布要成為最強(qiáng)的人  
大家好,本篇文章主要講的是C語言中遞歸和排列組合詳解,感興趣的同學(xué)趕快來看一看吧,對(duì)你有幫助的話記得收藏一下,方便下次瀏覽

排列組合三大問題:

1.打印n個(gè)數(shù)的全排列
2.打印n個(gè)數(shù)中任意m個(gè)數(shù)的全排列
3.打印n個(gè)數(shù)中任意m個(gè)數(shù)的組合

1.打印n個(gè)數(shù)的全排列

這個(gè)題實(shí)際上是可以直接用STL中的next_permutation()函數(shù),代碼如下:

#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));
}
這樣輸出出來的全排列是按照字典序輸出的,這是它的優(yōu)點(diǎn)。

如果用遞歸求全排列呢?
假如給了n個(gè)數(shù)123…n,求其全排列的數(shù)量,應(yīng)當(dāng)如何解決呢,下面給出一個(gè)遞歸的思路:

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

然后在上面的每個(gè)數(shù)列中去掉第一個(gè)數(shù),對(duì)后面的n-1個(gè)數(shù)做如上操作,例如取第二組做該操作,則該第二層的遞歸為:
1 3 4 5…n
3 1 4 5…n
.
.
.
n 3 4 5…1

重復(fù)以上步驟,直到用完所有的數(shù)字。

這么講并不好理解,我從小規(guī)模到大規(guī)模來闡述這個(gè)思想:

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

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

往后依舊借用前面的標(biāo)準(zhǔn)即可。
可是放到代碼實(shí)現(xiàn)的時(shí)候可不能做完一層刪一個(gè)數(shù),只能實(shí)現(xiàn)的了保留那層遞歸的第一個(gè)數(shù),然后繼續(xù)對(duì)下面的數(shù)做遞歸操作,這樣就完美符合了遞歸的思想。
代碼實(shí)現(xiàn)如下:

#include<bits/stdc++.h>
using namespace std;
#define Swap(a,b){int temp=a;a=b;b=temp;}
//也可以用STL的swap函數(shù),但是速度慢一些
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);//保留第一個(gè)數(shù),進(jìn)入下一層遞歸
            Swap(data[begin],data[i]);//要記得換回來
        }
    }
}
int main(){
	Perm(0,4);
	cout<<num<<endl;
}

如果想要輸出這個(gè)排列,直接在Perm函數(shù)中的if語句下面做循環(huán)輸出即可。
需要注意的是:這樣輸出出來的并不一定符合字典序。

2.打印n個(gè)數(shù)中任意m個(gè)數(shù)的全排列

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

3.打印n個(gè)數(shù)中任意m個(gè)數(shù)的組合

這個(gè)和上面的第2個(gè)問題就不一樣了,組合問題只需要選m個(gè)數(shù)而無須做排列,應(yīng)該怎么實(shí)現(xiàn)呢?
利用二進(jìn)制的思想,原理如下:
設(shè)一個(gè)集合{a0,a1,a2,…,an-1},子集共有2的n次方個(gè),其中包括空集。
例如一個(gè)n=3的集合{a0,a1,a2},其子集為{φ},{a0},{a1},{a1,a0},{a2},{a2,a0},{a2,a1},{a2,a1,a0}。為什么以這個(gè)順序來排呢?因?yàn)檫@樣非常符合二進(jìn)制位權(quán)值的思想。剛好可以和二進(jìn)制對(duì)應(yīng):

φa0a1a1 a0a2a2 a0a2 a1a2 a1 a0
000001010011100101110111

如何輸出這些子集?,還是利用二進(jìn)制位權(quán)的思想,利用相與運(yùn)算得出其二進(jìn)制數(shù)中的每一個(gè)1,直接對(duì)應(yīng)數(shù)字,完全代碼如下:

#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的二進(jìn)制數(shù)中的每一個(gè)1
            if(i&(1<<j))
                cout<<j<<" ";
        cout<<endl;
    }
}
int main(){
	int n;
	cin>>n;
	print_subset(n);
}

回到問題3,要找到任意m個(gè)數(shù)的組合,只需要做一個(gè)判斷:確定一個(gè)子集對(duì)應(yīng)的二進(jìn)制數(shù)中1的數(shù)量。這是解題的關(guān)鍵。
有一個(gè)很巧妙的做法:kk=kk&(kk-1)
重復(fù)使用該式子,直到kk為0,即可得出1的數(shù)量。

完整代碼如下:

#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的二進(jìn)制數(shù)中的每一個(gè)1
                if(i&(1<<j))
                    cout<<j<<" ";
            cout<<endl;
        }
    }
}
int main(){
	int n,k;
	cin>>n>>k;
	print_subset(n,k);
}

總結(jié)

到此這篇關(guān)于C語言中遞歸和排列組合詳解的文章就介紹到這了,更多相關(guān)C語言遞歸和排列組合內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

最新評(píng)論