组合数学 鸽巢原理
教程导读
学研发网的这篇信息学奥赛技术教程文章主要介绍了组合数学 鸽巢原理,现在分享给大家,供学习和参考。文章包含835字,纯文字阅读大概需要3分钟。
教程信息
鸽巢原理
鸽巢原理(Pigeonhole Principle),也被称为鸽笼原理
或抽屉原理
,是一种基本的计数原理。
该原理反映一个基本事实:如果有n个鸽子被放到不超过n个鸽巢中,那么必定有至少一个鸽巢里面有两只或两只以上的鸽子。
鸽巢原理根据适用范围又分为第一鸽巢原理和第二鸽巢原理。
1、第一鸽巢原理/弱鸽巢原理
(1)把多于n个的物体放到n个抽屉里,则至少有一个抽屉里的东西不少于两件。
(2)把多于m*n+1(n不为0)个的物体放到n个抽屉里,则至少有一个抽屉里有不少于(m+1)的物体。
(3)把无数还多件物体放入n个抽屉,则至少有一个抽屉里有无数个物体
2、第二鸽巢原理/强鸽巢原理
把m*n-1个物体放入n个抽屉中,其中必有一个抽屉中至多有m—1个物体。
例如,将3×5-1=14个物体放入5个抽屉中,则必定有一个抽屉中的物体数少于等于3-1=2)。
3、鸽巢原理的使用
(1)运用抽屉原理的核心是分析清楚哪个是物件,哪个是抽屉:较多的一方就是物件,较少的一方就是抽屉。
例如,属相是有12个,那么任意37个人中,至少有一个属相是不少于4个人。这时将属相看成12个抽屉,则一个抽屉中有 37/12,即3余1,余数不考虑,而向上考虑取整数,所以这里是3+1=4个人,但这里需要注意的是,前面的余数1和这里加上的1是不一样的。
(2)鸽巢原理通常遵循最差原则:即考虑所有可能情况中,最不利于某件事情发生的情况。
例如,有300人到招聘会求职,其中软件设计有100人,市场营销有80人,财务管理有70人,人力资源管理有50人。那么至少有多少人找到工作才能保证一定有70人找的工作专业相同呢?
此时我们考虑的最差情况为:软件设计、市场营销和财务管理各录取69人,人力资源管理的50人全部录取,则此时再录取1人就能保证有70人找到的工作专业相同。因此至少需要69*3+50+1=258人。
教程咨询
如果章节内容看不懂,可以联系作者。
教程总结
以上是学研发网为您提供组合数学 鸽巢原理的全部内容,希望教程文章能够帮你了解学习组合数学 鸽巢原理,解决所遇到的问题。 如果觉得学研发网信息学奥赛教程内容还不错,欢迎将学研发网网站推荐给身边需要的人。
教程备注
版权声明:教程内容为学研发网整理和编写,如需转载请联系站长并附上文章原始链接和原始作者信息。
手机阅读
扫描二维码推送至手机访问。
本文链接:http://www.xueyanfa.com/xinaojiaocheng/xinaozhongji-253.html