我喜歡捉猶

發布時間: March 25, 2020, 11:18 p.m.   最後更新時間: Sept. 15, 2023, 9:52 a.m.   時間限制: 1000ms   記憶體限制: 128M

於第一世紀時,猶太人受制於羅馬帝國,一批愛國志士反叛羅馬帝國,最後僅剩下41人受困於山洞。這41人不想受辱於羅馬帝國,又不想自殺,因此決定圍成一個圓圈,由1號開始將2號殺掉;3號將4號殺掉,依此類推,即由前一個殺掉下一個,欲將全團41人全部殉戰而亡。然而,最後必定會剩下一人。試問哪一號最後得以苟且偷生?如果有n個人圍成一圓圈,誰得以殘留餘命呢?

令f(n)為最後留下性命的號數,則f(1)=1。設有2n個人,則過了第一圈後所有偶數號的都要被去除,剩下的人為成一圈如下:

1,3,5,...,2i-1,...,2n-3,2n-1 (接1)

將其重新編號,則編號為1至n為成一圈與上述所剩下的人其號碼的對應方式為i=>2i-1。

1,2,3,...,i,...,n-1,n

一個正整數N(1<=N<=50)

輸出f(n)之值

複製範例
41
19

math 模擬

CSDC35TH 第3次社內競賽