未分類
30 5 月 2020

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

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

資深大佬 : prenwang 11

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

如图, 该图形要求一笔画成, 比如 (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)

  • 資深大佬 : gwy15

    从有奇数连接边的点开始，到奇数连接的点停止。
    如果全是偶数，随便哪个都可以。
    如果两个以上奇数连接点，无解。
    不可能只有一个奇数连接边的点。

  • 資深大佬 : Jeffrey0215

    满足一笔画有两种情况，1 图形里没有单数点。2 图形里有两个单数点。
    第二种情况的话选一个单数点作为开始，另一个单数点肯定是终点。

  • 資深大佬 : isukkaw

    现在的程序员都不学图论了？

  • 主 資深大佬 : prenwang

    上代码, 奇偶分析论妈妈们都知道了

  • 資深大佬 : MOONLIGHTT

    可以去看看欧拉通路

  • 資深大佬 : deplives

    没记错的话《离散数学》中有讲过

  • 資深大佬 : hanzichi

    上说的没毛病，欧拉回路，给你找到题做一下 http://acm.hdu.edu.cn/showproblem.php?pid=1878

  • 資深大佬 : daozhihun

    用数学知识解，不要一上来就想着暴力搜。。

  • 資深大佬 : AlghaPorthos

    @hanzichi 这个有奇度点，是欧拉路而非欧拉回路。

  • 資深大佬 : sarvatathagata

    这个有构造方法的，上次 CodeForces 的 Div 1 还考到了呢。就是 dfs，每次走所有当前点的未访问过的出边，如果没有任何出边了就把当前节点压到栈顶。最后栈里就是一条欧拉回路。

    对于欧拉路，在两个奇度点之间连一条边，求新图的欧拉回路，再把多连的那条边从回路里去掉就行了。

  • 主 資深大佬 : prenwang

    小学 2 年级就考这个, 还带动一帮亲妈熬夜苦算, 现在全国小学都这样吗

  • 資深大佬 : 0x4F5DA2

    从 5 出发，到 4 结束，随便画
    （或者反过来，4 出发，5 结束）

  • 資深大佬 : rioshikelong121

    这是不是那个什么七桥问题 小学看书看到过。

  • 資深大佬 : XanderChen

    5 2 4 3 1 5 4 就行了，

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

    这种题家长参与进来就没什么意义了，家长总是用自己的思维做题，而不是问问孩子的想法，再从孩子的想法出发去解决问题。

  • 資深大佬 : XanderChen

    43215425 也行，解题方法很多啊，或者 43245125

  • 資深大佬 : XanderChen

    @XanderChen 想简单了，没想到要求还挺多，丢人了丢人了

  • 資深大佬 : learningman

    奇数偶数点是用来验证是否可行的
    至于具体的画法，dfs 或者 bfs 都行啊，暴力一点 dp
    下周考离散，我这水平估计要挂。。。

  • 資深大佬 : lijialong1313

    图论说了验证是否可行……
    验证就是：
    现在你这个图里，123 都是偶数条线连接的点，意思就是必有相等的入和出
    只有 4 、5 是奇数个，所以要么 4 开始最终终点 5，要么 5 开始最终终点 4 。

    至于找出来……简单的就深度优先搜索，难一点应该是图论的带权图求最短路径方式。

  • 資深大佬 : wwbfred

    七桥问题啊.小学的确倒是接触过…

  • 資深大佬 : Xs0ul

    只要知道从奇数点开始，不是随便凑凑就出来了吗

  • 資深大佬 : jxie0755

    这还真是小学时学的，但是当时是奥数题，知道奇数点和偶数点的奥义就行了

  • 資深大佬 : autoxbc

    中小学奥数题要用技巧将高等数学简化为初等数学，试图升维后借助数学工具都是南辕北辙

  • 資深大佬 : BingZ

    这题的解有很多，凭直觉就能做出来。主要考察小朋友的试错能力，同时也能对“科学方法论”进行实践体验。但为什么要升级到图论或者奇偶数点这种纯粹的数学技巧里面去？完全违背了学习数学的初衷。回想下自己的小学阶段，没人告诉“高深的数学解题技巧”之前，你们不都是凭直觉去尝试的么？至于何时才需要去研究更高层次的东西，那不是小学，甚至都不是初、高中生去做的事情。当作课余了解下倒是可以，提前窥探下数学的博大和奥妙，激发兴趣。不要被应试牵着鼻子走，不要唯解题论英雄。陪着娃一起去解决问题的过程，就很好，这就够了。