如图, 该图形要求一笔画成, 比如 (5-2-4-3-2-1-5-4), 很多妈妈与娃娃彻夜奋战,用穷举法找出了答案, 那么对于程序员来说, 有没有一个非常精简的算法来解答呢?
简单分析:
[ (5, 2), (2, 4), (4, 3), (3, 2), (2, 1), (1, 5), (5, 4) ]
这个分析可能有点愚蠢. 但是
请解救伟大的妈妈和可怜的娃娃们. 好多娃娃 11 点以后才睡觉, 好多妈妈 12 点才睡觉.
1
gwy15 2020-06-12 21:37:33 +08:00 via Android 2
从有奇数连接边的点开始,到奇数连接的点停止。
如果全是偶数,随便哪个都可以。 如果两个以上奇数连接点,无解。 不可能只有一个奇数连接边的点。 |
2
Jeffrey0215 2020-06-12 21:44:55 +08:00
满足一笔画有两种情况,1 图形里没有单数点。2 图形里有两个单数点。
第二种情况的话选一个单数点作为开始,另一个单数点肯定是终点。 |
3
isukkaw 2020-06-12 21:45:34 +08:00 14
现在的程序员都不学图论了?
|
4
prenwang OP 上代码, 奇偶分析论妈妈们都知道了
|
5
MOONLIGHTT 2020-06-12 22:10:49 +08:00
可以去看看欧拉通路
|
6
deplives 2020-06-12 22:18:20 +08:00
没记错的话《离散数学》中有讲过
|
7
hanzichi 2020-06-12 22:30:28 +08:00
楼上说的没毛病,欧拉回路,给你找到题做一下 http://acm.hdu.edu.cn/showproblem.php?pid=1878
|
8
daozhihun 2020-06-12 22:33:32 +08:00
用数学知识解,不要一上来就想着暴力搜。。
|
9
AlghaPorthos 2020-06-12 22:38:23 +08:00
@hanzichi 这个有奇度点,是欧拉路而非欧拉回路。
|
10
sarvatathagata 2020-06-12 22:53:31 +08:00
这个有构造方法的,上次 CodeForces 的 Div 1 还考到了呢。就是 dfs,每次走所有当前点的未访问过的出边,如果没有任何出边了就把当前节点压到栈顶。最后栈里就是一条欧拉回路。
对于欧拉路,在两个奇度点之间连一条边,求新图的欧拉回路,再把多连的那条边从回路里去掉就行了。 |
11
prenwang OP 小学 2 年级就考这个, 还带动一帮亲妈熬夜苦算, 现在全国小学都这样吗
|
12
0x4F5DA2 2020-06-12 23:02:51 +08:00
从 5 出发,到 4 结束,随便画
(或者反过来,4 出发,5 结束) |
13
rioshikelong121 2020-06-12 23:11:04 +08:00
这是不是那个什么七桥问题 小学看书看到过。
|
14
XanderChen 2020-06-12 23:31:48 +08:00 via Android
5 2 4 3 1 5 4 就行了,
与其考虑用算法解决,不如考虑怎么开阔孩子的视野,增强孩子的发散思维的能力。 这种题家长参与进来就没什么意义了,家长总是用自己的思维做题,而不是问问孩子的想法,再从孩子的想法出发去解决问题。 |
15
XanderChen 2020-06-12 23:34:09 +08:00 via Android
43215425 也行,解题方法很多啊,或者 43245125
|
16
XanderChen 2020-06-12 23:39:07 +08:00 via Android
@XanderChen 想简单了,没想到要求还挺多,丢人了丢人了
|
17
learningman 2020-06-13 01:58:54 +08:00
奇数偶数点是用来验证是否可行的
至于具体的画法,dfs 或者 bfs 都行啊,暴力一点 dp 下周考离散,我这水平估计要挂。。。 |
18
lijialong1313 2020-06-13 02:22:55 +08:00
图论说了验证是否可行……
验证就是: 现在你这个图里,123 都是偶数条线连接的点,意思就是必有相等的入和出 只有 4 、5 是奇数个,所以要么 4 开始最终终点 5,要么 5 开始最终终点 4 。 至于找出来……简单的就深度优先搜索,难一点应该是图论的带权图求最短路径方式。 |
19
wwbfred 2020-06-13 03:00:27 +08:00
七桥问题啊.小学的确倒是接触过...
|
20
Xs0ul 2020-06-13 04:25:51 +08:00
只要知道从奇数点开始,不是随便凑凑就出来了吗
|
21
jxie0755 2020-06-13 09:22:10 +08:00 via iPhone
这还真是小学时学的,但是当时是奥数题,知道奇数点和偶数点的奥义就行了
|
22
autoxbc 2020-06-13 10:52:03 +08:00
中小学奥数题要用技巧将高等数学简化为初等数学,试图升维后借助数学工具都是南辕北辙
|
23
BingZ 2020-06-13 11:26:23 +08:00 1
这题的解有很多,凭直觉就能做出来。主要考察小朋友的试错能力,同时也能对“科学方法论”进行实践体验。但为什么要升级到图论或者奇偶数点这种纯粹的数学技巧里面去?完全违背了学习数学的初衷。回想下自己的小学阶段,没人告诉“高深的数学解题技巧”之前,你们不都是凭直觉去尝试的么?至于何时才需要去研究更高层次的东西,那不是小学,甚至都不是初、高中生去做的事情。当作课余了解下倒是可以,提前窥探下数学的博大和奥妙,激发兴趣。不要被应试牵着鼻子走,不要唯解题论英雄。陪着娃一起去解决问题的过程,就很好,这就够了。
|