演算法組合數

⑴ 排列組合公式及排列組合演算法

排列組合公式

排列組合公式/排列組合計算公式

公式P是指排列，從N個元素取M個進行排列。

公式C是指組合，從N個元素取M個進行組合，不進行排列。

N-元素的總個數

M參與選擇的元素個數

！-階乘，如9！＝9*8*7*6*5*4*3*2*1

從N到數M個，表達式應該為n*（n-1)*(n-2)..(n-m+1);

因為從n到（n-m+1)個數為n－(n-m+1)＝m

舉例：

Q1: 有從1到9共計9個號碼球，請問，可以組成多少個三位數？

A1: 123和213是兩個不同的排列數。即對排列順序有要求的，既屬於「排列P」計算范疇。

上問題中，任何一個號碼只能用一次，顯然不會出現988,997之類的組合，我們可以這么看，百位數有9種可能，十位數則應該有9-1種可能，個位數則應該只有9-1-1種可能，最終共有9*8*7個三位數。計算公式＝P(3,9)＝9*8*7,(從9倒數3個的乘積）

Q2:有從1到9共計9個號碼球，請問，如果三個一組，代表「三國聯盟」，可以組合成多少個「三國聯盟」？

A2:213組合和312組合，代表同一個組合，只要有三個號碼球在一起即可。即不要求順序的，屬於「組合C」計算范疇。

上問題中，將所有的包括排列數的個數去除掉屬於重復的個數即為最終組合數C(3,9)=9*8*7/3*2*1

⑵ 數學的排列組合演算法加公式

不能重復的c(6,4) c(6,5) 1,2,3......,n n個數中 任取m個組合 c(n,m) 能重復的 6^4 6^5 1，2，3，。。。。n,n個數中，取m個組合（可重復） n^m 追問： c(n,m),讀作什麼？把1-6取4位帶進去怎麼算，可以教我嗎？50分感激不盡 回答： 這個是組合數 從n個元素裡面取m個元素的組合數 比如c(6,4)=(6*5*4*3)/(1*2*3*4) c(n,m)=[n*(n-1)*.........*(n-m+1)]/(1*2*......*m) 分子從n開始往下取 一直取m個連續的自然數相乘 分母從1取到m m個連續自然數相乘 追問： c(n,m)=[n*(n-1)*.........*(n-m+1)]/(1*2*......*m) 後面的/(1*2*......*m)是要除的么？ 這個怎麼求的？ 回答： 你題目說的不是很清楚 如果說要是組成數字 就不需要除以下面的（排列） 若只是取出來 不要求構成數字 則要除（組合） 補充： 只算組合 不要求構成數字 你的做法是對的 補充： 不可重復 15組 可重復 6^4=1296組 補充： 估計你的題目是要求構成數字的 不可重復的就是 6*5*4*3=360種 可重復的還是1296種 補充： 你一直都沒說 是否要求構成數字 取4個數字出來 是要構成一個4位數嗎？ 如果是 則是360種 不是 則是15種 補充： 這是你自己想的題目吧 原題絕對不會說這樣的話 補充： 排列組合你沒學 這些一下你也搞不懂的 打個比方，從1，2，3中取2個數字 則有3種取法 {1，2}，{1，3），{2，3} 如果你要是說取2個數字構成2位數 則有6種12，21，13，31，23，32 你對照公式看下 追問： 就是6位取4位構成4位數就有360種，那麼15種又是哪裡來的？ 回答： 暈了 我已經說的很清楚了啊 例子都列出來了 15種是取出來不進行排列 360是還要進去排列組成4位數 補充： 你要是自學排列組合 還是先把定義搞清楚吧 再說 你出的這個題目本身說的就模稜兩可得 我一直在問你是否要求構成四位數 360和15得區別就在於這點 追問： 我終於懂了，在你們精心輔導下，我終於懂了，其實我對這些一竅不通，根本都沒學！謝謝你們懸賞最高！

⑶ 怎樣求大組合數（取模）（ACM演算法）

這種題目然做過的，
意思比較簡單，就由 m 個共 0 和 n 個 1 組成一個串，但從左到右要1出現的次數不少於0出現的次數。
由大牛的演算法： 結果就是 C(m+n, n) - C(m+n, m-1) 再取模，我們可以對式子化簡一下就是：
(n+m)！*
(n-m+1) / ((m)！* (n+1)！)
再取模，但由於組合數很大，直接用大數乘除就會超時了，看了別人的報告才知道原來可以用素數化簡快速求模的， n! = 2^p[i] *
3^p[i] * 5^p[i]*...... 再求模就可以很快了~(^ = ^)~。。。

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
#define M 2000005
#define mm 20100501
bool sig[M];
int prime[150000], p[150000], len; // prime 記錄素數， p 記錄素數的冪 len 記錄長度
void getprime() // 篩法找素數
{
int i,j,k=0;
prime[k++] = 2;
for(i=3; i<=M; i+=2)
{
if( !sig[i] )
{
prime[k++] = i;
for(j=i; j<=M; j+=i)
sig[j] = 1;
}
}
}
void get(int k, int s) // K! 的素數分解, S為指數的加減(分母，分子)
{
int i, mid;
for(i=0; prime[i]<=k && prime[i]; i++)
{
mid = k;
while(mid)
{
if(s)
p[i] += mid/prime[i];
else
p[i] -= mid/prime[i];
mid /= prime[i];
}
}
if(len < i)
len = i;
}
__int64 cal() // 計算結果 (prime[i...]^p[i...]) % mm
{
__int64 i,ans = 1;
for(i=0; i<=len; i++)
{
if( p[i] )
{
__int64 t = prime[i], b = p[i], ret = 1;
while(b) //計算 (t^b) % mm
{
if(b%2) ret *= t %mm;
t = t*t%mm;
b /= 2;
}
ans = ( ans*ret ) % mm;
}
}
return ans;
}
int main()
{
int t,m,n,i,mid;
__int64 ans;
getprime();
cin>>t;
while(t--)
{
cin>>n>>m;
len = 0;
memset(p, 0, sizeof(p));
mid = n-m+1; //先前要把 n-m+1 的因子加進 P 中去才能使 (m+n)! / ((m)!*(n+1)!) 整除
for(i=0; mid>1; i++)
{
if( mid%prime[i] == 0)
{
while(mid%prime[i]==0)
{
p[i] += 1;
mid /= prime[i];
}
}
}
get(m+n, 1);
get(m, 0);
get(n+1, 0);
ans = cal();
printf("%I64d\n", ans);
}
return 0;
}

可以用素數分解法，
先求出上面和下面的素數表示，然後約分後，再用求冪公式

⑷ 求排列組合演算法，比如C62（6在下，2在上），麻煩詳細一點，高中的知識還給老師了，汗

C62（6在下，2在上）計算方法如下：

⑸ c語言組合數演算法不用遞歸怎麼做

不用遞歸則可以用 公式的呀，從n個元素中選取m個(n>=m)的組合數，公式如下。

C(n, m) = n!/(m! * (n-m)!)

而m!和(n-m)!兩者中的較大一個可以和n!的前若干項約分掉，我們不妨設n-m > m，則(n-m)!可以被約掉，只要求m!和 (n-m+1)*...*n即可。然後將這兩個連乘積相除，即為組合數。

程序可如下：

#include <stdio.h>

void main( )

{

int n, m, max, min, i, s = 1, r = 1;

scanf("%d%d", &n, &m);

max = (m > (n-m) ? m : (n - m));

min = n - max;

for(i = 1; i <= min; i++)

r *= i, s *= (max + i);

printf("C(%d,%d) = %d ", n, m, s / r); /*max的階乘可以約掉，所以不必求*/

}

運行結果：

⑹ 能不能講給我關於排列，組合的公式怎麼演算法

zfjsdc

翟玉蘭 發表於 2007-3-3 15:14:00

排列與組合的概念與計算公式

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).

⑺ 排列組合公式演算法是什麼

排列組合是組合學最基本的概念公式，從n個中取m個排一下，有n(n-1)(n-2)…(n-m+1)種，即n/(n-m)。排列組合計算公式從n個不同元素中取出m（m≤n）個元素的所有排列的個數。

從n個不同元素中，任取m(m≤n）個元素並成一組，叫做從n個不同元素中取出m個元素的一個組合；從n個不同元素中取出m(m≤n）個元素的所有組合的個數，叫做從n個不同元素中取出m個元素的組合數。用符號 C(n,m) 表示。

根據組合學研究與發展的現狀，它可以分為如下五個分支：經典組合學、組合設計、組合序、圖與超圖和組合多面形與最優化。

由於組合學所涉及的范圍觸及到幾乎所有數學分支，也許和數學本身一樣不大可能建立一種統一的理論。然而，如何在上述的五個分支的基礎上建立一些統一的理論，或者從組合學中獨立出來形成數學的一些新分支將是對21世紀數學家們提出的一個新的挑戰。

⑻ 數字排列組合演算法

例子： C1，3=（3*2*1）/（3-1）！*1！

組合：C7，9=36 組
排列：A7，9=181440 組

⑼ 排列組合中A和C的演算法怎麼算的，查了百度都不會，求詳細點的謝謝（高中）

排列數 A(n,m) ----------即 字母A右下角n 右上角m,表示n取m的排列數
A(n,m)=n!/(n-m)!=n*(n-1)*(n-2)*……*(n-m+1)
A(n,m)等於從n 開始連續遞減的 m 個自然數的積
n取m的排列數 A(n,m) 等於從n 開始連續遞減的 m 個自然數的積
例: A(7,3)=7*6*5=210
組合數 C(n,m) ----------即 字母C右下角n 右上角m,表示n取m的排列數
C(n,m)=n!/(m!*(n-m)!)=n*(n-1)*(n-2)*……*(n-m+1)/(1*2*3*……*m)
C(n,m)等於(從n 開始連續遞減的 m 個自然數的積)除以(從1開始連續遞增的 m 個自然數的積)
n選m的組合數 C(n,m) 等於(從n 開始連續遞減的 m 個自然數的積)除以(從1開始連續遞增的 m 個自然數的積)
例: C(7,3)=7*6*5/(1*2*3)=35

⑽ 組合演算法：從m個數中選n個數的所有組合

#include <iostream.h>

int combine(int a[], int n, int m)
{
m = m > n ? n : m;

int* order = new int[m+1];
for(int i=0; i<=m; i++)
order[i] = i-1;

int count = 0;
int k = m;
bool flag = true;
while(order[0] == -1)
{
if(flag)
{
for(i=1; i<=m; i++)
cout << a[order[i]] << " ";
cout << endl;
count++;
flag = false;
}

order[k]++;
if(order[k] == n)
{
order[k--] = 0;
continue;
}

if(k < m)
{
order[++k] = order[k-1];
continue;
}

if(k == m)
flag = true;
}

delete[] order;
return count;
}

int main()
{
const int M = 4;
const int N = 3;
int a[M];
int b[N];
for(int i=0;i<M;i++)
a[i] = i+1;

combine(a,M,N);

return 0;
}