V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
prenwang
V2EX  ›  程序员

小学生数学题(编程解答)挑战

  •  
  •   prenwang · 2020-06-12 21:35:36 +08:00 · 2957 次点击
    这是一个创建于 1624 天前的主题,其中的信息可能已经有所发展或是发生改变。

    image

    如图, 该图形要求一笔画成, 比如 (5-2-4-3-2-1-5-4), 很多妈妈与娃娃彻夜奋战,用穷举法找出了答案, 那么对于程序员来说, 有没有一个非常精简的算法来解答呢?

    简单分析:

    • 一共有 7 条边, 7 条边每一次都会被画并且仅画一次
    • 每一次一条边只能单向画一次 (比如存在(5,2), 就不能存在(2, 5)),
    • 必须是连续的划线(比如 (5, 2), (2, 4) 就是连续的 )

    [ (5, 2), (2, 4), (4, 3), (3, 2), (2, 1), (1, 5), (5, 4) ]

    这个分析可能有点愚蠢. 但是

    请解救伟大的妈妈和可怜的娃娃们. 好多娃娃 11 点以后才睡觉, 好多妈妈 12 点才睡觉.

    23 条回复    2020-06-13 11:26:23 +08:00
    gwy15
        1
    gwy15  
       2020-06-12 21:37:33 +08:00 via Android   ❤️ 2
    从有奇数连接边的点开始,到奇数连接的点停止。
    如果全是偶数,随便哪个都可以。
    如果两个以上奇数连接点,无解。
    不可能只有一个奇数连接边的点。
    Jeffrey0215
        2
    Jeffrey0215  
       2020-06-12 21:44:55 +08:00
    满足一笔画有两种情况,1 图形里没有单数点。2 图形里有两个单数点。
    第二种情况的话选一个单数点作为开始,另一个单数点肯定是终点。
    isukkaw
        3
    isukkaw  
       2020-06-12 21:45:34 +08:00   ❤️ 14
    现在的程序员都不学图论了?
    prenwang
        4
    prenwang  
    OP
       2020-06-12 21:49:32 +08:00
    上代码, 奇偶分析论妈妈们都知道了
    MOONLIGHTT
        5
    MOONLIGHTT  
       2020-06-12 22:10:49 +08:00
    可以去看看欧拉通路
    deplives
        6
    deplives  
       2020-06-12 22:18:20 +08:00
    没记错的话《离散数学》中有讲过
    hanzichi
        7
    hanzichi  
       2020-06-12 22:30:28 +08:00
    楼上说的没毛病,欧拉回路,给你找到题做一下 http://acm.hdu.edu.cn/showproblem.php?pid=1878
    daozhihun
        8
    daozhihun  
       2020-06-12 22:33:32 +08:00
    用数学知识解,不要一上来就想着暴力搜。。
    AlghaPorthos
        9
    AlghaPorthos  
       2020-06-12 22:38:23 +08:00
    @hanzichi 这个有奇度点,是欧拉路而非欧拉回路。
    sarvatathagata
        10
    sarvatathagata  
       2020-06-12 22:53:31 +08:00
    这个有构造方法的,上次 CodeForces 的 Div 1 还考到了呢。就是 dfs,每次走所有当前点的未访问过的出边,如果没有任何出边了就把当前节点压到栈顶。最后栈里就是一条欧拉回路。

    对于欧拉路,在两个奇度点之间连一条边,求新图的欧拉回路,再把多连的那条边从回路里去掉就行了。
    prenwang
        11
    prenwang  
    OP
       2020-06-12 22:55:46 +08:00
    小学 2 年级就考这个, 还带动一帮亲妈熬夜苦算, 现在全国小学都这样吗
    0x4F5DA2
        12
    0x4F5DA2  
       2020-06-12 23:02:51 +08:00
    从 5 出发,到 4 结束,随便画
    (或者反过来,4 出发,5 结束)
    rioshikelong121
        13
    rioshikelong121  
       2020-06-12 23:11:04 +08:00
    这是不是那个什么七桥问题 小学看书看到过。
    XanderChen
        14
    XanderChen  
       2020-06-12 23:31:48 +08:00 via Android
    5 2 4 3 1 5 4 就行了,

    与其考虑用算法解决,不如考虑怎么开阔孩子的视野,增强孩子的发散思维的能力。

    这种题家长参与进来就没什么意义了,家长总是用自己的思维做题,而不是问问孩子的想法,再从孩子的想法出发去解决问题。
    XanderChen
        15
    XanderChen  
       2020-06-12 23:34:09 +08:00 via Android
    43215425 也行,解题方法很多啊,或者 43245125
    XanderChen
        16
    XanderChen  
       2020-06-12 23:39:07 +08:00 via Android
    @XanderChen 想简单了,没想到要求还挺多,丢人了丢人了
    learningman
        17
    learningman  
       2020-06-13 01:58:54 +08:00
    奇数偶数点是用来验证是否可行的
    至于具体的画法,dfs 或者 bfs 都行啊,暴力一点 dp
    下周考离散,我这水平估计要挂。。。
    lijialong1313
        18
    lijialong1313  
       2020-06-13 02:22:55 +08:00
    图论说了验证是否可行……
    验证就是:
    现在你这个图里,123 都是偶数条线连接的点,意思就是必有相等的入和出
    只有 4 、5 是奇数个,所以要么 4 开始最终终点 5,要么 5 开始最终终点 4 。

    至于找出来……简单的就深度优先搜索,难一点应该是图论的带权图求最短路径方式。
    wwbfred
        19
    wwbfred  
       2020-06-13 03:00:27 +08:00
    七桥问题啊.小学的确倒是接触过...
    Xs0ul
        20
    Xs0ul  
       2020-06-13 04:25:51 +08:00
    只要知道从奇数点开始,不是随便凑凑就出来了吗
    jxie0755
        21
    jxie0755  
       2020-06-13 09:22:10 +08:00 via iPhone
    这还真是小学时学的,但是当时是奥数题,知道奇数点和偶数点的奥义就行了
    autoxbc
        22
    autoxbc  
       2020-06-13 10:52:03 +08:00
    中小学奥数题要用技巧将高等数学简化为初等数学,试图升维后借助数学工具都是南辕北辙
    BingZ
        23
    BingZ  
       2020-06-13 11:26:23 +08:00   ❤️ 1
    这题的解有很多,凭直觉就能做出来。主要考察小朋友的试错能力,同时也能对“科学方法论”进行实践体验。但为什么要升级到图论或者奇偶数点这种纯粹的数学技巧里面去?完全违背了学习数学的初衷。回想下自己的小学阶段,没人告诉“高深的数学解题技巧”之前,你们不都是凭直觉去尝试的么?至于何时才需要去研究更高层次的东西,那不是小学,甚至都不是初、高中生去做的事情。当作课余了解下倒是可以,提前窥探下数学的博大和奥妙,激发兴趣。不要被应试牵着鼻子走,不要唯解题论英雄。陪着娃一起去解决问题的过程,就很好,这就够了。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1188 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 18:15 · PVG 02:15 · LAX 10:15 · JFK 13:15
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.