通常我不会来这推荐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/cn.aspx?n=bbs/Math/M.1695307660.A.5A9.html ※ 编辑: utomaya (58.115.129.34 台湾), 09/22/2023 00:34:26