106建中學科能力競賽初試
把1到2017這2017個自然數，按順時鐘方向依序排列在一個圓周上，由1開始，順時鐘方向，保留1，擦去2，保留3，擦去4，以此規則，每隔一個數就擦去一個數，請問最後一個擦去的數字為何。 [size=3]以前看過如下解法。[/size][size=3][/size]
[size=3]先考慮: 如果共有 2ⁿ 個數，則易知最後一個擦去的數字為 1。[/size]
[size=3][/size]
[size=3]現在共有 2017 個數，把它視為 2¹¹ = 2048 個數擦去 31 個數後所留，回補 31 個數後的那個 "1" 的位置即為所求 = 2017 - 30 = 1987。[/size]
[size=3][/size]
[size=3]當然也可以由 2017 個數擦去 993 個剩 1024 = 2¹⁰個數，那個 "1" 的位置即為所求 = 1+2*993 = 1987。[/size]
[size=3][/size]
[size=3][/size] 感謝分享，真是妙解 可以google "Josephus Problem"
其實是一樣的 將2017用二進位表示 11111100001 ---------->(把最前面數字移到最後) 變成11111000011
還原此數的二進位變回十進位
即為1987 前幾天發現這次107中山大學雙週一題第一學期第五題的題目跟這題幾乎一模一樣，不過還是時間截止再丟上來討論，抄個題先
一疊紙牌有 2018 張標記 1 到 2018，其每張紙牌數字皆不同。這疊紙牌並無按照數字
大小做排序。將最上面的牌抽出並且放到桌上，而下一張牌放置於這疊紙牌的最後一張。
之後新的最上面那張牌再抽出並且放到之前桌上那張牌的右邊，然後其下一張牌再放置於
這疊紙牌的最後一張。此過程−將上面這張牌放到之前桌上那張牌的右邊並且下一張牌再
抽放置於牌組的最後一張，重複過程直到所有牌都被放到桌上為止。發現從左讀到右，這
桌上的牌之順序為 1, 2, 3, . . ., 2017, 2018。請問原本那疊紙牌中，有多少張卡片在號碼
為 2017 的卡片上面？
可以先討論16張牌情形，從上到下(仿造約瑟夫問題就是劃一個圓)
編號1-16，倒數第二張會是8，
15張是6，14張是4。同理，17張是10，18張是12
所以這題知道2048張是1024，2018就是1024-30*2=964，編號964的上方有963張就是答案
頁:
[1]