三九宝宝网宝宝百科宝宝知识

离散数学趣味题目

11月23日 编辑 39baobao.com

[男性生育趣味观]生儿育女,乃是人类得以延续的大事。以往,人们的目光基本上锁定在妻子身上,其实丈夫也是举足轻重的一方,故了解一些男人的生育知识也很有必要。为此,本文向你介绍科学家们的一些新...+阅读

1,Catalan数

饭后,姐妹洗碗,妹妹把姐姐洗过的碗一个一个放进碗橱摞成一摞。共有n个两两相异的碗,洗前也摞成一摞,也许因为妹妹贪玩,碗拿进橱子不及时,姐姐就把洗过的碗摞在傍边:

-

- - - -

— — - -

- - — —

(1)待洗 (2)待摞 (3)已摞

问最后小妹摞起的碗摞可能有几种方式?

这个题目有个同解题是这样的:

一队不同的汽车行进在大街上,它们可以在任何时刻拐进一个死胡同里去加油,然后再出来加入队伍。问你最后出城时汽车队列有多少种可能形式?

呵呵,大家想想,有意思呢!

[简短分析]

这是个有趣的组合问题。组合数学是离散数学的一部分,研究的是组合计数问题。图论原来也是组合数学的一部分,后来才分家的:)。组合计数的一个指导性技巧是,如果对于一个过程的计数不好研究,就可以找一个和它有一一对应的过程,而且该过程相对很好研究,这不是很美吗?

你看看,如果碗有n个,姐姐每方下一个,就画一个“(”,妹妹如果摞一个,就画一个“)”,如果妹妹不贪玩,刚放下就能放好,串就是“()()()……()”,对吧?现在你来考虑一下,下次我说答案:)。

汽车车队也是如此,车进了胡同就画“(”,出来时再画“)”,而没有进胡同的就是“()”,呵呵,所以同解呢。

离散的问题,技巧性很大,初看问题的解没有规律,仿佛量体裁衣般的,但也有指导性的思路对吧?

2,拉姆赛问题

朴素的方式叙述:

r(p,q)是任意给的人群中必有p人相识或必有q人彼此不相识的人群人数之最小值。例如,r(3,3)=6,就是说,任意个的人群,最少6个人,一定可满足其中3个人相识,或3个人互相不认识。r(p,q)就称为拉姆赛数。

图论的方式叙述:

Any p,q in N,把一个完全图G用红与蓝两色进行边涂色,每条边一种颜色,其结果或者有一个红色p边形,连同其全部对角线皆为红色,或者有一个蓝色q边形,连同其全部对角线皆为蓝色,G最小的顶点数,能保证出现上述结果,就是拉姆赛数r(p,q)。

经过几代人的努力,加上计算机的帮忙,现在人类求的9个非平凡的拉姆赛数:

r(3,3)=6,r(3,4)=9,r(3,5)=14

r(3,6)=18,r(3,7)=23,r(3,8)=28

r(3,9)=36,r(4,4)=18,r(4,5)=25

呵呵,你来试试,你能给出哪些拉姆赛数的推理过程?

[背景趣闻]

关于求拉姆赛数的艰巨性,匈牙利数学家厄尔多斯曾用下面的话比喻:

某年某月某日,一伙外星强盗入侵地球,威胁道,若不能一年内求出r(5,5),他们将灭绝人类!面对如此生死关头,人类应当召集全球所有的数学家和计算机专家,夜以继日的计算r(5,5),以求人类免于灭顶之灾;如果外星人要我们求得r(6,6),我们就别无选择了,干脆直接开战,放手一搏:)。

3,梦中情人

约翰的梦中情人长着金黄色的头发,蓝蓝的眼睛,纤细的身子,高高的个子。他认识阿黛尔,贝蒂,卡洛尔和多丽丝四位小姐,其中一位是约翰的梦中情人。(1)只有三位小姐是蓝眼睛和细身材。(2)只有两位是黄头发和高个子(3)只有两位是细身材和高个子。(4)只有一位是蓝眼睛和黄头发(5) 阿黛尔和贝蒂眼睛颜色相同。(6)贝蒂和卡洛尔头发颜色相同(7)卡洛尔和多丽丝身材不同(8)多丽丝和阿黛尔身高相同。四位中谁是约翰的梦中情人?

[简单分析]

呵呵,显然这是个数理逻辑问题了。可以建立形式化的模型来分析,也可以用朴素的推理过程来做。很有意思的,这是离散数学的魅力!

以下为关联文档:

安奈儿童装2017秋冬新品发布,用心探索时尚与趣味成人的时尚元素有拼接、撞色、印花……儿童的时尚元素又是什么?让安奈儿2017秋冬新品告诉你,如何用童心探索时尚世界。近日,安奈儿2017秋冬新品发布会绚丽上演,开启一场别具一...

趣味练习让数学变成飞扬的青春很多数学成绩较好的学生都会说 数学是玩出来的 。数学大师陈省身曾给青少年数学爱好者题词 数学好玩 四个字。只有让学生认为数学好玩,才能喜欢上数学,才能将数学学得更好。这...

趣味英语让孩子们的英语阅读更有乐趣小学英语阅读教学对于孩子的英语基础有着无可替代的作用,在这个阶段,孩子将完成英语阅读技能以及习惯的启发与养成,这对于日后更深一层的英语学习来说是根本性的作用。在英语阅...

构建充满趣味的软环境,为主动学习添动力《看图写话》课例点评一、构建充满趣味的软环境,为主动学习添动力良好课堂教学软环境的构建是教师深层次思维、认知境界的一种体现,也是教师教学个性的体现,良好的课堂软环境会帮助学生生长出比知...

趣味方法教你更快学英语趣味方法教你更快学英语 找到英语广播台或播客。现在有无数的播客提供各类娱乐,政治,新闻。搜寻的最佳方式就是从你经常看的电视频道找一个出来。挑一个你感兴趣的,开车的时候...

中医方剂趣味记忆第四章第四章 清热剂 一、清气分热 白虎汤《伤寒论》:师母干净。/白虎精食母肝。 竹叶石膏汤《伤寒论》:草人半夜卖米糕。 二、清营凉血 清营汤《温病条辨》:乔皇帝住西单卖银元。/乔...

小小家蚕,趣味多多5月8日,第一次见到蚕卵的小朋友,被它那小小卵里竟蕴育着的生命,感到惊奇。黑色芝麻粒般大的蚕卵,在孵化盒中沙沙作响,也将在孵化盒的保护下破壳而出。作为年轻的我,也感到有点惶恐...

构建充满趣味的软环境,为主动学习添动力《看图写话》一、构建充满趣味的软环境,为主动学习添动力 良好课堂教学软环境的构建是教师深层次思维、认知境界的一种体现,也是教师教学个性的体现,良好的课堂软环境会帮助学生生长出比知...

印度的趣味教学法越来越多的印度教育专家发现,真正的学习是在合上课本之后开始的。诸多试验表明,只要运用得法,一个废弃的包装袋、几根火柴棒等都可以作为教具,其作用远比传统的教室黑板粉笔教学...

推荐阅读
图文推荐