第一夜 · 一枚假币灯亮了。第一夜不讲王子也不讲公主。讲一枚假币——和一句我背了十二年的答案。2014 年我上高中。一堂数学课讲方程的近似解老师引入的方式很特别一堆金币里混了一枚假的比真币略轻。手里有一架没有砝码的天平问最少称几次能把假币找出来教室里吵了一阵答案慢慢统一对半分。一半上一边天平一斜假币就在轻的那边轻的那边再对半分。一百枚七次。老师说对。这叫二分法它是最优的。我把这句话抄在本子上抄得工工整整。这一抄就是十二年。许多年后一间大学的阶梯教室一位客座教授来讲计算思维。他把同一道题摆到同一群年轻人面前。教室里的答案和当年的我一模一样对半分称轻的继续二分法最快。教授不置可否。他只问了一句谁规定所有金币都必须上秤教室安静了下来。天平是会说话的。只有两枚金币的时候它有两种回答左边轻右边轻。可金币一多它就多出了一种回答平衡——两边一样重说明假币根本没上秤。当年那道题里这种回答从没出现过因为老师把全部上秤写进了规矩。规矩里没有平衡天平就只剩两个词。教授说允许一堆金币不上秤。把一百枚分成三份三十三、三十三、三十四两份上秤若平假币在看热闹的三十四枚里若斜假币在轻的那三十三枚里。无论天平怎么回答嫌疑都只剩下三分之一。三十三枚再分三份。一百枚金币五次稳稳找出来。图 1-1 三分找假币的流程。每一次称量嫌疑都切成三份平了假币在看热闹的那堆里斜了在轻的那堆里。五次称量后一百枚里只剩一枚。作为对比老规矩“全部上秤、对半分”要称七次——省下的两次就是“留一堆看热闹”换来的。七次和五次差的不是聪明是一条规矩。二分没有错——在那条全部上秤的规矩里它就是最优数学可以证明。可规矩一旦改写最优就换了主人。那年教室里的我以为最优是题目发的奖牌天生挂在某一种解法的脖子上。十二年后的我才懂最优从来不属于题目它属于题目和规矩的婚姻。规矩改一条最优就改嫁一次。后来我写代码谋生无数次遇见这架天平。程序里的每一次比较都是一次称量。只是代码里的天平是个哑巴它只会说两个词小于大于等于。所以在代码的世界里二分查找称王谁也夺不走它的冠冕——不是它天赋异禀是那架天平天生只会两个词。直到有一天你在 Java 里遇见一位老朋友compareTo。它每次称量返回的恰恰是三种结果小了一样大了。三结果的天平早就住进了每一行代码里只是很少有人想起它还有一种回答没有用上。故事讲到这里其实漏了一位主角。那堂 2014 年的数学课讲的从来不是假币——假币是它借来的比喻。那堂课的真身是解方程求 f(x) 0 的近似解。二分法在方程的世界里也是老姿势掐头去尾每次砍一半。只是它有个毛病只问正负从不问高低。函数在每个点上站得多高、跌得多深它看也不看全部扔掉。被扔掉的东西里藏着速度。把已经算过的点连成一条曲线直接跳到这条曲线穿过零线的地方这叫插值。两点连一条直线是试位法每走一步就扔掉更老的那个点、只留最新两个是割线法三点连一条弯的用的是拉格朗日插值。它们都瞧不起二分你称三十次才攒下的那点信息我们几步就用尽了。图 1-2 插值为什么快。同一段区间 [2, 3]二分只问正负第一步走到中点 2.5割线把两个起点 (2, −1) 与 (3, 16) 连成直线第一步就落在 2.059——离根 2.0946只剩半步的路。虚线就是这条割线它穿过零线的位置 2.059就是插值交出的第一个答案。牛顿的名字在这里物归原主。1669 年他在手稿里演示自己的方法挑的方程是 x³ − 2x − 5 0——根在 2 和 3 之间。三百年后全世界的教科书还在用这一条方程考一代又一代的学生。当年把牛顿错写在二分法旁边的少年直到写这一夜才把名字还了回去。同一条方程照出了三种人生。守规矩的笨人用二分走了三十步永不失手也从不加速。念旧的人用试位法聪明地把两点连成线却死死抱着右端点不撒手——走了一百万步还在半路上。放手的人用割线法同样两点插值只是每一步都更新全部的已知六步到家。原来插值也不是万能药。同一个方法抱着旧点不放的人比笨人还慢。这一夜的规矩又多了一条信息要用旧的点要舍得扔。写给孩子的话就放在这里做题的时候先别急着抓最聪明的解法。放下笔看一眼题目里有没有一条没人念出来的规矩。很多你以为的天花板只是某条规矩的房檐你挪开它头上就是另一片天。也看一眼你手里的信息——每一次算出来的高低深浅都是别人随手扔掉的东西抱着旧结果不撒手的人跑不过肯更新的人。最优从来不在题目里它在规矩里。规矩改一条最优就改嫁一次而每一次改嫁都要你交出一样旧东西——上一次是全部上秤的迷信这一次是那个抱了太久的端点。这一夜的三架天平我都写成了能跑的程序附在下面的三面镜子里。你要是不信次数会变、路程会短自己跑一遍数一数。镜子一 · 全部上秤二分的天平importjava.util.*;/** * 《算法一千零一夜》第一夜 · 找假币二分的天平 * 改编自作者的高中课堂。一堆金币里混着一枚略轻的假币 * 店规是所有金币必须上秤——天平只会说两个词左边轻右边轻。 * 老师的策略是贪心式的干脆对半分轻的那边继续永不回头。 */publicclassFakeCoinBisect{publicstaticvoidmain(String[]args){intn100;// 一百枚金币其中一枚略轻。inttimes0;while(n1){times;intleftn/2,rightn-left;// 全部上秤一边一半。System.out.println(第 times 次称量左盘 left 枚右盘 right 枚全部上秤。);System.out.println(天平倾斜了——嫌疑只剩下 Math.max(left,right) 枚。);nMath.max(left,right);}System.out.println(二分的天平称了 times 次。假币无处可逃规矩毫发无损。);}}镜子二 · 留一堆不上秤三分的天平importjava.util.*;/** * 《算法一千零一夜》第一夜 · 找假币三分的天平 * 同样的金币同样的天平。改变的只有一条规矩 * 允许留一堆金币不上秤——于是天平多学会了一个词平。 * 她的策略三等分称其中两堆平了看热闹的那堆斜了听轻的那堆。 */publicclassFakeCoinTrisect{publicstaticvoidmain(String[]args){intn100;// 一百枚金币其中一枚略轻。inttimes0;while(n1){times;inta(n2)/3;// 上秤的两堆每堆这么多。intcn-2*a;// 留在旁边看热闹的那一堆。if(c0){System.out.println(第 times 次称量两堆各 a 枚上秤c 枚在旁边看热闹。);}else{System.out.println(第 times 次称量两堆各 a 枚上秤。);}System.out.println(不管天平怎么答——平了听看热闹的斜了听轻的那堆——嫌疑只剩下 Math.max(a,c) 枚。);nMath.max(a,c);}System.out.println(三分的天平只称了 times 次。金币一枚没少规矩换了一条。);}}镜子三 · 同一条方程的三种人生importjava.util.*;/** * 《算法一千零一夜》第一夜 · 同一条方程的三种人生镜子三 * 方程x³ − 2x − 5 0。牛顿在他 1669 年的手稿里用的正是这一条。 * 根在 2 与 3 之间f(2) −1f(3) 16。 * * 三种人三种求根的活法 * 一、守规矩的笨人二分只问正负永不失手每次把区间砍一半。 * 二、念旧的人试位用两点连线的插值找根聪明——但右端点抱着不放手。 * 三、放手的人割线同样两点插值每一步都更新全部已知超线性收敛。 */publicclassNewtonNight{staticdoublef(doublex){returnx*x*x-2*x-5;}staticfinaldoubleEPS1e-9;// 精度要求区间窄过十亿分之一。publicstaticvoidmain(String[]args){System.out.println(方程x^3 - 2x - 5 0牛顿 1669 年手稿里那条。根在 2 与 3 之间。);System.out.println(精度要求区间窄于 0.000000001。);System.out.println();// 一、守规矩的笨人二分。只问正负每次砍一半。doublea2,b3;intsteps0;while(b-aEPS){doublem(ab)/2;if(f(a)*f(m)0)bm;elseam;steps;}System.out.println(一、守规矩的笨人二分走了 steps 步根 ≈ (ab)/2);System.out.println( 永不失手也从不加速——每一步都只知道一半。\n);// 二、念旧的人试位法。两点连线找根但右端点 3 永远不更新。a2;b3;steps0;while(b-aEPS){doublec(a*f(b)-b*f(a))/(f(b)-f(a));// 两点的插值零点if(f(a)*f(c)0)bc;elseac;steps;if(steps100000)break;// 念旧的人可能要走很久很久}System.out.println(二、念旧的人试位法端点抱着不撒手走了 steps 步区间还剩 String.format(java.util.Locale.ROOT,%.6f,b-a));System.out.println( 聪明却把旧消息攥出了褶子。\n);// 三、放手的人割线法。同样两点插值但每一步都更新全部已知。doublex02,x13;steps0;while(Math.abs(f(x1))EPSsteps100){doublex2x1-f(x1)*(x1-x0)/(f(x1)-f(x0));x0x1;x1x2;steps;}System.out.println(三、放手的人割线法两点插值步步更新走了 steps 步根 ≈ x1);System.out.println( 同样的插值同样的两点——它只是舍得搬家。);}}改编来源称金币问题是流传已久的经典智力题“允许不上秤则三分优于二分的解法与解释为真2014 年的课堂与客座教授的插曲是作者亲历。方程段史实牛顿在 1669 年写成的手稿后于 1711 年发表中以 x³ − 2x − 5 0 演示其方法根约 2.09455148试位法与割线法的历史源流、插值法的现代表述见数值分析标准教材。另照实标注作者自己的错名当年笔记里的牛顿二分法”名字是记串的——教材里它叫二分法牛顿法是另一种用切线逼近的解法。错误也是故事的一部分照单全收。一条真核也照实入账这条方程在 [2, 3] 上是凸的试位法的弦交点永远落在真根左侧于是右端点 3 钉死不动、左端点独自爬行。念旧的人走满一百万步仍在半路是数学的必然不是程序写错程序实跑为证。今夜习题八十一枚金币混着一枚略轻的假币。用允许留一堆不上秤的称法最少几次保证找出提示3 的几次方恰好是 81你算出来几次评论区见。答案与参考程序收在书后《参考解答》。版权声明本文为作者原创受著作权法保护。未经授权禁止转载、搬运、摘编、改编及任何形式的二次创作个人学习引用请注明作者与原文出处。转载授权请联系作者CSDN 私信。侵权必究。