首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
V2EX  ›  问与答

一个算法题目:女学生散步问题

  •  
  •   zemora · 2018-11-09 10:00:00 +08:00 · 2089 次点击
    这是一个创建于 396 天前的主题,其中的信息可能已经有所发展或是发生改变。

    这个问题叫做 Kirkman's Schoolgirl Problem,即某学校有十五名女生,她们经常每天三人一行、共组成五行去散步,问要怎样安排才能使得在一周的时间里,任何两个女生恰好在同一行中散步一次?

    找出一种来不难,网上有很多,我在想怎么能罗列出所有的解法来。不知道大家有什么好办法没有?

    15 回复  |  直到 2018-11-09 14:42:46 +08:00
        1
    Deville   2018-11-09 10:02:14 +08:00
    女生长得好看么;
    有微信号么;
    哪个学校的;
    确定都是女生并没有混入女装大佬么?
        2
    alikesi   2018-11-09 10:05:48 +08:00
    @Deville 充分考虑程序边界条件,优秀。
        3
    Deville   2018-11-09 10:10:26 +08:00
    @alikesi 其实想想这道题还是挺有趣的喔
        4
    coderluan   2018-11-09 10:28:44 +08:00
    直接设置 15 个变量,然后暴力枚举所有情况,最后再挨个检查是否符合要求,没要求复杂度的前提下,暴力枚举就是最好的算法。
        5
    mathzhaoliang   2018-11-09 10:32:17 +08:00
    @coderluan 伪代码呢? talk is cheap, show me the code.
        6
    dikT   2018-11-09 10:35:49 +08:00
        7
    Fulcrum   2018-11-09 10:55:40 +08:00 via Android
    像一个复杂的指派规划。。。
        8
    coderluan   2018-11-09 11:15:57 +08:00   ♥ 2
    @mathzhaoliang

    "talk is cheap, show me the code." 这话是用来解决技术争论的,你没提自己的观点和反对意见,也就是没争论。
    现在的情况,是别人帮忙提供解决问题的思路,你却指责对方不给代码,这是什么行为,我不就不说了。
    希望你只是不小心滥用了词语。
        9
    ryd994   2018-11-09 11:52:32 +08:00 via iPhone
    第一列 A 不动,第二列 B 每次 shift1,第三列 C 每次 shift2
    5 天后,所有的 A 都和所有的 B 并排过,所有的 B 都和所有的 C 并排过。这个应该不难证。
    剩下 AC 并排关系。A1 和 B135 并排然后绕回来 24 正好
    完成
        10
    ryd994   2018-11-09 11:54:57 +08:00 via iPhone
    等等,还漏了 ABC 各自内部,我再想想
        11
    kenv07   2018-11-09 11:59:23 +08:00
    楼上说暴力枚举的,15 的阶乘等于 1,307,674,368,000,所以其实可行就是要花点时间
        12
    wdv2ly   2018-11-09 11:59:24 +08:00
    楼上说得对啊,这题目用穷举是简单啊,还需要伪代码吗
        13
    zemora   2018-11-09 12:04:18 +08:00
    @wdv2ly 要是穷举就行,还要算法做什么。Leetcode 还有时间限制呢。
        14
    wdv2ly   2018-11-09 12:14:52 +08:00
    @zemora 穷举也是算法的一种啊。你只说找出所有组合,又没说有其它要求,那肯定直接穷举咯。
        15
    zcjfesky   2018-11-09 14:42:46 +08:00 via Android   ♥ 1
    这是 Kirkman 三元集的 v15 情况, 非同构组合有 7 个

    原始穷举法复杂度是 15!的七次方,可以等到地球毁灭
    可以考虑深度搜索剪枝,具体参考 sovling the kirksman schoolgirl problem in a few minutes 这篇 ppt,最终剪枝剪到复杂度 20000 的程度
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   3045 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 30ms · UTC 11:12 · PVG 19:12 · LAX 03:12 · JFK 06:12
    ♥ Do have faith in what you're doing.