另类约瑟夫问题 – 技术圈



另类约瑟夫问题 – 技术圈

总共有 N 个人编号为 1 号到 N 号(每个人的编号一直不变),一开始只取 1 号到 M 号沿顺时针围成一圈(脸都对着圆心)。同样是依次报数,当轮到报数为 k 的人时,如果此人的编号为奇数,则将剩余的人中编号最小的人插入此人右侧,如果此人的编号为偶数,则将剩余的人中编号最小的人插入此人左侧。并从报数为 k 的人左侧开始重新开始重复此过程。当围成一个 N 个人的圈后,继续从报数为 k 的人左侧重新开始沿顺时针报数,当有人再次报数为 k 时,此人出列。继续从出列的人的左侧重新开始重复此过程。直到围成圈的人数再次为 M 时停止。

问: 最后留下的 M 个人中,有多少来自一开始取的 M 个人。

注: 链表中当 N 非常大时,考虑到时间复杂度,k 可以取 k≪N。

示例: 假设 N=6, M=4, k=2。则一开始取的人编号分别 1,2,3,4 的人围成一圈。然后从 1 开始报两个数。 2 为偶数,则圆圈中编号为 2 的人左侧位置加一个 5,圆圈的顺序变为: 1,2,5,3,4。 又从 5 开始重新报数,报 2 的人为 3 号,则往其圆圈中的右侧位置加一个 6。圆圈顺序变为 1,2,5,6,3,4。 此时 6 人全部在圆圈中,继续从刚刚的 3 号的下一位 4 号报数,报 2 的人为 1 号,则 1 号出列。圆圈顺序变为 2,5,6,3,4,继续从 1 号下一位开始报数,下一次报 2 的为 5 号,则 5 号出列。则圆圈的顺序变为 2,6,3,4。其中 2,3,4 号来自于一开始取的 1,2,3,4 中,所以答案为 3。


Read full article from 另类约瑟夫问题 – 技术圈


No comments:

Post a Comment

Labels

Algorithm (219) Lucene (130) LeetCode (97) Database (36) Data Structure (33) text mining (28) Solr (27) java (27) Mathematical Algorithm (26) Difficult Algorithm (25) Logic Thinking (23) Puzzles (23) Bit Algorithms (22) Math (21) List (20) Dynamic Programming (19) Linux (19) Tree (18) Machine Learning (15) EPI (11) Queue (11) Smart Algorithm (11) Operating System (9) Java Basic (8) Recursive Algorithm (8) Stack (8) Eclipse (7) Scala (7) Tika (7) J2EE (6) Monitoring (6) Trie (6) Concurrency (5) Geometry Algorithm (5) Greedy Algorithm (5) Mahout (5) MySQL (5) xpost (5) C (4) Interview (4) Vi (4) regular expression (4) to-do (4) C++ (3) Chrome (3) Divide and Conquer (3) Graph Algorithm (3) Permutation (3) Powershell (3) Random (3) Segment Tree (3) UIMA (3) Union-Find (3) Video (3) Virtualization (3) Windows (3) XML (3) Advanced Data Structure (2) Android (2) Bash (2) Classic Algorithm (2) Debugging (2) Design Pattern (2) Google (2) Hadoop (2) Java Collections (2) Markov Chains (2) Probabilities (2) Shell (2) Site (2) Web Development (2) Workplace (2) angularjs (2) .Net (1) Amazon Interview (1) Android Studio (1) Array (1) Boilerpipe (1) Book Notes (1) ChromeOS (1) Chromebook (1) Codility (1) Desgin (1) Design (1) Divide and Conqure (1) GAE (1) Google Interview (1) Great Stuff (1) Hash (1) High Tech Companies (1) Improving (1) LifeTips (1) Maven (1) Network (1) Performance (1) Programming (1) Resources (1) Sampling (1) Sed (1) Smart Thinking (1) Sort (1) Spark (1) Stanford NLP (1) System Design (1) Trove (1) VIP (1) tools (1)

Popular Posts