作者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