排列与组合的一些定理教案_平行轴定理推导

排列与组合的一些定理教案_平行轴定理推导一,加法原理与乘法原理加法原理与乘法原理是排列与组合的基础。加法原理本质上是分类,乘法原理本质上是分步。分类,就是把一个集合(某事物)分成互不相交的若干独立的部分。比如,概率论中的全概率公式就将事

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

一,加法原理与乘法原理

加法原理与乘法原理是排列与组合的基础。加法原理本质上是分类,乘法原理本质上是分步。

分类,就是把一个集合(某事物)分成互不相交的若干独立的部分。比如,概率论中的全概率公式就将事件分成”全划分“

分类思想可以简化程序的时间复杂度。比如:最短路径算法-Dijkstra算法的应用之单词转换(词梯问题)

分步,就是第一步干嘛,第二步再干嘛……比如A地到D地,第一步:先到达B地;第二步,再到达C地

 

二,排列

P(n,r)表示从n个数中选择r个数的一个全排列

公式:P(n,r)=P(n-1,r)+p(n-1,r-1)*r

上面公式用到了分类思想:对于某个元素而言,要么选,要么不选。如果不选它,则在剩下的n-1个元素中选r个进行全排列;如果选了它,则在剩下的n-1个元素中只需要选r-1个元素进行全排列了。但是选了的那个元素,一共有r种位置存放(因为这是排列,同一个元素放在不同的位置 属于不同的排列)故p(n-1,r-1)*r。

排列一共有三种:①线排列,就是通常的普通排列。

公式:P(n,r)=n!/(n-r)!

②圆排列,相当于排序的数围成一个圆。比如循环队列的那种实现方式。举个圆排列的例子如下:

a b c d四个字母的线排列共有4!=24种。对于其中的一种排列: a b c d ,它对应着四种等价圆排列:

1) a b c d   2) b c d a   3)c d a b   4)d a b c

因此,对于给定n个数的所有圆排列,一共有 p(n,r)/r种。 因为,一个圆排列可以产生r个线排列。

③重排列

对于线排列而言,某个元素选了之后,就不能再选了(一个元素只能选一次)

对于重排列而言,一个元素可以选多次。

集合{∞·b1∞·b2,….,∞·bn}的一个r排列个数为:nr

即从b1b2bn,共n个元素中选出r个,每个元素可选任意多次,一共有nr排列

还有一种重排列是:每个元素最多只能选K次(某个固定的次数)

{K1·b1,K2·b2,….,Kn·bn}( 元素b1最多只能选K1次)的一个r排列个数为:(K1+K2+….+Kn)!/(K1!K2!…Kn!)

上面表示从b1b2bn,共n个元素中选出r个进行排列,但是 bj最多只能选Kj次,一共有(K1+K2+….+Kn)!/(K1!K2!…Kn!)次排列方式。

 

三,组合

C(n,r)表示从n个数中选择r个数的一个全组合。

公式:C(n, r)=[n!/(r!)(n-r)!]=P(n,r)/r!

公式:C(n,r)=C(n-1,r)+C(n-1,r-1)  这个公式用到了分类思想。对于n个元素的某个元素,要么选,要么不选。

如果选了,只需在 剩下的n-1 个元素中选 r-1个;如果不选,则在剩下的n-1个元素中选r个(因为一共要选r个啊)。

这个公式非常有用,这是杨辉三解公式:其中基准条件C(n,0)=1,C(i,i)=1

C(0,0)

C(1,0)   C(1,1)

C(2,0)   C(2,1)   C(2,2)

C(3,0)   C(3,1)   C(3,2)   C(3,3)

…..        …..        …..

