排列組合遞歸演算法
#include<stdio.h>
#include<string.h>
void
Show(int
n,int
len
,char
str[],
char
p[],int
*i)
{
/*函數功能說明： 密碼窮舉法
遞歸演算法
參數說明：
len
密碼可選元素的個數，實際等於
strlen(str);
n
密碼位數。
STR[]密碼表。
*p
密碼排列組合的臨時存檔
*/
int
a;
n--;
for(a=0;
a
<
len;
a++)
{
p[n]=str[a];
if(n==0)printf("%d:%s
",(*i)++,p);
if(n>0)Show(n,len
,
str,p,i);
}
} /*驅動程序
用於測試*/
int
main(void)
{
char
str[]="abcdef";//密碼表
可選元素集合可根據選擇修改
int
n=4; //密碼位數，根據具體應用而定。
int
len=strlen(str);//用於密碼元素集合計數。
char
p[20]; //存放排列組合的密碼，用於輸出。
int
num=0;//存放統計個數的整數值，
int
*i=#//計數器
地址。
p[n]='\0';//這個不用說啦。 Show(
n,len
,str,
p
,i);
printf("\n%d
位密碼,每個密碼有%d個選擇的話，共有：%d個組合。\n",n,len,*i); return
0;
}
2. 遞歸演算法的設計
#include <stdio.h>
int C(int n,int m)
{ if(m==0||m==n)return 1;
return C(n-1,m)+C(n-1,m-1);
}
int main()
{ int i,j;
for(i=0; i<11; i++)
{ for(j=0; j<=i; j++)
printf("%5d",C(i,j));
printf(" ");
}
return 0;
}
3. 排列組合演算法，要求從一堆數中任取m個數組合使得m個數的和最接近某個數
典型的組合問題，解法有遞歸、回溯等等遞歸法較簡單，代碼如下： void combine(int a[], int n, int m, int b[], int M); 參數：a 存放候選數字n 總項數m 取出項數b 存放選出結果M = m
#include "stdio.h"#define MAX 100 void combine(int a[], int n, int m, int b[], int M); int main(void){ int i; int a[MAX], b[MAX]; for (i = 1; i < 100; i++) a[i - 1] = i; combine(a, 5, 4, b, 4);} void combine(int a[], int n, int m, int b[], int M){ int i, j; for (i = n; i >= m; i--) { b[m - 1] = i - 1; if (m > 1) combine(a, i - 1, m - 1, b, M); else { for (j = M - 1; j >= 0; j--) printf("%d ", a[b[j]]); printf("\n"); } }}
其他方法可查閱相關資料。
4. 設計遞歸演算法生成n個元素的所有排列對象
#include<iostream>
#include<iterator>
#include<algorithm>
using namespace std;
template<class T>
void permutation(T list[], int k, int m)
{
if (k == m)
{
(list, list + m + 1, ostream_iterator<T>(cout, "")); //將當前list排序
cout << endl;
}
else{
for (int i = k; i <= m; i++)
{
swap(list[i], list[k]); //將下標為i的元素交換到k位置，類似從list[k:m]中剔除操作
permutation(list, k + 1, m);
swap(list[i], list[k]);
}
}
}
int main(int argc, char* argv[])
{
char arr[3] = { 'a', 'b', 'c' };
cout << "排序結果如下：" << endl;
permutation(arr, 0, 2);
return 0;
}
(4)排列組合遞歸演算法擴展閱讀
遞歸，在數學與計算機科學中，是指在函數的定義中使用函數自身的方法。也就是說，遞歸演算法是一種直接或者間接調用自身函數或者方法的演算法。
通俗來說，遞歸演算法的實質是把問題分解成規模縮小的同類問題的子問題，然後遞歸調用方法來表示問題的解。
遞歸的基本原理
第一：每一級的函數調用都有自己的變數。
第二：每一次函數調用都會有一次返回。
第三：遞歸函數中，位於遞歸調用前的語句和各級被調用函數具有相同的執行順序。
第四：遞歸函數中，位於遞歸調用後的語句的執行順序和各個被調用函數的順序相反。
第五：雖然每一級遞歸都有自己的變數，但是函數代碼並不會得到復制。
5. c語言編程排列組合
void Show(int n,int len ,char str[], char p[],int *i){/*函數功能說明：
密碼窮舉法 遞歸演算法參數說明：len 密碼可選元素的個數，實際等於 strlen(str);
n 密碼位數。
STR[]密碼表。
*p 密碼排列組合的臨時存檔*/int a;n--;for(a=0; a < len; a++){p[n]=str[a];
if(n==0)printf("%d:%s ",(*i)++,p);
if(n0)Show(n,len , str,p,i);}}
/*驅動程序 用於測試*/
int main(void){char str[]="abcdef";//密碼表 可選元素集合可根據選擇修改
int n=4;//密碼位數，根據具體應用而定。
int len=strlen(str);//用於密碼元素集合計數。
char p[20];//存放排列組合的密碼，用於輸出。
int num=0;//存放統計個數的整數值，
int *i=#//計數器 地址。
p[n]='\0';//這個不用說啦。
printf("\n%d 位密碼,每個密碼有%d個選擇的話，共有：%d個組合。\n",n,len,*i);return 0;}
以上回答你滿意么？
6. 排列組合中A和C怎麼算啊
1、排列組合中，組合的計算公式為：
7. 排列組合中c53是怎麼算的，5在下，3在上
C（5,3）=C（5,2）=5*4/2*1=20/2=10
1、從n個不同元素中，任取m(m≤n)個元素並成一組，叫做從n個不同元素中取出m個元素的一個組合；從n個不同元素中取出m(m≤n)個元素的所有組合的個數，叫做從n個不同元素中取出m個元素的組合數。
2、在線性寫法中被寫作C(n,m)。組合數的計算公式為
即從m個不同元素中取出n個元素的組合數=從m個不同元素中取出 (m-n) 個元素的組合數；
這個性質很容易理解，例如C(9,2)=C(9,7)，即從9個元素里選擇2個元素的方法與從9個元素里選擇7個元素的方法是相等的。
規定：C(n,0)=1 C(n,n)=1 C(0,0)=1
參考資料
網路-組合數
8. pascal排列組合教程
排列與組合
3.1加法原理與乘法原理
1.加法原理：
做一件事情，完成它可以有n類辦法，在第一類辦法中有m1 種不同的方法，在第二類辦法中有 m2種不同的方法，……，在第n類辦法中有 mn種不同的方法。那麼完成這件事共有 N= m1+m2+...+mn 種不同的方法。
2.乘法原理：
做一件事情，完成它需要分成n個步驟，做第一步有m1 種不同的方法，做第二步有 m2種不同的方法，……，做第n步有 種mn不同的方法，那麼完成這件事有 N=m1*m2*...*mn 種不同的方法。
3.兩個原理的區別：一個與分類有關，一個與分步有關；加法原理是「分類完成」，乘法原理是「分步完成」。
練習：
1.由數字1，2，3，4，5可以組成多少個三位數（各位上的數字允許重復）？
② 2.由數字0、1，2，3，4，5可以組成多少個三位數（各位上的數字允許重復）？
③ 3.由數字0，1，2，3，4，5可以組成多少個十位數字大於個位數字的兩位數？
例 4. 一個三位密碼鎖,各位上數字由0,1,2,3,4,5,6,7,8,9十個數字組成,可以設置多少種三位數的密碼(各位上的數字允許重復)？首位數字不為0的密碼數是多少種？首位數字是0的密碼數又是多少種？
5.如圖，要給地圖A、B、C、D四個區域分別塗上3種不同顏色中的某一種，允許同一種顏色使用多次，但相鄰區域必須塗不同的顏色，不同的塗色方案有多少種？
6.某班有22名女生，23名男生.
① 選一位學生代表班級去領獎，有幾種不同選法？
② 選出男學生與女學生各一名去參加智力競賽，有幾種不同的選法？
7.105有多少個約數？並將這些約數寫出來.
8.從5幅不同的國畫、2幅不同的油畫、7幅不同的水彩畫中選不同畫種的兩幅畫布置房間，有幾種選法？
9.若x、y可以取1，2，3，4，5中的任一個，則點(x,y)的不同個數有多少？
10.一個口袋內裝有5個小球另一個口袋內裝有4個小球，所有這些小球的顏色各不相同① 從兩個口袋內任取一個小球，有 種不同的取法；
11.從兩個口袋內各取一個小球，有 種不同的取法.
12.乘積（a1+a2+a3）(b1+b2+b3+b4)(c1+c2+c3+c4+c5)展開共有 個項。
13.有四位考生安排在5個考場參加考試.有 種不同的安排方法。
(答案:125；180；15；1000，900，100；6；45，506；8；59；25；9；20；60；625）
3. 2 排列與組合的概念與計算公式
1．排列及計算公式
從n個不同元素中，任取m(m≤n)個元素按照一定的順序排成一列，叫做從n個不同元素中取出m個元素的一個排列；從n個不同元素中取出m(m≤n)個元素的所有排列的個數，叫做從n個不同元素中取出m個元素的排列數，用符號 p(n,m)表示.
p(n,m)=n(n-1)(n-2)……(n-m+1)= n!/(n-m)!(規定0!=1).
2．組合及計算公式
從n個不同元素中，任取m(m≤n)個元素並成一組，叫做從n個不同元素中取出m個元素的一個組合；從n個不同元素中取出m(m≤n)個元素的所有組合的個數，叫做從n個不同元素中取出m個元素的組合數.用符號
c(n,m) 表示.
c(n,m)=p(n,m)/m!=n!/((n-m)!*m!)；c(n,m)=c(n,n-m);
3．其他排列與組合公式
從n個元素中取出r個元素的循環排列數＝p(n,r)/r=n!/r(n-r)!.
n個元素被分成k類，每類的個數分別是n1,n2,...nk這n個元素的全排列數為
n!/(n1!*n2!*...*nk!).
k類元素,每類的個數無限,從中取出m個元素的組合數為c(m+k-1,m).
練習：
1．（1）用0，1，2，3，4組合多少無重復數字的四位數？（96）
（2）這四位數中能被4整除的數有多少個？（30）
（3）這四位數中能被3整除的數有多少個？（36）
2．用0，1，2，3，4五個數字組成無重復數字的五位數從小到大依次排列.
（1） 第49個數是多少？（30124）
（2） 23140是第幾個數？（40）
3．求下列不同的排法種數：
（1） 6男2女排成一排，2女相鄰；(p(7,7)*p(2,2))
（2） 6男2女排成一排，2女不能相鄰；(p(6,6)*p(7,2))
（3） 5男3女排成一排，3女都不能相鄰;(p(5.5)*p(6,3))
（4） 4男4女排成一排，同性者相鄰；(p(4,4)*p(4,4)*p(2,2))
（5） 4男4女排成一排，同性者不能相鄰。(p(4,4)*p(4,4)*p(2,2))
4．有四位醫生、六位護士、五所學校。
(1) 若要選派三位醫生到五所學校之中的三所學校舉辦健康教育講座，每所學校去一位醫生有多少種不同的選派方法？(c(5,3)*p(4,3))
(2) 在醫生或護士中任選五人，派到五所學校進行健康情況調查，每校去且僅去一人，有多少種不同的選派方法？(p(10,5))
(3) 組成三個體檢小組，每組一名醫生、兩名護士，到五所學校中的三所學校為老師體檢，有多少種不同的選派方法？(c(5,3)*p(4,3)*c(6,2)*c(4,2)*c(2,2))
5．平面上有三條平行直線，每條直線上分別有7，5，6個點，且不同直線上三個點都不在同一條直線上。問用這些點為頂點，能組成多少個不同四邊形？(2250)
6．平面上有三條平行直線，每條直線上分別有7，5，6個點，且不同直線上三個點都不在同一條直線上。問用這些點為頂點，能組成多少個不同三角形？(751)
7．將N個紅球和M個黃球排成一行。例如:N=2,M=2可得到以下6種排法:
紅紅黃黃 紅黃紅黃 紅黃黃紅 黃紅紅黃 黃紅黃紅 黃黃紅紅
問題:當N=4,M=3時有多少種不同排法?(不用列出每種排法)(35)
8.用20個不同顏色的念珠穿成一條項鏈,能做多少個不同的項鏈.(20!/20)
9．在單詞MISSISSIPPI 中字母的排列數是(11!/(1!*4!*4!*2!)
10．求取自1,2,...k的長為r的非減序列的個數為(c(r+k-1,r))
3.3排列與組合的產生演算法
1．排列的產生
方法1：（遞歸，深度優先產生）
程序如下：
program pailei;
const m=4;
var a:array[1..m] of integer ;
b:array[1..m] of boolean;
procere print;
var i:integer;
begin
for i:=1 to m do
write(a[i]);
writeln;
end;
procere try(dep:integer);
var i:integer;
begin
for i:=1 to m do
if b[i] then
begin
a[dep]:=i; b[i]:=false;
if dep=m then print else try(dep+1);
b[i]:=true;
end;
end;
begin
fillchar(b,sizeof(b),true);
try(1);
end.
方法2．根據上一個排列產生下一個排列．
程序如下：
program pailei;
const m=5;
var a:array[1..m] of integer ;
i,j,temp,k,l:integer;
procere print;
var i:integer;
begin
for i:=1 to m do
write(a[i]);
writeln;
end;
begin
for i:=1 to m do a[i]:=i;
repeat
print;
i:=m-1;
while (i>0) and (a[i]>a[i+1]) do i:=i-1;
if i>0 then
begin
j:=m;
while a[j]<a[i] do j:=j-1;
temp:=a[i];a[i]:=a[j];a[j]:=temp;
k:=i+1;l:=m;
while k<l do
begin
temp:=a[k];a[k]:=a[l];a[l]:=temp;
k:=k+1;l:=l-1
end;
end;
until i=0;
end.
2．組合的產生演算法
演算法1：（遞歸，深度優先產生）
程序如下：
program zuhe;
const n=6;m=4;
var a:array[0..m] of integer;
i,j:integer;
procere print;
var i:integer;
begin
for i:=1 to m do write(a[i]);
writeln;
end;
procere try(dep:integer);
var i:integer;
begin
for i:=a[dep-1]+1 to n-(m-dep) do
begin
a[dep]:=i;
if dep=m then print else try(dep+1);
end
end;
begin
a[0]:=0;
try(1);
end.
演算法2：根據前一個組合產生下一個組合
程序如下：
program zuhe;
const n=6;m=4;
var a:array[1..m] of integer;
i,j:integer;
procere print;
var i:integer;
begin
for i:=1 to m do write(a[i]);
writeln;
end;
begin
for i:=1 to m do
a[i]:=i;
repeat
print;
i:=m;
while (i>0) and (a[i]=n-(m-i)) do dec(i);
if i>0 then
begin
a[i]:=a[i]+1;
for j:=i+1 to m do a[j]:=a[j-1]+1;
end;
until i=0;
end.
練習：
1．已知n（1<=n<=20）個整數x1,x2,…,xn（1<=xi<=5000000），以及一個整數k（k<n）。從n個整數中任選k個整數相加，可分別得到一系列的和。現在，要求你計算出和為素數共有多少種。
2．n個部件,每個部件必須經過先A後B兩道工序。
以知部件i在A,B 機器上的時間分別為ai，bi。如何安排加工順序，總加工時間最短？
輸入：
5 部件 1 2 3 4 5
ai 3 5 8 7 10
bi 6 2 1 4 9
輸出：
34
1 5 4 2 3
我有這個的EXE，講的東西也還行，這個只是其中的一章，你要要把郵箱留下
9. 設計遞歸演算法生成n個元素的所有排列對象
#include<iostream>
#include<cmath>
using namespace std;
int count(int n)
//算n的階乘——因為n個數能組成n!個數
{
if(n<1)
{
cout<<"輸入也錯！";
exit(0);
}
else
if(n==1)
return 1;
else
return count(n-1)*n;
}
int pow10(int n)
//算出10的n次方
{
int a;
if(n==0)
return 1;
else
for(int i=1;i<=n;i++)
a=10*pow10(n-1);
return a;
}
int * comm(int n)
//組合n!個數（這里用遞歸算）
{
int *a=new int[count(n)];
if(count(n)==1)
a[0]=1;
else
{
int *b=new int[count(n-1)];
b=comm(n-1);
for(int i=0;i<count(n-1);i++)
for(int j=0;j<n;j++)
a[i*n+j]=(b/pow10(j)*10+n)*pow10(j)+b%pow10(j);
}
return a;
}
void main()
{
int n;
cout<<"請輸入n=";
cin>>n;
int *a=new int[count(n)];
a=comm(n);
cout<<"1-"<<n<<"自然數所有的排列組合為：\
";
for(int i=0;i<count(n);i++)
cout<<a<<" ";
}
=======================================
#define MAX 1000
#include<stdio.h>
void DispArrangement(int a[MAX], int n, int deepth)
{
int i, temp;
if(deepth == 1) {
for(i = 1; i <= n; i ++) {
printf("%d", a);
}
printf("\
");
} else {
for(i = 1; i <= deepth; i ++ ){
temp = a[n - deepth + 1];
a[n - deepth + 1] = a[n - deepth + i];
a[n - deepth + i] = temp;
DispArrangement(a, n, deepth - 1);
temp = a[n - deepth + 1];
a[n - deepth + 1] = a[n - deepth + i];
a[n - deepth + i] = temp;
}
}
}
int main(void)
{
int i, n, a[MAX];
scanf("%d", &n);
for(i = 1; i <= n; i ++ ) {
a = i;
}
DispArrangement(a, n, n);
return 0;
}