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

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

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

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

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

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

    "talk is cheap, show me the code." 这话是用来解决技术争论的,你没提自己的观点和反对意见,也就是没争论。
    现在的情况,是别人帮忙提供解决问题的思路,你却指责对方不给代码,这是什么行为,我不就不说了。
    希望你只是不小心滥用了词语。
    ryd994
        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 正好
    完成
    ryd994
        10
    ryd994  
       2018-11-09 11:54:57 +08:00 via iPhone
    等等,还漏了 ABC 各自内部,我再想想
    kenv07
        11
    kenv07  
       2018-11-09 11:59:23 +08:00
    楼上说暴力枚举的,15 的阶乘等于 1,307,674,368,000,所以其实可行就是要花点时间
    wdv2ly
        12
    wdv2ly  
       2018-11-09 11:59:24 +08:00
    楼上说得对啊,这题目用穷举是简单啊,还需要伪代码吗
    zemora
        13
    zemora  
    OP
       2018-11-09 12:04:18 +08:00
    @wdv2ly 要是穷举就行,还要算法做什么。Leetcode 还有时间限制呢。
    wdv2ly
        14
    wdv2ly  
       2018-11-09 12:14:52 +08:00
    @zemora 穷举也是算法的一种啊。你只说找出所有组合,又没说有其它要求,那肯定直接穷举咯。
    zcjfesky
        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 的程度
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2907 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 14:16 · PVG 22:16 · LAX 07:16 · JFK 10:16
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.