※ 引述《balista (old man)》之銘言：
: ※ 引述《giveme5 (給我5塊~)》之銘言：
: : 想請幫忙解一下
: : 4 10 13 15 16 17
: : 感謝各位
: no. 17
: 今 f(n) 為 n 的解, 則
: f(1) = 1
: f(2n) = 2 * f(n) - 1
: f(2n+1) = 2 * f(n) + 1
: 將 n 用 2011 代入即可.
: (此為 Josephus problem, 參看 Knuth 的 Concrete Mathematics)
Knuth的書是自己所上的所長翻譯的，想說把細節再寫清楚一點。
法一
if
f(n) 為 n 的解,find n,n=(2^k)-1 k屬於N
so,f(1),f(3),f(7)...滿足f(n)=n
we let n=2^10-1=1023 f(1023)=1023
則f(2011)=2(2011-1023)-1=1975
其中, 將n1 n2 n3 n4 .......nx nx+1 皆滿足 n=f(n) 作排列
if當 nx <nx+p< nx+1 ,f(nx+p)=2(nx+p-nx)-1=2p-1 end
法二
演算法 (2011) =(11111011011) 左邊第1位尻掉 末位補1 =(11110110111)
10 2 2
=(1975)10
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.112.194.192
※ 編輯: fong1014 來自: 59.112.194.192 (03/18 23:27)