回複:請教:Counting-off Puzzles

回答: 請教:Counting-off Puzzlesbangbang98142012-06-18 19:44:30

這樣的問題有規律可循。樓上JINJING的解法是對數到7的人退出的一般遞推公式。

如果按以上方法,數到n的人退出,則有以下遞推公式:

1. 如果隻有1人,則其為最後剩下的人。

2. 如果有x個人時,最後剩下的是y號,則有x+1人時,最後剩下的號是(y+n)對 x+1“取模”。這裏的”取模“與正常的取模稍有不同。因為沒有0號,所以對  x+1 取模為0時,對  x+1 “取模”的結果為 x+1 。

證明:當有x+1人時,淘汰一人,即n號後,還剩x人。此時從n+1號開始所有人的號碼實際對應x人時相應號碼+n對x+1“取模”,所以最後剩下的號是x個人時,最後剩下號碼+n對x+1“取模”,即(y+n)對 x+1“取模”。

以上題為例,n=7,根據上述遞推公式可得:

f(1) = 1, 即隻有1人,則1號為最後剩下的人

f(2) = (1 + 7) MOD 2 = 2. 這裏的MOD為上述“取模”,下同。

f(3) = (2 + 7) MOD 3 = 3

f(4) = (3 + 7) MOD 4 = 2

f(5) = (2 + 7) MOD 5 = 4

f(6) = (4 + 7) MOD 6 = 5

f(7) = (5 + 7) MOD 7 = 5

f(8) = (5 + 7) MOD 8 = 4

f(9) = (4 + 7) MOD 9 = 2

f(10) = (2 + 7) MOD 10 = 9

f(11) = (9 + 7) MOD 11 = 5

f(12) = (5 + 7) MOD 12 = 12

f(13) = (12 + 7) MOD 13 = 6

f(14) = (6 + 7) MOD 14 = 13

f(15) = (13 + 7) MOD 15 = 5

f(16) = (5 + 7) MOD 16 = 12

f(17) = (12 + 7) MOD 17 = 2

f(18) = (2 + 7) MOD 18 = 9

f(19) = (9 + 7) MOD 19 = 16

f(20) = (16 + 7) MOD 20 = 3

f(21) = (3 + 7) MOD 21 = 10

f(22) = (10 + 7) MOD 22 = 17

f(23) = (17 + 7) MOD 23 = 1

f(24) = (1 + 7) MOD 24 = 8

f(25) = (8 + 7) MOD 25 = 15

所有跟帖: 

很好,...,加一說明更好: m mod m=m. ... -jinjing- 給 jinjing 發送悄悄話 (0 bytes) () 07/11/2012 postreply 20:07:00

請您先登陸,再發跟帖!