※ 引述《Leon (Achilles)》之铭言： : : 推 RockLee:不好意思不是很懂L大的意思 Third round拿X跟2 unkonws比 02/13 15:52 : : → RockLee:就可以知道5th吗? 以下123与ABC的情形要如何区分呢? 02/13 15:52 : : → RockLee:(game 1) 1 2 9 (game A) 1 2 7 02/13 15:52 : : → RockLee:(game 2) 3 4 5 (game B) 3 4 6 02/13 15:52 : : → RockLee:(game 3) 6 7 8 (game C) 5 8 9 02/13 15:53 : 我留你的例子和下面写的东西. 你需要去加强分析的概念, 以及 Quick sort Pivot 的使用. 如果你用上面 Game (1,2,3) 的例子, 以及照你的定义 号码代表车子真正的速度 那麽, median of median 这一步 是拿 cars 2,4,7 来比. 此时 median of median 是 4. 把这个当作 Pivort, 可以保证 2 < 4, and 1 < 2 from step 1. and 3 < 4 from step 1. 所以我得到 (1,2,3) 比 car 4 快, 以及 (5,7,8) 比 4 慢. 但 (6, 9) 此时是 unknown. 这个题目 scale 比较小, 所以下一步会是比 (4,6,9) 然後我就可以知道, (1,2,3) 比 4 快, (6), (9), (5), (7,8) 比 4 慢. 用这个 Pivort, 我找到了前四个 element (顺序不明), 此时要找第五个, 会在 6,9,5 之间产生. 你每次用 median of median, 干掉某个比例的 element, 很快就找到了. 你参照一下 http://stackoverflow.com/questions/4075289/race-car-puzzle 看 answered Mar 9 '11 at 22:59 Tom Sirgedas 的答案, 我没有去 trace 每一步, 但大致上应该是对的. : -- :

※ 发信站: 批踢踢实业坊(ptt.cc) : ◆ From: 142.136.127.112 : 推 RockLee:其实我举例的意思是数字小的就是比较快的 以game 123为例 02/13 16:36 : → RockLee:Third round会拿4 6 9来比 但都不是5th 02/13 16:36 : → Leon:you can draw a graph and it will become clear 02/13 16:56 : → Leon:the third round will tell 4 is the 4th of the cars 02/13 16:57 : 推 RockLee:But how to tell which car is the 5th after third round 02/13 17:10 : → Leon:http://en.wikipedia.org/wiki/Selection_algorithm 02/14 01:48 : → Leon:去读 median of median 那一段 02/14 01:48 : 推 RockLee:Median of Medians那段 看来主要是在讲 Median of Medians 02/14 09:41 : → RockLee:保证大於及小於某固定比例的cases 不过看完之後还是无法厘 02/14 09:41 : → RockLee:清我原本的问题: L大完整的步骤到底是什麽? 02/14 09:41 : → RockLee:就第一篇回文 9 cars 的描述 我原本以为只要 Round 3 拿 X 02/14 09:42 : → RockLee:跟 2 unkonws 比完就可以知道哪辆车是 5th 不过就我举的例 02/14 09:42 : → RockLee:子 Game 123 来看并非如此 02/14 09:42 : → RockLee:L大有空的话 可否好人做到底举个 49 cars 的 worst case 02/14 09:42 : → RockLee:说明如何保证在 16 步之内找到 25th car? 02/14 09:43 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 142.136.127.112 ※ 编辑: Leon 来自: 142.136.127.112 (02/14 10:22)