第九夜 · 卖火柴的小女孩的游戏第九夜让我们走进安徒生童话听听他笔下卖火柴小女孩与大年夜游戏的故事。篮子里还剩三十一支火柴我数了三遍。数目越数越清楚天却越来越黑。大年夜的雪落个不停街两旁的窗户一格一格地亮起来窗里全是热的烤鹅和热面包的香气从窗缝里挤出来。只有我站在墙角光着两只脚雪把脚背一点一点盖住。火柴一支也没有卖掉。一整天我等在街角看大人的靴子一双一双从我面前掠过去没有一双停下来。我学会了看人。赶着回家的不买手挽着手说笑的不买酒气熏熏大声吆喝的更不买。天黑透了我不敢回家火柴没有换成钱回去父亲要打我的。再说家里跟街上一样冷屋顶上只有一层破草毡最大的裂缝拿草和破布堵着风照样灌进来。祖母在的时候冬天晚上我不用上街。屋里冷得早祖母舍不得点灯就抓一把火柴摊在桌上跟我玩游戏。她把火柴分成几堆我们轮流拿谁拿到最后一支谁赢。她教过我一句口诀数目是要成双的把落单的留给对手。跟我说这话的时候她在桌上画了下面这张图。我那时看不大懂那些一和零只记得清清楚楚图上每一对一都被弧线牵在一起谁也不落单。跟着这张图摆摆着摆着桌上的火柴就全到了我手里。祖母夸我说这双手将来饿不死。祖母是去年冬天走的走的那晚也下着雪。一双大靴子在我的篮子前面停住了。我抬起头是一位先生呢子大衣领子上落着雪眉毛也是白的。他蹲下来蹲得跟我一般高声音放得很轻。他问孩子这么晚了怎么还不回家。我说火柴没有卖掉不敢回去。他从口袋里摸出几枚铜板说火柴我全要了不用找了。我把篮子往怀里收了收摇头。祖母说过钱要凭本事挣白给的钱拿在手里跟讨来的一样。他捏着铜板愣在那里大概没有想过一个卖火柴的小女孩还会摇头。我看看他又看看篮子心里有一个主意冒出来。我说先生我们玩个游戏吧。我从篮子里数出六支火柴摆在两人中间的石阶上一堆一支一堆两支一堆三支。我们轮流拿每次只许从同一堆里拿拿几支随便不许不拿谁拿到最后一支火柴谁就赢了。您赢了这六支白送您篮子里剩下的也白送。我赢了您把火柴全部买走一枚铜板一支公道价。他说要是我不玩呢。我说那火柴还在这儿您走您的路。他笑了把我从头到脚打量了一遍又看了看那三小堆火柴像大人看小孩掏出一件宝贝。他说好依你。他顿了顿又说局是你摆的我先拿这总公道了吧。我说本该如此。客人先请。他从最长那堆里抽走一支在指头上转了转漫不经心的像在等我后悔。三堆成了一支、两支、两支。我盯着石阶上的三堆祖母的口诀在心里走了一遍。我把单着的那一堆收进掌心桌上剩下两堆每堆两支。他愣了一下又从方才那堆抽走一支。一堆两支一堆一支。我把两支那堆收走一支。桌上剩下一支、一支齐齐的一对。他抽走其中一支。最后一支火柴立在雪地上孤零零的。我伸手把它拿了起来。他把六支火柴拢在掌心数了一遍又数了一遍蹲在那里把三堆重新摆回一支、两支、三支自己跟自己走了一遍走一步停一停眉头越皱越紧。走完他把火柴一拢说再来一把。我说说出去的话要作数。他不说话了。街上安静雪落下来有细细的声音。过了一会儿他数出六枚铜板一枚一枚码在石阶上又指了指我的篮子问还剩多少。我说二十五支。他说一并算上。三十一枚铜板全放在我的手心里压得手腕往下一沉。他问谁教你的。我说祖母。他说替我谢谢她。我张了张嘴没有说祖母已经不在了。我说好。我往家跑。铜板在口袋里叮叮当当地响像一小串过年的铃铛。窗户里的灯还是那么亮烤鹅的香气还是那么浓可是从前它们是别人的今晚起也算我的一份。雪还在下落在脸上不冷了。祖母说过火柴划一支就少一支玩法却不会你把它讲给别人听它就一直亮着。今晚我把它讲给一位先生听了。往后每一个大年夜他都会记得有一年雪夜他输给过一个卖火柴的小女孩输得心服口服还替她把三十一支火柴全数买走。火柴卖完了。祖母的玩法从今晚起也在别人那里亮着了。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 A1 B2 C3, 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. Bouton1901 年在《数学年刊》第二编第三卷首次发表论文题目直译为《Nim一个有完整数学理论的游戏》载于该卷 35 至 39 页真。布顿时在哈佛大学真。Ⅱ 词源 布顿本人未解释 Nim 一名的来历。通行说法是德语动词 nehmen 的命令式 nimm意思是拿牛津英语字典持此说布顿早年留学莱比锡通德语真。另有一说是古英语废动词 nim拿、窃真两说并存。至于 Nim 倒过来拼正是 win 一节属后世趣谈无出处可考不入正文登记备查。Ⅲ 祖母的口诀与异或 口诀说数目是要成双的把落单的留给对手。它的原理是把每堆支数写成二进制之后逐位配对真。一支、两支、三支写成 01、10、11两个数位上各自恰好有两个一双双成对合起来异或得零真。定理保证从成双局面出发任何一手都会拆散某一双对手从零局面走一步必得非零而轮到守局的人总能再配成一对非零局面必存在一步归零。所以先落在成双局面里的人必败真。本夜正文的 1、2、3 正是这样一手成双局先拿的先生无论怎么取守局的人总走得出下一步成双实跑见 Ⅴ。Ⅳ 安徒生原作 《卖火柴的小女孩》丹麦语原题 Den lille Pige med Svovlstikkerne1845 年 12 月发表真。原作故事发生在大年夜即 12 月 31 日一年的最后一夜通行中译即作大年夜真。破草毡屋顶、裂缝堵草、光脚、墙角擦火柴、烤鹅香气均为原作细节真。原作里祖母早在故事之前就已过世只在火柴的光里出现过一回本夜沿用祖母已故的设定生前教火柴游戏一段为编编。路人、游戏与火柴买卖的结局皆为本夜改编编。Ⅴ 实跑记录 本夜 Java 程序两件JDK 21。其一正文所载 MatchGame六手全程照排先生三手各取一支守局三手逐一归零最后一支落在守局人手里与正文逐句对上。其二NimGame 收在随书代码库三笔验证全数通过两堆三堆支数各不超过十五的全部 4352 个局面异或判定与机器一步一步试出来的胜负完全一致无一分歧两堆到四堆、支数十五以内的随机一千零一局该先手时先手该让先手时让先手守局打法未输一局祖母配对图的 1、2、3 三堆异或得零先手必败与图 9-1 相符。② 今夜习题三道评论区见。Ⅰ 那位先生回家越想越不服第二天摆了三堆火柴请他侄子先拿这回是一支、两支、四支。先拿的人是赢是输写一段代码算一算再找出必胜的第一手看看它摆出来的是个什么局面。Ⅱ 随便取两个不同的数当两堆支数再把第三堆摆成这两堆支数的异或。用代码验证这样摆出来的三堆先拿的人必败。再想一想这是为什么。Ⅲ 后来那位先生自己也学乖了。又一个雪夜他摆了四堆火柴一支、两支、四支、七支请小女孩先拿。小女孩看了一眼说还是您先请吧。写代码算一算这四堆的局面值说说她为什么让。你算出来了吗评论区见。答案与参考程序收在书后《参考解答》。本书目录导航上一篇第八夜 switch 穿透的魔法 让一版受伤的代码成为了断臂的维纳斯 下一篇第十夜 方程之业 起点卷首语·算法童话版权声明本文为作者原创受著作权法保护。未经授权禁止转载、搬运、摘编、改编及任何形式的二次创作个人学习引用请注明作者与原文出处。转载授权请联系作者CSDN 私信。侵权必究。
第九夜 · 卖火柴的小女孩的游戏第九夜让我们走进安徒生童话听听他笔下卖火柴小女孩与大年夜游戏的故事。篮子里还剩三十一支火柴我数了三遍。数目越数越清楚天却越来越黑。大年夜的雪落个不停街两旁的窗户一格一格地亮起来窗里全是热的烤鹅和热面包的香气从窗缝里挤出来。只有我站在墙角光着两只脚雪把脚背一点一点盖住。火柴一支也没有卖掉。一整天我等在街角看大人的靴子一双一双从我面前掠过去没有一双停下来。我学会了看人。赶着回家的不买手挽着手说笑的不买酒气熏熏大声吆喝的更不买。天黑透了我不敢回家火柴没有换成钱回去父亲要打我的。再说家里跟街上一样冷屋顶上只有一层破草毡最大的裂缝拿草和破布堵着风照样灌进来。祖母在的时候冬天晚上我不用上街。屋里冷得早祖母舍不得点灯就抓一把火柴摊在桌上跟我玩游戏。她把火柴分成几堆我们轮流拿谁拿到最后一支谁赢。她教过我一句口诀数目是要成双的把落单的留给对手。跟我说这话的时候她在桌上画了下面这张图。我那时看不大懂那些一和零只记得清清楚楚图上每一对一都被弧线牵在一起谁也不落单。跟着这张图摆摆着摆着桌上的火柴就全到了我手里。祖母夸我说这双手将来饿不死。祖母是去年冬天走的走的那晚也下着雪。一双大靴子在我的篮子前面停住了。我抬起头是一位先生呢子大衣领子上落着雪眉毛也是白的。他蹲下来蹲得跟我一般高声音放得很轻。他问孩子这么晚了怎么还不回家。我说火柴没有卖掉不敢回去。他从口袋里摸出几枚铜板说火柴我全要了不用找了。我把篮子往怀里收了收摇头。祖母说过钱要凭本事挣白给的钱拿在手里跟讨来的一样。他捏着铜板愣在那里大概没有想过一个卖火柴的小女孩还会摇头。我看看他又看看篮子心里有一个主意冒出来。我说先生我们玩个游戏吧。我从篮子里数出六支火柴摆在两人中间的石阶上一堆一支一堆两支一堆三支。我们轮流拿每次只许从同一堆里拿拿几支随便不许不拿谁拿到最后一支火柴谁就赢了。您赢了这六支白送您篮子里剩下的也白送。我赢了您把火柴全部买走一枚铜板一支公道价。他说要是我不玩呢。我说那火柴还在这儿您走您的路。他笑了把我从头到脚打量了一遍又看了看那三小堆火柴像大人看小孩掏出一件宝贝。他说好依你。他顿了顿又说局是你摆的我先拿这总公道了吧。我说本该如此。客人先请。他从最长那堆里抽走一支在指头上转了转漫不经心的像在等我后悔。三堆成了一支、两支、两支。我盯着石阶上的三堆祖母的口诀在心里走了一遍。我把单着的那一堆收进掌心桌上剩下两堆每堆两支。他愣了一下又从方才那堆抽走一支。一堆两支一堆一支。我把两支那堆收走一支。桌上剩下一支、一支齐齐的一对。他抽走其中一支。最后一支火柴立在雪地上孤零零的。我伸手把它拿了起来。他把六支火柴拢在掌心数了一遍又数了一遍蹲在那里把三堆重新摆回一支、两支、三支自己跟自己走了一遍走一步停一停眉头越皱越紧。走完他把火柴一拢说再来一把。我说说出去的话要作数。他不说话了。街上安静雪落下来有细细的声音。过了一会儿他数出六枚铜板一枚一枚码在石阶上又指了指我的篮子问还剩多少。我说二十五支。他说一并算上。三十一枚铜板全放在我的手心里压得手腕往下一沉。他问谁教你的。我说祖母。他说替我谢谢她。我张了张嘴没有说祖母已经不在了。我说好。我往家跑。铜板在口袋里叮叮当当地响像一小串过年的铃铛。窗户里的灯还是那么亮烤鹅的香气还是那么浓可是从前它们是别人的今晚起也算我的一份。雪还在下落在脸上不冷了。祖母说过火柴划一支就少一支玩法却不会你把它讲给别人听它就一直亮着。今晚我把它讲给一位先生听了。往后每一个大年夜他都会记得有一年雪夜他输给过一个卖火柴的小女孩输得心服口服还替她把三十一支火柴全数买走。火柴卖完了。祖母的玩法从今晚起也在别人那里亮着了。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 A1 B2 C3, 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. Bouton1901 年在《数学年刊》第二编第三卷首次发表论文题目直译为《Nim一个有完整数学理论的游戏》载于该卷 35 至 39 页真。布顿时在哈佛大学真。Ⅱ 词源 布顿本人未解释 Nim 一名的来历。通行说法是德语动词 nehmen 的命令式 nimm意思是拿牛津英语字典持此说布顿早年留学莱比锡通德语真。另有一说是古英语废动词 nim拿、窃真两说并存。至于 Nim 倒过来拼正是 win 一节属后世趣谈无出处可考不入正文登记备查。Ⅲ 祖母的口诀与异或 口诀说数目是要成双的把落单的留给对手。它的原理是把每堆支数写成二进制之后逐位配对真。一支、两支、三支写成 01、10、11两个数位上各自恰好有两个一双双成对合起来异或得零真。定理保证从成双局面出发任何一手都会拆散某一双对手从零局面走一步必得非零而轮到守局的人总能再配成一对非零局面必存在一步归零。所以先落在成双局面里的人必败真。本夜正文的 1、2、3 正是这样一手成双局先拿的先生无论怎么取守局的人总走得出下一步成双实跑见 Ⅴ。Ⅳ 安徒生原作 《卖火柴的小女孩》丹麦语原题 Den lille Pige med Svovlstikkerne1845 年 12 月发表真。原作故事发生在大年夜即 12 月 31 日一年的最后一夜通行中译即作大年夜真。破草毡屋顶、裂缝堵草、光脚、墙角擦火柴、烤鹅香气均为原作细节真。原作里祖母早在故事之前就已过世只在火柴的光里出现过一回本夜沿用祖母已故的设定生前教火柴游戏一段为编编。路人、游戏与火柴买卖的结局皆为本夜改编编。Ⅴ 实跑记录 本夜 Java 程序两件JDK 21。其一正文所载 MatchGame六手全程照排先生三手各取一支守局三手逐一归零最后一支落在守局人手里与正文逐句对上。其二NimGame 收在随书代码库三笔验证全数通过两堆三堆支数各不超过十五的全部 4352 个局面异或判定与机器一步一步试出来的胜负完全一致无一分歧两堆到四堆、支数十五以内的随机一千零一局该先手时先手该让先手时让先手守局打法未输一局祖母配对图的 1、2、3 三堆异或得零先手必败与图 9-1 相符。② 今夜习题三道评论区见。Ⅰ 那位先生回家越想越不服第二天摆了三堆火柴请他侄子先拿这回是一支、两支、四支。先拿的人是赢是输写一段代码算一算再找出必胜的第一手看看它摆出来的是个什么局面。Ⅱ 随便取两个不同的数当两堆支数再把第三堆摆成这两堆支数的异或。用代码验证这样摆出来的三堆先拿的人必败。再想一想这是为什么。Ⅲ 后来那位先生自己也学乖了。又一个雪夜他摆了四堆火柴一支、两支、四支、七支请小女孩先拿。小女孩看了一眼说还是您先请吧。写代码算一算这四堆的局面值说说她为什么让。你算出来了吗评论区见。答案与参考程序收在书后《参考解答》。本书目录导航上一篇第八夜 switch 穿透的魔法 让一版受伤的代码成为了断臂的维纳斯 下一篇第十夜 方程之业 起点卷首语·算法童话版权声明本文为作者原创受著作权法保护。未经授权禁止转载、搬运、摘编、改编及任何形式的二次创作个人学习引用请注明作者与原文出处。转载授权请联系作者CSDN 私信。侵权必究。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
