企业官网建设流程全解析

第九夜 · 卖火柴的小女孩的游戏

第九夜，让我们走进安徒生童话，听听他笔下卖火柴小女孩与大年夜游戏的故事。

篮子里还剩三十一支火柴，我数了三遍。数目越数越清楚，天却越来越黑。大年夜的雪落个不停，街两旁的窗户一格一格地亮起来，窗里全是热的，烤鹅和热面包的香气从窗缝里挤出来。只有我站在墙角，光着两只脚，雪把脚背一点一点盖住。

火柴一支也没有卖掉。一整天我等在街角，看大人的靴子一双一双从我面前掠过去，没有一双停下来。我学会了看人。赶着回家的不买，手挽着手说笑的不买，酒气熏熏大声吆喝的更不买。天黑透了，我不敢回家，火柴没有换成钱，回去父亲要打我的。再说，家里跟街上一样冷，屋顶上只有一层破草毡，最大的裂缝拿草和破布堵着，风照样灌进来。

祖母在的时候，冬天晚上我不用上街。屋里冷得早，祖母舍不得点灯，就抓一把火柴摊在桌上，跟我玩游戏。她把火柴分成几堆，我们轮流拿，谁拿到最后一支谁赢。她教过我一句口诀，数目是要成双的，把落单的留给对手。跟我说这话的时候，她在桌上画了下面这张图。

我那时看不大懂那些一和零，只记得清清楚楚，图上每一对一都被弧线牵在一起，谁也不落单。跟着这张图摆，摆着摆着，桌上的火柴就全到了我手里。祖母夸我，说这双手将来饿不死。祖母是去年冬天走的，走的那晚也下着雪。

一双大靴子在我的篮子前面停住了。我抬起头，是一位先生，呢子大衣，领子上落着雪，眉毛也是白的。他蹲下来，蹲得跟我一般高，声音放得很轻。他问，孩子，这么晚了，怎么还不回家。我说，火柴没有卖掉，不敢回去。他从口袋里摸出几枚铜板，说，火柴我全要了，不用找了。

我把篮子往怀里收了收，摇头。祖母说过，钱要凭本事挣，白给的钱拿在手里，跟讨来的一样。他捏着铜板愣在那里，大概没有想过，一个卖火柴的小女孩还会摇头。

我看看他，又看看篮子，心里有一个主意冒出来。我说，先生，我们玩个游戏吧。我从篮子里数出六支火柴，摆在两人中间的石阶上，一堆一支，一堆两支，一堆三支。我们轮流拿，每次只许从同一堆里拿，拿几支随便，不许不拿，谁拿到最后一支火柴谁就赢了。您赢了，这六支白送您，篮子里剩下的也白送。我赢了，您把火柴全部买走，一枚铜板一支，公道价。

他说，要是我不玩呢。

我说，那火柴还在这儿，您走您的路。

他笑了，把我从头到脚打量了一遍，又看了看那三小堆火柴，像大人看小孩掏出一件宝贝。他说，好，依你。他顿了顿，又说，局是你摆的，我先拿，这总公道了吧。

我说，本该如此。客人先请。

他从最长那堆里抽走一支，在指头上转了转，漫不经心的，像在等我后悔。三堆成了一支、两支、两支。

我盯着石阶上的三堆，祖母的口诀在心里走了一遍。我把单着的那一堆收进掌心，桌上剩下两堆，每堆两支。

他愣了一下，又从方才那堆抽走一支。一堆两支，一堆一支。

我把两支那堆收走一支。桌上剩下一支、一支，齐齐的一对。

他抽走其中一支。最后一支火柴立在雪地上，孤零零的。

我伸手把它拿了起来。

他把六支火柴拢在掌心数了一遍，又数了一遍，蹲在那里把三堆重新摆回一支、两支、三支，自己跟自己走了一遍，走一步，停一停，眉头越皱越紧。走完他把火柴一拢，说，再来一把。

我说，说出去的话，要作数。

他不说话了。街上安静，雪落下来有细细的声音。过了一会儿，他数出六枚铜板，一枚一枚码在石阶上，又指了指我的篮子问，还剩多少。我说，二十五支。他说，一并算上。三十一枚铜板全放在我的手心里，压得手腕往下一沉。

他问，谁教你的。

我说，祖母。

他说，替我谢谢她。

我张了张嘴，没有说祖母已经不在了。我说，好。

我往家跑。铜板在口袋里叮叮当当地响，像一小串过年的铃铛。窗户里的灯还是那么亮，烤鹅的香气还是那么浓，可是从前它们是别人的，今晚起也算我的一份。雪还在下，落在脸上，不冷了。

祖母说过，火柴划一支就少一支，玩法却不会，你把它讲给别人听，它就一直亮着。今晚我把它讲给一位先生听了。往后每一个大年夜，他都会记得有一年雪夜，他输给过一个卖火柴的小女孩，输得心服口服，还替她把三十一支火柴全数买走。火柴卖完了。祖母的玩法，从今晚起，也在别人那里亮着了。

