遞 迴 問 題 的 應 用

Question

一位數學家在蠻荒探險，在部落做客，卻遇到外族強力來犯，酋長帶著族人和數學家總共 ３1 人，一同被圍困在一個山洞內，正面臨著無可避免的失敗 ，他們下定決心， 不成功便成仁 ，寧死不降 。於是他們決定安排自己在一圓圈上， 其中酋長被指為 1 號， 然後開始進行他們的決定 ，方法是順時針方向由 1 號算起， 每二人按順序自殺， 直到所有人都死光為止 ，2，4，...， 28, 30 相繼自殺。接下來應該是輪到 1 號 ,再接下來的並不是 3 號， 因為 2號和 4號剛才己經自殺身亡了， 所以下一個是跳過 3 號的 5 號 ，依此類推。數學家不想平白死掉，但是又怕族人笑他懦弱，因此，他立即算出自己應該站在那一位置才是最後輪到的。
請問，數學家是站在哪一個位置

可以教我算這個嗎 這是網路上的一個題目 它的算法我看不懂 聽說是遞迴的應用

那如果他問第25個死掉的是幾號呢

沒關西
你也盡力幫助我了

Answer 1

遞迴確實是解決這個問題的好辦法，答案有些恐佈，事實上，數學家會站在這個位置：

2(n-2^k)+1

其中的 k 差不多是 log_{2}n，如果這個數字不是整數，就取比它小的最大整數

（因此，2^k 也差不多就是 n ， n-2^k 也差不多就是 0 ，當 n 是 2 的次方時，第 1 位是最有利的位置；當 n 不是 2 的次方時，2(n-2^k)
因此，

如果有 31 個人，數學家會站在第 2(31-16)+1=31 個位置
如果有 25 個人，數學家會站在第 2(25-16)+1=19 個位置

詳細的論證請參考台大數學系張鎮華教授的文章：

普通高中數學課程中"遞迴關係"移轉位置之背景及我見
http://www.ck.tp.edu.tw/xoops/custom/resource/article9502_1.pdf

Answer 2

vbboyy你好

2006-04-26 17:54:57 補充：
我有問題可以請教你嗎

2006-05-02 18:35:30 補充：
可是我的問題無法寄給你ㄟ
要怎樣才可以問到你呢

2006-05-03 20:09:11 補充：
那你要來常看我的問題喔
謝謝你

2006-05-03 20:09:17 補充：
那你要來常看我的問題喔
謝謝你

Answer 3

我想出來的方法不是遞迴
不過我也想不出用遞迴的方式解決

第一輪之後留下來的人為: 2k - 1
第二輪之後留下來的人為: 4k - 1
第三輪之後留下來的人為: 8k - 1
第四輪之後留下來的人為: 16k - 1
第五輪之後留下來的人為: 32k - 1

可以看出來第五輪是最後一輪,
因為 32k - 1 只能等於31( 下一個是63,並沒有這麼多人)

所以, 31號是最後的生還者

2006-04-23 23:44:12 補充：
那如果他問第25個死掉的是幾號呢?
超出我的範圍, 不好意思, 我也想幫你
不過我找不出公式

2006-05-01 20:17:27 補充：
LBJ你好
有什麼問題請說
我如果會的話就會回答

2006-05-02 19:48:38 補充：
如果打的下就在這裡問囉

Answer 4

用推理的方式
第一輪：所有偶數號死亡(差2)
第二輪：1.5.9.13.17.21.25.29死亡(差4)
第三輪：3.11.19.27死亡(差8)
第四輪：7.23死亡(差16)
第五輪：15死亡
最後僅剩 31

2006-04-27 00:51:27 補充：
第一輪死15個，第2輪死8個，所以第25位死亡一定是第三輪的第2位，也就是NO.11