离散数学趣味题目.doc
《离散数学趣味题目.doc》由会员分享,可在线阅读,更多相关《离散数学趣味题目.doc(4页珍藏版)》请在三一文库上搜索。
1、离散数学趣味题目1,Catalan数饭后,姐妹洗碗,妹妹把姐姐洗过的碗一个一个放进碗橱摞成一摞。共有n个两两相异的碗,洗前也摞成一摞,也许因为妹妹贪玩,碗拿进橱子不及时,姐姐就把洗过的碗摞在傍边:(1)待洗(2)待摞(3)已摞问最后小妹摞起的碗摞可能有几种方式?这个题目有个同解题是这样的:一队不同的汽车行进在大街上,它们可以在任何时刻拐进一个死胡同里去加油,然后再出来加入队伍。问你最后出城时汽车队列有多少种可能形式?呵呵,大家想想,有意思呢!简短分析这是个有趣的组合问题。组合数学是离散数学的一部分,研究的是组合计数问题。图论原来也是组合数学的一部分,后来才分家的:)。组合计数的一个指导性技巧是
2、,如果对于一个过程的计数不好研究,就可以找一个和它有一一对应的过程,而且该过程相对很好研究,这不是很美吗?你看看,如果碗有n个,姐姐每方下一个,就画一个“(”,妹妹如果摞一个,就画一个“)”,如果妹妹不贪玩,刚放下就能放好,串就是“()()()()”,对吧?现在你来考虑一下,下次我说答案:)。汽车车队也是如此,车进了胡同就画“(”,出来时再画“)”,而没有进胡同的就是“()”,呵呵,所以同解呢。离散的问题,技巧性很大,初看问题的解没有规律,仿佛量体裁衣般的,但也有指导性的思路对吧?2,拉姆赛问题朴素的方式叙述:r(p,q)是任意给的人群中必有p人相识或必有q人彼此不相识的人群人数之最小值。例如
3、,r(3,3)=6,就是说,任意个的人群,最少6个人,一定可满足其中3个人相识,或3个人互相不认识。r(p,q)就称为拉姆赛数。图论的方式叙述:Anyp,qinN,把一个完全图G用红与蓝两色进行边涂色,每条边一种颜色,其结果或者有一个红色p边形,连同其全部对角线皆为红色,或者有一个蓝色q边形,连同其全部对角线皆为蓝色,G最小的顶点数,能保证出现上述结果,就是拉姆赛数r(p,q)。经过几代人的努力,加上计算机的帮忙,现在人类求的9个非平凡的拉姆赛数:r(3,3)=6,r(3,4)=9,r(3,5)=14r(3,6)=18,r(3,7)=23,r(3,8)=28r(3,9)=36,r(4,4)=1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 趣味 题目
链接地址:https://www.31doc.com/p-1879177.html