企业官网建设流程全解析

第六夜 · 蜗牛的井与弹跳的板

灯又亮了。第六夜。这一夜讲两个慢性子，一只蜗牛，一颗小球。它们这一生只做一件事，朝着出口，一步一步挪。你马上会看见，能把这种事做好的，天底下只有一种机器，和一个肯陪它们慢下来的人。

先说蜗牛。一口井，深 h 尺。蜗牛住在井底，白天往上爬三尺，夜里睡着了，往下滑一尺。要问的是，第几天爬出井口。题面末尾还藏着半句话，爬到井口那一下，是在白天。这半句先搁着，后面有它的用场。

听见这道题，聪明人立即摆出巧算法。白天三尺，夜里一尺，一天净进两尺，井深十尺，十除以二，五天。拿十尺的井一对，答案五天，灵了。巧算法袖子一甩，五尺的井也答三天。蜗牛笑了。第一天白天它爬了三尺，天还没黑，它已经扒着井口了，夜里那一下滑，轮不到它。两天，到家。公式没有算错加法，它忘了问一句，出口在白天。九尺的井也一样栽，公式答五天，蜗牛四天就到家了。

公式这条路没有断，断的只是那条巧算法的运气。再往下剥一层。蜗牛只在最后一天白天出井，出井之前，每一天都是完整的白天加黑夜，净进两尺。那就把最后那三尺先从井里扣掉，留给白天，剩下的路交给两尺一天，数完再补上最后这一天。列成等式，设天数是 $d$。出口在白天，是说第 $d$ 天的白天从 $2(d-1)$ 尺起步，再爬三尺必须够着井口，$2(d-1)+3\ge h$，解出来 $d\ge\dfrac{h-1}{2}$，天数取最小的整数。

$$d=\begin{cases}1, & h\le 3\\[6pt] \left\lceil\dfrac{h-1}{2}\right\rceil, & h\gt 3\end{cases}$$

这跟先扣三尺的数法算出来是同一个数。巧算法那句话也有式子，$d=\left\lceil h/2\right\rceil$，写得更快，错得也更快。五口井逐口验过去，十尺，四天加一天；九尺，四天；五尺，两天；两尺、一尺，各一天。全对。两条公式并排一摆，差的就是题面末尾那半句。巧算法不分白天黑夜；对的那条先把三尺扣给白天，等于把出口在白天算进了式子里。

图 6-1 十尺井，五天。实线是白天的三尺，虚线是夜里的一尺，白天扒住的位置白底，夜里滑到的位置灰底。第五天从八尺起步，爬三尺，井口就到了，夜里那一下省了。右联的五尺井是巧算法的伤心处，公式答三天，蜗牛两天到家。

机器不背公式。它陪蜗牛过日子。天亮，爬三尺，问一句，到了吗。没到，天黑，滑一尺。井底到井口有多远，它就陪多远。五口井跑下来，十尺五天，九尺四天，五尺两天，两尺一天，一尺也是一天。三份答案摆在一起，巧算法错两处，正公式五题全对，陪爬的机器也五题全对。巧算法错的那两处，错因是同一句，出口在白天。正公式把这句写进了式子里，机器把这句留在了脚步里。

蜗牛的出口是一道井沿，小球的出口是一排板的尽头。五块弹簧板一字排开，从左到右编号，第 i 块板会把落下来的小球向前弹 a[i] 个距离。小球落在一号板上，这一下算第一次弹跳，往后每落到一块板上，再算一弹，落出板外的那一下不算。要问的是，弹跳几次才能出界。这一夜的样例，五块板，弹跳距离一、二、三、一、二。

落在一号板，第一次弹，弹跳距离一，落到二号板，第二次弹。二号板弹跳距离二，一跳两格，落到四号板，第三次弹。四号板弹跳距离一，落到五号板，第四次弹。五号板弹跳距离二，两步出去，出界，这一下不算。答案，四次弹跳。慢着，三号板呢。三号板弹跳距离三，听着最有力气，可小球从二号板一跳就是四号，三号板从头到尾没被踩到。球只走自己的路，别人的板再近，与它无关。

图 6-2 五块板，四次弹跳出界。弧线是球的去路，一号板落球算第一次弹跳，二号、四号、五号各算一弹，出界那一下不算。第三块板用虚线描着，弹跳距离三，力气最大，却一次也没有被踩到。

