作者changkh (留學生涯)
看板ck47th320
標題Re: [問題] 又一個演算法的問題
時間Thu Mar 24 05:55:34 2005
※ 引述《genie2 (新挑戰)》之銘言:
: 雖然有點看不懂有關你證明的部分
: 但是我突然想說,這題挖井的位置是"實數"嗎?
: 如果是的話,那數線上任何interval不是都可以有無限個實數?
: 這樣就可以得證了
: 還是我想得太簡單了,有錯請大家指正
位置是實數沒錯,不過麻煩的地方在於要如何確定目前挖的井的位置不
會和未來某個區間衝突。
我的證明是一種比較特別的數學歸納法。本來數學歸納法是假設n成立,
推到n+1。但是在這題裡,假設挖了n個井,想推到一個可以滿足所有情況
的n+1不是那麼容易。所以我的方法是證明2^n到2^(n+1)成立,然後從
n證到n-1。我的想法是一個一個拿掉然後證明每次拿掉後都合乎n-1
似乎會比較容易。不過從n證到n-1的部份也發生了困難。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 68.43.196.35