※ 引述《ping1902 (我已经老了)》之铭言： : 应该是说 教授跳楼会死的楼数 在2~100中 (我不知道楼层顶算不算 算的话一楼也要考虑) : 要想出一个方法 顶多只死两个教授就知道哪个楼层是最小致死楼层 : 而且还要证明你这方法中用的跳楼次数的可能最多次数 : 是所有能找出最小致死楼层的方法中的最多次数里面最少的 : 最後 你这方法中所用的可能最多次数 就是答案啦 以下的「答案」一词指的是「最小致死楼层」 由ACGfans版友的想法来想 我们可以知道 第二个教授一定得要一层一层往上试 那麽如果第一个教授试的层数是 1<x1<x2<x3<...<x_n=100 那麽(部份答案的)总次数是 (令x0=1) 答案 2=x0+1 x1+1 x2+1 x3+1 ... x_(n-1) x_n=100 次数 2 3 4 5 n+1 ---- x0~x_(n-1)都是第一个教授试到它的下一个楼层而摔死 第二个教授往上试一层也挂了 所以(x_k)+1需要k+2次 在x_k之间的楼层所需次数则是 (若x_(k+1)>ans>x_k) ans-x_k+(k+1) (第二个教授一层一层跳 跳到死为止) 但是答案是x_k的次数却可以少一次 因为少跳一次x_k层 由他在(x_k)-1层的生还而确定答案是x_k 因此我们只要找到对所有k=0..n-1, 使(x_(k+1))-1-x_k+(k+1)=(x_(k+1))-x_k+k的最大值最小 由1+2+...+13=91<100 知 k>13 (还不够k增加) 若k=14, 则所有k个(x_(k+1))-x_k+k的总合=x_n-x_0+(1+2+...+13) =100-1+(91)=190 190/14=13.5xx => 个别的最大总合取14最小 而总合14平均分摊的情形是: (不平均分摊的话只会剩更多总合下来) x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 1 15 28 40 51 61 70 78 85 91 96 100 --- --- --- 总合13的情形, 易知排不满100层: x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 1 14 26 37 47 56 64 71 77 82 86 89 91 92 ... 若k=15, 所有总合=100-1+105=205, 205/15=13.6xx => 个别的最大总合也≧14 不能更好 k=更大的数(K)时, 所有总合=99+(K(K-1))/2, 平均=99/K+(K-1)/2≧2√(99/2)-1/2=13.57xx => 个别的最大总合还是≧14 一样不能更好 而我们已经有了一个最大总合14的例子了 故知答案为14次 -- 上面这组答案(15,28,40,51,61,70,78,85,91,96,100) 和ACGfans版友求得的(14,27,39,50,60,69,77,84,90,95,99)只差一层楼 这是由於我的答案范围是由2开始 (也就是如果答案在低楼层 若15楼就摔死教授1则教授2是由2楼起跳) 如果由1开始的话就会得到ACGfans的答案 不过一样都是14次 -- 有错或不完整的请指教 谢谢 -- "LPH" is for "Let Program Heal us".... --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 192.192.197.112