这一夜我翻出一件自己的旧物。当年第一次写弹簧板，我用的是递归，弹一次，函数喊一次自己，弹跳的次数挂在参数上，出了界再一层一层退回来。尾巴上那一下，恰好是纯粹的尾递归。写的时候只觉得顺手，跑小样也漂亮，五块板，答四次弹跳。直到有一天把板数加上十个零，程序摔死了。每一次弹跳压一层栈，弹十万次，压十万层，栈碎了。这正是第四夜那句话的下文。递归改成循环，要么尾递归，要么带本子。弹簧板恰好是带本子都不要的那一种，两个变量，一个 while，尾巴一剪，栈就空了。我还做了个对照，同一份代码，同一份十万块板的输入，普通编译，摔死，一个字都没来得及吐；换一个编译器再编，编译器自己把尾巴剪了，十万层安然跑完，答案十万。第四夜说机器不替你剪尾巴，那句话对一半。Java 的机器不替你剪，C 的编译器肯替你剪，前提是你肯把尾巴写成尾巴。这条尾递归写成数学分段函数式，只有两行。记号先交代清楚，$n$ 是板子的总数，$p$ 是小球脚下这块板的编号，$a_p$ 是第 $p$ 块板上写着的弹跳距离，$f(p)$ 是从这块板弹到出界还要弹的次数。

$$f(p)=\begin{cases}0, & p\gt n\\[6pt] f\big(p+a_p\big)+1, & 1\le p\le n\end{cases}$$

这两个式子直接念确实拗口，用样例一站一站问过去就明白了。问法只有一句，从你这块板出发，到出界还要弹几下。

先问五号板。五号板弹跳距离二，一跳就把球送出界了，出界那一下不算数，所以出界报零，五号板加上自己脚下这一弹，报一次弹跳。再问四号板。四号板把球送给五号板，五号板报一次弹跳，加上自己脚下这一弹，四号板报两次弹跳。轮到二号板。它把球送给四号板，四号要两次弹跳，加上自己这一次弹跳，三次弹跳。最后问一号板。它把球送给二号板，二号要三弹，加上自己这一次弹跳，四次弹跳。答案，四次弹跳。

式子里的 $f(p)$，就是第 $p$ 块板报出来的数。$f\big(p+a_p\big)$，是下一站报上来的数。加的那个一，是脚下这一次弹。第二段程序没有倒着问，它陪小球正着走，走一步数一步，数出来也是这四次弹跳。两条路，一个答案。

有一个说法要点明。这个式子是逆推式，不是顺推式。每一次的弹跳次数，取决于后一次的弹跳次数，所以要倒着问，先问离出界最近的五号板，一路问回一号板。顺着一号到五号正着问，问不动，一号板在等二号板的答案，二号板在等四号板，四号板在等五号板，五号板在等出界。出界报了零，问话才开始。

那有没有通项公式，一条式子把弹跳次数一口算出来，不用一站一站问。通例没有。弹跳距离各说各话，答案是整串弹跳距离一起写出来的，谁也代替不了谁，通项写不出来，只能一站一站问。特例倒是有，假如每块板的弹跳距离都是一，从一号板出发要弹跳 $n$ 次，从第 $p$ 块板出发要弹跳 $n-p+1$ 次，一条式子就够。特例能写通项，通例只能递推，这条分界往后还会一次一次遇见。

两版程序还都默认了一件没说出口的事。弹跳距离向前进，板子总有尽头，球总有出去的一天。可要是哪一块板的弹跳距离是零（$a_i=0$）呢。小球原地弹，弹到天荒地老，while 不会喊停，它没有腿，喊停的事得写程序的人来。我给这版程序加了个守卫，弹十万次还在二号板上，就停下来说实话。写这种一步一步走的程序，先问三句，候选列得出来吗，验证写得出来吗，停得下来吗。第三问最不显眼，也最要命。

写这一夜之前，我去查过这只蜗牛的户口，查完又好气又好笑。蜗牛爬井是有户口的，一千二百年前就上了书。公元 800 年前后，英格兰有个学者叫阿尔昆，在查理曼的宫廷里教书，编了一本拉丁算题集，磨砺年轻人的命题，蜗牛掉坑里日爬夜滑这件事就收在里面，规则与今夜完全相同。数字各版本有出入，流传较广的一版是六十尺的坑，白天爬七尺，夜里滑两尺。有趣的是阿尔昆自己给的答案，用的是除法硬算，天数给大了。按出口在白天的规则，蜗牛第十二天白天从五十五尺一步越过坑沿，就出去了。出这道题的人，自己先掉进了巧算法。题集的名字，直译过来就是磨砺年轻人，磨刀石的磨。阿尔昆在查理曼的宫廷里教书，教的是年轻的教士和贵族子弟，这本书的用途，他起名的时候就交代了，题目是磨刀石，年轻的心智是刀。书里躺着无解题，也躺着逗乐的谜语，真要教人算术，这些题早该删了。留着，就为磨。后来这道题漂洋过海，欧洲民间传来传去，传到中文世界，主角换成了青蛙，蹲进了公务员考试的题库，行测的数量关系管它叫陷阱题，通行答法的第一步与正公式一字不差，先扣掉最后一跳。

