通常我不會來這推薦ProjectEuler的題目 不過這題實在太有趣，我覺得可以介紹給大家 如同很多題目一樣，厲害的不是解出來的人，而且出題者別具匠心的巧思可以想出這種題目。 題目的連結: https://projecteuler.net/problem=855 英文出題 以下是翻譯：(不是逐字翻，大概翻一下就好，如果覺得我翻得不好可以看原文) Alex跟Bianca在玩一個遊戲，這個遊戲先給2個正整數a,b，則遊戲的回合數為a*b回合。 遊戲開始時有一個邊長為1的正方形紙張，每一回合Alex將紙張水平切了a-1刀，垂直切了b-1刀，將紙張分割成a*b個小矩形，切割的線不必均勻分布，任兩刀可以重合，也可以和紙張的邊緣重合(注：也就是說可以有矩形面積為0)，這些小矩形從上到下，由左至右編號為1,2,3,...,a*b。 接下來Bianca從這些小矩形中選一個出來作為下一回合使用，但是Bianca不可以選之前回合已經選過的號碼。 Bianca想要最小化最後紙張的面積，而Alex想要最大化該面積。 令S(a,b)為最後紙張的面積，假定兩人都用最佳策略在進行該遊戲。 例如，S(2,2)=1/36，S(2,3)=1/1800 ≒ 5.5555555556e-4 試求S(5,8)，將你的答案以科學記號進位到小數點後10位數，以小寫英文字母e分隔首數與尾數。 --------------------------------分隔線------------------------------ 以下是解題的心路歷程，但不會有解答，因為PE的主辦方不太希望我們在外透露解法： 如同大部份的PE題目一樣，一開始狀態非常混沌，完全不知道從哪下手？ 只知道好像是這樣，每一回合Bianca選個一個號碼以後，下一次Alex的分割的方法就會不一樣。不同的號碼，就會有不同的分割法。 以S(2,2)來說，如果每一回合Alex都將紙張分割成4個同樣大小的正方形，那麼最後紙張的大小會是(1/4)^4 = 1/256，而不是題目提示的最大值1/36。 順手紙筆算了一下，好像可以得到S(2,2) = 1/36，但是離S(5,8)還有一大段距離。 只好等待A-ha時刻的來到，不是唱Take on me的那個A-ha樂團 而是當你忽然想到關鍵的解法時，會驚呼一聲「A-ha，原來是這樣！」的那個A-ha時刻。 https://www.youtube.com/watch?v=xqTBlft8gQA 然後就沉沉睡去，還好這次我的A-ha moment沒有太晚來到，在睡夢中忽然想到會不會是指那個？ 趕快起床用紙筆算了一下，玩了幾盤，果然是那個！沒有太多時間證明，趕快把程式寫一寫，把答案上傳上去。完全正確，第37位！ 後來在傳完答案後的幾小時內，我給出了證明，並完全瞭解為何這樣是最大值？ 通常ProjectEuler需要跑程式，但這題只需要按計算機，當然是指Windows上那種工程計算機，這算是一個提示吧！ 對了，再次提醒，PE主辦方不太希望有玩家在外透露答案，請勿在此寫出答案。 如果你有自信你的答案是對的，請在ProjectEuler註冊帳號 https://projecteuler.net/ 登入後輸入答案，你的帳號將出現在fastest table上，把自己的id印在fastest table上是很酷的一件事。但只有前100位正解者會列在fastest table上，超過100位解出來者，就榜上無名了，這題目前只有61位解出來。 以上 -- 王菲 成英姝 吳明益 張雨生 崔健 陳珊妮 南西‧威爾森(Nancy Wilson) 紅心合唱團 譚維維 希莉娜依 高圓圓 Deborah Harry 金髮美女合唱團(Blondie) 楊乃文 中森明菜 小紅莓(The Cranberries) 數學 ProjectEuler 解題網站 80年代西洋音樂 小泉今日子 In the fall we sleep all day https://projecteuler.net/recent 歐拉編程競賽 https://projecteuler.net/problem=855 最新一題是個困難題 --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 58.115.129.34 (臺灣) ※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1695307660.A.5A9.html ※ 編輯: utomaya (58.115.129.34 臺灣), 09/22/2023 00:34:26