算法-一群人中至少有三个人都互相认识或互相不认识问题变种 该如何建模程序实现

算法-一群人中至少有三个人都互相认识或互相不认识问题变种 该如何建模程序实现

偏爱自由 发布于 2016-10-14 字数 453 浏览 1244 回复 1

原题:任意一群人中至少有三个人都互相认识或互相不认识,求人数至少为多少。
这个问题是比较经典的问题,可以用 抽屉理论 解决。
不过如果把条件中的三个人改为 四个人,即:
任意一群人中保证至少有四个人都互相认识或互相不认识,求人数至少为多少。
再做分析时候就会变得很复杂。
我想用设计程序来求解,却一时不懂如何下手。求做算法的大牛指导一二,不胜感激。

最好配有数据结构跟核心算法剖析。
语言不做要求,主流语言、脚本都可。

如果你对这篇文章有疑问,欢迎到本站 社区 发帖提问或使用手Q扫描下方二维码加群参与讨论,获取更多帮助。

扫码加入群聊

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

想挽留 2017-02-22 1 楼

这是一个经典的数学问题,围绕这个问题的一系列理论称为Ramsey理论,“任意一群人中至少r个人相互认识,或者s个人相互不认识”这个问题的答案称为Ramsey数,写作R(r,s)
求这个数是非常困难的,更别说用计算机找到合适的算法了。以下内容摘自维基百科:
已知的拉姆齐数非常少,保罗·艾狄胥曾以一个故事来描述寻找拉姆齐数的难度:“想像有队外星人军队在地球降落,要求取得R(5,5)的值,否则便会毁灭地球。在这个情况,我们应该集中所有电脑和数学家尝试去找这个数值。若它们要求的是R(6,6)的值,我们要尝试毁灭这班外星人了。”
下面是一些已知的结果,R(4,4) = 18,而R(5,5)现在还没人知道……只有一些定理可以确定他们的上下界。
s 1 2 3 4 5 6 7 8 9 10
1 1 1 1 1 1 1 1 1 1 1
2 1 2 3 4 5 6 7 8 9 10
3 1 3 6 9 14 18 23 28 36 40—43
4 1 4 9 18 25 36—41 49—61 56—84 73—115 92—149
5 1 5 14 25 43—49 58—87 80—143 101—216 126—316 144—442
6 1 6 18 36—41 58—87 102—165 113—298 132—495 169—780 179—1171
7 1 7 23 49—61 80—143 113—298 205—540 217—1031 241—1713 289—2826
8 1 8 28 56—84 101—216 132—495 217—1031 282—1870 317—3583 331—6090
9 1 9 36 73—115 126—316 169—780 241—1713 317—3583 565—6588 581—12677
10 1 10 40—43 92—149 144—442 179—1171 289—2826 331—6090 581—12677 798—23556

参考:
http://zh.wikipedia.org/wiki/%E6%8B%89%E5%A7%86%E9%BD%90%E5%AE%9A%E7%90%86