所以你看，这些奥数题的教练们都在干嘛。没事就考我们，把我们考得焦头烂额。我绞尽脑汁，也想不出该用什么来形容小学奥数。偏题，怪题，技巧性的题，稀奇古怪的所谓趣味题，大学里面从来不考。别跟我说建立数理思维。这些题，连清华北大的教授也得弯弯腰。那教研员为什么喜欢出这种题？答案只有一个。做选拔性考试的筛选尺度。这种题不是知识，是筛子。筛子的眼儿有多密不要紧，要紧的是把人分成过线的和没过线的。同一道题，阿尔昆叫它磨刀石，教研员把它用成了筛子。

所以这一本书出这道题，是为了讲故事，不是为了筛选人才。这也是这本书的写作初衷，用童话把偏题怪题拆成故事，一页一页地讲。当乐子，不当考查，把恐惧一点一点消掉。当数学题离开课本，走进算法的乐园，突然一切变得有趣起来。变的不是题，是讲故事的人。教研员用考试讲故事，讲出来的故事枯燥无味；这一本书用算法讲故事，在机器一次又一次的欢唱里奏出乐章。乐章是什么，就是规律。正公式是怎么推出来的？不是天上掉下来的，是陪着蜗牛爬完五口井，回头看脚印看出来的。机器把脚印一行一行打印出来，那就是它的欢唱。

有一句话，我想压在这一夜的井沿上。知道自己走到哪一步该停下，比走得快要紧。

这一夜的三段程序我都留了下来。第一段陪蜗牛爬井，十尺井一天一天摆给你看。第二段陪小球弹板，连弹跳距离为零的那块板也替你试了一回。第三段是当年的尾递归化石，原样照登，一字没改，连注释里几个早已变成问号的字一起。你要是不信公式会忘出口、尾巴剪了栈就不碎，自己跑一跑，数一数。

第一段 · 蜗牛爬井