如果要求解C(n,r),可以先求解出C(n-1,r) 和 C(n-1,r-1);再运用公式相加即可。很明显,这是一个与Fib数列类似的递归计算。只不过求Fib(n)时,只有一个参数,而这里有二个参数而已。当然,上面的程序效率是非常低的,因为它重复计算了很多子问题。代码实现如下:

 1 public class YanHuiTriangle {  2 //compute C(n,r)  3 public static long c(int n, int r){  4 if(n == 0 || r == 0)  5 return 1;//base condition  6 if(n == r)  7 return 1;//base condition  8 else  9 return c(n-1, r-1) + c(n-1, r); 10  } 11 12 //compute c(n,r) 13 public static long c_dp(int n ,int r){ 14 long[][] dp = new long[n+1][r+1]; 15 16 //init 17 for(int i = 0; i <= n; i++) 18 dp[i][0] = 1;//if(n==0) 19 for(int i = 0; i <= r; i++) 20 dp[0][i] = 1;//if(r==0) 21 for(int i = 0; i <= r; i++)//Assume r < n 22 dp[i][i] = 1;//if(n==r) 23 24 for(int i = 1; i <= n; i++) 25  { 26 for(int j = 1; j <= r; j++) 27  { 28 if(j < i) 29 dp[i][j] = dp[i-1][j] + dp[i-1][j-1]; 30 else if(j > i)//从 i 个元素中选取出 j个元素(j>i 没有意义) 31 dp[i][j] = 0; 32  } 33  } 34 return dp[n][r]; 35  } 36 37 public static void main(String[] args) { 38 39 long start_dp = System.currentTimeMillis(); 40 System.out.println(c_dp(50, 10)); 41 long end_dp = System.currentTimeMillis(); 42 System.out.println("dp use time: " + (end_dp - start_dp) + "ms"); 43 44 long start = System.currentTimeMillis(); 45 System.out.println(c(50,10)); 46 long end = System.currentTimeMillis(); 47 System.out.println("non dp use time: " + (end - start) + "ms"); 48  } 49 }

 

排列与组合的一些定理教案_平行轴定理推导

 

这个示例完美地证明了DP(动态规划)实现和递归实现的差距。是学习DP的一个好示例。如何将一个程序从递归改成DP?看上面的示例就会有启示了。

其次,这也是0-1背包问题分解的思路,对于某件物品,要么拿走,要么不拿走。因此,这个组合公式在DP问题的分析中经常用到

 

重组合公式:从集合{∞·b1∞·b2,….,∞·bn}中选取r个元素,(不考虑次序),一共有多少种组合?

答案是:F(n,r) = C(n+r-1, r)

 

四,二项式定理

(X+Y)n = C(n,0)X0 Yn + C(n,1)X1 Yn-1 +…..+ C(n,n)Xn Y0

“二项式”定理嘛,就是有两个项相加求n次幂。。。。。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/166377.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • AI重新定义web及谷歌验证码安全

    AI重新定义web及谷歌验证码安全云给安全带来的影响距离2006年Amazon发布EC2服务已经过去了11年,在这11年里,发生的不仅仅是AWS收入从几十万美金上涨到100多亿美金,更重要的是云计算已经走进每一家企业。根据信通院发布的“2016云计算白皮书”,目前近90%的企业都已经开始使用云计算(包括公有云、私有云等),这说明大规模云化对于企业而言已经不只是趋势,更是确凿的既成事实。云化普及的同时也给安全带来很多挑战,主要包括:云化导致以硬件设备为主的传统安全方式失效。我在跟企业交流时,不止一家企业提出了这样的担心:在上公有云的过程

  • Java面试题总结:微服务、SpringBoot、SpringCloud

    Java面试题总结:微服务、SpringBoot、SpringCloud

  • HTTP状态码——302「建议收藏」

    理解302表示临时性重定向。访问一个Url时,被重定向到另一个url上。常用于页面跳转。与301的区别301是指永久性的移动,302是暂时性的,即以后还可能有变化其它重定向方式在响应头中加入Location参数。浏览器接受到带有location头的响应时,就会跳转到相应的地址。…

  • JS正则表达式完整版

    JS正则表达式完整版目录引言第一章正则表达式字符匹配攻略1两种模糊匹配2.字符组3.量词4.多选分支5.案例分析第1章小结第二章正则表达式位置匹配攻略1.什么是位置呢?2.如何匹配位置呢?3.位置的特性4.相关案例第二章小结第三章正则表达式括号的作用1.分组和分支结构2.引用分组3.反向引用4.非捕获分组…

  • Python编程语言简介

    Python编程语言简介Python诞生于20世纪90年代初,由荷兰人吉多·范罗苏姆发明。那么,Python这一门编程语言是如何发明的呢?这之中又有怎么的故事呢?请看下面。故事发生在1989年的圣诞节上,吉多先生

  • Java程序猿面试题集(181- 199)

    Java程序猿面试题集(181- 199)

    2021年12月10日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号