public class MatchGame { // 桌上所有堆一起做异或，得出这一手的局面值 static int nimSum(int[] piles) { int x = 0; for (int p : piles) { x ^= p; } return x; } // 祖母口诀的机器版：局面值为零，轮到走的人必败 // 必胜的一手，挑出一堆拿走若干支，把局面值送回零 static int[] zeroMove(int[] piles) { int x = nimSum(piles); for (int i = 0; i < piles.length; i++) { int keep = piles[i] ^ x; if (keep < piles[i]) { return new int[]{i, piles[i] - keep}; } } return null; } public static void main(String[] args) { int[] piles = {1, 2, 3}; System.out.println("start A=1 B=2 C=3, xor=" + nimSum(piles) + ", first player must lose"); // 先生第一手，从最长那堆抽一支 piles[2] -= 1; print("man", piles); while (piles[0] + piles[1] + piles[2] > 0) { // 小女孩接招，把零找回来 int[] mv = zeroMove(piles); piles[mv[0]] -= mv[1]; print("girl", piles); if (piles[0] + piles[1] + piles[2] == 0) { break; } int i = 2; while (piles[i] == 0) { i--; } piles[i] -= 1; print("man", piles); } System.out.println("last stick taken by girl"); } static void print(String who, int[] p) { System.out.println(who + " -> A=" + p[0] + " B=" + p[1] + " C=" + p[2] + ", xor=" + nimSum(p)); } }

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

Ⅰ Nim 定理 任取若干堆火柴，两人轮流从其中一堆取，至少一支，取到最后一支者胜。把所有堆的支数一起做异或，结果是零则轮到走的人必败，非零则轮到走的人必胜。此判定即 Nim 定理，由查尔斯·布顿（Charles L. Bouton）1901 年在《数学年刊》第二编第三卷首次发表，论文题目直译为《Nim，一个有完整数学理论的游戏》，载于该卷 35 至 39 页（真）。布顿时在哈佛大学（真）。

Ⅱ 词源 布顿本人未解释 Nim 一名的来历。通行说法是德语动词 nehmen 的命令式 nimm，意思是拿，牛津英语字典持此说，布顿早年留学莱比锡，通德语（真）。另有一说是古英语废动词 nim，拿、窃（真，两说并存）。至于 Nim 倒过来拼正是 win 一节，属后世趣谈，无出处可考，不入正文，登记备查。

Ⅲ 祖母的口诀与异或 口诀说，数目是要成双的，把落单的留给对手。它的原理是把每堆支数写成二进制之后逐位配对（真）。一支、两支、三支写成 01、10、11，两个数位上各自恰好有两个一，双双成对，合起来异或得零（真）。定理保证，从成双局面出发，任何一手都会拆散某一双，对手从零局面走一步必得非零；而轮到守局的人总能再配成一对，非零局面必存在一步归零。所以先落在成双局面里的人必败（真）。本夜正文的 1、2、3 正是这样一手成双局，先拿的先生无论怎么取，守局的人总走得出下一步成双（实跑见 Ⅴ）。

Ⅳ 安徒生原作 《卖火柴的小女孩》，丹麦语原题 Den lille Pige med Svovlstikkerne，1845 年 12 月发表（真）。原作故事发生在大年夜，即 12 月 31 日，一年的最后一夜，通行中译即作大年夜（真）。破草毡屋顶、裂缝堵草、光脚、墙角擦火柴、烤鹅香气，均为原作细节（真）。原作里祖母早在故事之前就已过世，只在火柴的光里出现过一回；本夜沿用祖母已故的设定，生前教火柴游戏一段为编（编）。路人、游戏与火柴买卖的结局皆为本夜改编（编）。

Ⅴ 实跑记录 本夜 Java 程序两件（JDK 21）。其一，正文所载 MatchGame，六手全程照排，先生三手各取一支，守局三手逐一归零，最后一支落在守局人手里，与正文逐句对上。其二，NimGame 收在随书代码库，三笔验证全数通过，两堆三堆支数各不超过十五的全部 4352 个局面，异或判定与机器一步一步试出来的胜负完全一致，无一分歧；两堆到四堆、支数十五以内的随机一千零一局，该先手时先手，该让先手时让先手，守局打法未输一局；祖母配对图的 1、2、3 三堆，异或得零，先手必败，与图 9-1 相符。

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

Ⅰ 那位先生回家越想越不服，第二天摆了三堆火柴请他侄子先拿，这回是一支、两支、四支。先拿的人是赢是输？写一段代码算一算，再找出必胜的第一手，看看它摆出来的是个什么局面。

Ⅱ 随便取两个不同的数当两堆支数，再把第三堆摆成这两堆支数的异或。用代码验证，这样摆出来的三堆，先拿的人必败。再想一想，这是为什么。

Ⅲ 后来那位先生自己也学乖了。又一个雪夜，他摆了四堆火柴，一支、两支、四支、七支，请小女孩先拿。小女孩看了一眼说，还是您先请吧。写代码算一算这四堆的局面值，说说她为什么让。

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

本书目录导航上一篇：第八夜 switch 穿透的魔法 让一版受伤的代码成为了断臂的维纳斯 下一篇：第十夜 方程之业 起点：卷首语·算法童话

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