import java.io.PrintStream; /** * 《算法一千零一夜》第六夜 · 蜗牛爬井 * 井深 h 尺，白天往上爬三尺，夜里往下滑一尺，爬到井口那一下是在白天。 * 不背公式，陪蜗牛一天一天爬：天亮先问一句到没到，没到才轮到夜里滑。 * 两条公式陪跑对照。巧算法一天净进两尺，五尺井答三天，错了； * 正公式先把最后三尺扣给白天，剩下的除以二向上取整再补一天，五口井全对。 */ public class SnailWell { // 返回爬出井要的天数：天亮爬三尺，先到先算；没到，夜里滑一尺。 static int days(int h) { int pos = 0, day = 0; while (true) { day++; pos += 3; // 白天，往上爬三尺。 if (pos >= h) { return day; // 爬到井口，这一下是在白天。 } pos -= 1; // 夜里，往下滑一尺。 } } // 巧算法：一天净进两尺，不分白天黑夜。 static int naive(int h) { return (h + 1) / 2; } // 正公式：最后三尺留给白天，剩下的路一天两尺，向上取整再补最后那一天。 static int rightFormula(int h) { if (h <= 3) { return 1; // 井深不过三尺，头一天白天就到。 } return (h - 2) / 2 + 1; // (h-3)/2 向上取整加一的整数写法。 } // 陪爬一遍，把每天的位置摆出来看。 static void trace(int h) { int pos = 0, day = 0; while (true) { day++; pos += 3; System.out.println(" 第 " + day + " 天白天，爬到 " + Math.min(pos, h) + " 尺。"); if (pos >= h) { return; } pos -= 1; System.out.println(" 第 " + day + " 天夜里，滑到 " + pos + " 尺。"); } } public static void main(String[] args) throws Exception { System.setOut(new PrintStream(System.out, true, "UTF-8")); System.out.println("一、十尺的井，陪爬一遍"); trace(10); System.out.println(); System.out.println("二、五口井的天数（两条公式与蜗牛各答一遍）"); int[] wells = {10, 9, 5, 2, 1}; for (int h : wells) { int d = days(h); String verdict; boolean naiveOk = naive(h) == d, rightOk = rightFormula(h) == d; if (naiveOk && rightOk) { verdict = "两条公式都对。"; } else { verdict = "巧算法答 " + naive(h) + " 天，" + (naiveOk ? "对" : "错了") + "；正公式答 " + rightFormula(h) + " 天，" + (rightOk ? "对" : "也错了") + "。"; } System.out.println(" 井深 " + h + " 尺：蜗牛 " + d + " 天。" + verdict); } } }

第二段 · 弹簧板

import java.io.PrintStream; /** * 《算法一千零一夜》第六夜 · 弹簧板 * n 块弹簧板一字排开，第 i 块把小球向前弹 a[i] 个距离， * 球落在一号板上算第一次弹跳，问弹几次弹出板外。 * 一个变量记位置，一个变量记弹数，一个 while 弹到出界为止。 * 当年的化石是尾递归，弹一次压一层栈；剪掉尾巴，栈就空了。 */ public class SpringBoards { // 返回弹跳出界要的次数：落在板上算一弹，弹出板外的那一下不算。 static int bounces(int[] a) { int n = a.length; int pos = 1, count = 1; // 一号板，这一下算第一次弹跳。 while (pos <= n) { // 还在板上，就还得弹。 pos += a[pos - 1]; // 第 pos 块板把球向前弹 a[pos-1]。 if (pos <= n) { count++; // 落回板上，记一弹。 } } return count; } // 陪弹一遍，把每一次落点摆出来看。 static void trace(int[] a) { int n = a.length; int pos = 1, count = 1; System.out.println(" 落在一号板，第 1 次弹跳。"); while (pos <= n) { int jump = a[pos - 1]; // 这一块板把球向前弹 jump。 pos += jump; if (pos <= n) { count++; System.out.println(" 弹到第 " + pos + " 块板，第 " + count + " 弹。"); } else { System.out.println(" 再弹 " + jump + " 个距离，落到 " + pos + "，出界。"); } } } public static void main(String[] args) throws Exception { System.setOut(new PrintStream(System.out, true, "UTF-8")); System.out.println("一、五块板，弹跳距离 1、2、3、1、2，陪弹一遍"); int[] a = {1, 2, 3, 1, 2}; trace(a); System.out.println(" 一共 " + bounces(a) + " 弹。"); System.out.println(); System.out.println("二、停得下来吗（弹跳距离为零的板）"); int[] stuck = {1, 0, 2}; int pos = 1, count = 1, guard = 0; while (pos <= stuck.length && guard < 100000) { pos += stuck[pos - 1]; if (pos <= stuck.length) { count++; } guard++; } if (guard >= 100000) { System.out.println(" 弹跳距离 1、0、2 的板：十万次循环过去，球还在第 " + pos + " 块板上原地弹。程序停不下来，得写程序的人先问一句，停得下来吗。"); } else { System.out.println(" 弹了 " + count + " 次，出界。"); } } }

第三段 · 当年的尾递归

#include <stdlib.h> #include <stdio.h> #define N 100000 int resolve(int, int * ,int, int); int main() { int n; scanf("%d", &n); int a[N] = {0}; for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } // 1 找到小球的位置 int start = 0; for (int i = 0; i < n; i++) { if (a[i] == 1) { start = i; break; } } int ans = resolve(n,a,1,0); printf("%d",ans); // system("pause"); return 0; } // 有一个小球掉落在一连续的弹簧板上，小球落到某一个弹簧板后，会被弹到某一个地点，直到小球被弹到弹簧板以外的位置。 // 假设有 n 个连续的弹簧板，每个弹簧板占一个单位距离，a[i] 代表代表第 i 个弹簧板会把小球向前弹 a[i] 个距离。比如位置 1 的弹簧能让小球前进 2 个距离到达位置 3 。如果小球落到某个弹簧板后，经过一系?弹跳会被弹出弹簧板，那么小球就能从这个弹簧板弹出来。 // 现在小球掉到?1 号弹簧板上面，那么这个小球会被弹起多少次，才会弹出弹簧板。 1号弹簧板也算一次。 // 5 // 1 2 3 1 2 // 4 int resolve(int n,int *a, int count, int position) { if(position>=n){ return count-1; } // f(n+1)=n+1 // g（p+1）=g(p)+a[p] count=resolve(n, a, count+1,position+=a[position]); return count; }

① 真伪核对逐条照实登记。

Ⅰ 蜗牛爬井 这道题有户口。公元 800 年前后，阿尔昆编的拉丁算题集 Propositiones ad Acuendos Juvenes（磨砺年轻人的命题）收录了蜗牛掉坑、日爬夜滑的题；该集是现存最古老的拉丁趣味数学题集，狼羊菜过河与三夫三妻过河的首例也在其中。题号与数字各版本有出入，流传较广的一版为六十尺的坑、白天爬七尺、夜里滑两尺。阿尔昆本人的答法用除法硬算，天数偏大；按出口在白天的规则，蜗牛第十二天白天从五十五尺越过坑沿即出。通行校注见 Hadley 与 Singmaster 合译 Problems to sharpen the young（The Mathematical Gazette 第 76 卷，1992 年）。中文世界的变体多把主角换成青蛙，蹲进公务员考试行测的数量关系题库，称陷阱题；通行答法第一步先扣掉最后一跳，与本夜正公式同款。另有三十尺井等变体，数字依版本而异，不锁死一种。书名直译即磨砺年轻人（ad acuendos，为了磨砺），学界通行的判断是课堂教具而非算术手册；阿尔昆时任查理曼宫廷学校的教师，后任图尔圣马丁修道院院长。

Ⅱ 弹簧板 算法竞赛与编程教学中的流传题，变体众多，有的版本问每一块板各需几次弹跳，原始出处不可考。第三段照录自作者早年的教学代码，正文与注释一字未改。尸检三笔照实登记。其一，main 里有一段寻找弹跳距离为一的下标的循环，找出的位置从未被使用，是死代码。其二，resolve 的最后一步是调用自己，弹一次压一层栈；实跑样例五块板答四，板数上万之后，一万、两万、五万、十万用普通档位编译全部摔死，进程无输出退出；同一份代码换一个编译档位再编，编译器把尾调用剪成循环，十万块板安然答十万。其三，位置更新写在递归调用的实参里，边传参边改值，能跑，读的人得多看两眼；文件里几处注释的字早已变成问号，老编码留下的疤，照登不修，唯一的手脚是注释里一处词按全书规则改了写法。

Ⅲ 实跑记录 两段 Java 与一份 C 化石均在本机实跑（JDK 21 与 g++）。蜗牛这五口井，十尺五天，九尺四天，五尺两天，两尺一天，一尺一天；巧算法（一天净进两尺）在九尺井答五天，五尺井答三天，与蜗牛各差一天。弹簧板样例五块板四次弹跳出界，与图 6-2 一致；弹跳距离一、零、二的板，守卫十万次的循环转满十万次，球仍在二号板上原地弹。化石 C 在样例上答 4，换档位后十万块板答 100000。

Ⅳ 术语三笔 尾递归，函数的最后一步是调用自己，且此后再无别的计算；C++ 编译器在优化档位下会把尾调用剪成循环，Java 虚拟机至今不做，第四夜的核对表在案，本夜的化石是它的对照组。模拟，跟着过程一步一步走，与枚举是近亲；枚举列候选，模拟走过程，候选往往就是一步一格的脚印。终止性，一段程序停不停这一问的学名；本夜只推门一角，门后连着第二夜的死循环画廊。

Ⅴ 数字与规律 五尺井，巧算法答三天，蜗牛两天；九尺井，公式答五天，蜗牛四天；十尺井两边都答五天。正公式（井深不过三尺答一天，否则井深减三除以二向上取整再加一）五口井全对，已并入第一段程序与两条公式的对照实跑。弹簧板样例四次弹跳出界，出界的落点在第七个位置；第三块板弹跳距离三，未被踩到。

② 今夜习题两道，评论区见。

Ⅰ 笼子里关着鸡和兔，数头三十五个，数脚九十四只。不许列方程，也别替动物抬脚，让机器把每一种可能都过一遍，鸡几只，兔几只。提示就一句，候选列得出来吗，脚数验得出来吗。

Ⅱ 读入一个整数，从个位起一位一位吐出来。90321 要吐出 1、2、3、0、9，中间那个 0 不许漏。

你算出来了吗？评论区见。（答案与参考程序，收在书后《参考解答》。）

本书目录导航上一篇：第五夜 春节晚会魔术牌的秘密 下一篇：第七夜（连载中） 起点：卷首语·算法童话

版权声明：本文为作者原创，受著作权法保护。未经授权禁止转载、搬运、摘编、改编及任何形式的二次创作；个人学习引用请注明作者与原文出处。转载授权请联系作者（CSDN 私信）。侵权必究。