排列组合的C语言实现

2023-09-19 22:33| 来源: 网络整理| 查看: 265

排列与组合

排列与组合一排列数学定义代码实现（求排列的种类）：排列的具体形式二组合数学意义：代码实现求组合的具体形式（个人觉得回溯这一步真的很容易忘掉-_-)以上就是全部内容，希望大家三连关注，我会继续更新C语言和python方面的有关内容

一排列数学定义

A m n \quad A_m^n Amn表示在m个数中取出n个数，并进行全排列，当m=n时，为全排列，可写为 n ! n! n!。 A m n = m ( m − 1 ) ( m − 2 ) . . . . ( m − n ) A_m^n=m(m-1)(m-2)....(m-n) Amn=m(m−1)(m−2)....(m−n)

代码实现（求排列的种类）： int arrange(int m,int n) { if(m==n) return n; return m*arrange(m-1,n); } 排列的具体形式

在这里我们可以用dfs（深度优先搜索）去解决,思路如下：从第一个数开始，让其等于 1 , 2 , 3 , 4... n 1,2,3,4...n 1,2,3,4...n,以此类推到第n个数，且前面用过的数后面就不能再用，我们用 m a r k [ ] mark[] mark[]去记录这个数，并在每一次执行到n后回溯。代码如下：

void dfs(int x){ if(x==n){ for(int i=1;ia[x]=i;mark[i]++; } dfs(x+1); mark[i]=0;//回溯 } }

输出每一种排序的可能

二组合数学意义：

C m n C_m^n Cmn表示从m个数中取出n个数的方法数，想要求出这个数我们有两种方法：

法一： C m n = m ( m − 1 ) ( m − 2 ) . . . . ( m − n ) n ! C_m^n= \frac{m(m-1)(m-2)....(m-n)}{n! } Cmn=n!m(m−1)(m−2)....(m−n)

法二： C m n = C m − 1 n + C m − 1 n − 1 C_m^n=C_{m-1}^n+C_{m-1}^{n-1} Cmn=Cm−1n+Cm−1n−1

代码实现 //法一 int cnm(int n,int m){ if(n==1) return m; return m*cnm(n-1, m-1)/n; } //法二 int cnm(int n,int m){ if(n==1) return m; if(n==m)return 1; return (cnm(n,m-1)+cnm(n-1, m-1)); } 求组合的具体形式

咱们依然是用dfs去解决

void dfs(int x) { if(x==m+1){for(int j=1;j

【本文地址】

排列组合的C语言实现

排列组合的C语言实现

今日新闻

推荐新闻