五子棋^[wǔ zǐ qí] （两人对弈的策略型棋类游戏）

五子棋是全国智力运动会竞技项目之一，是一种两人对弈的纯策略型棋类游戏。

有两种玩法。玩法一：双方分别使用黑白两色的棋子，下在棋盘直线与横线的交叉点上，先形成五子连线者获胜。

玩法二：自己形成五子连线就替换对方任意一枚棋子。被替换的棋子可以和对方交换棋子。最后以先出完所有棋子的一方为胜。

五子棋的棋具与围棋通用，是一种的传统黑白棋种。围棋主要流行于东亚以及欧洲的一些国家。

五子棋容易上手，老少皆宜，而且趣味横生，引人入胜；它不仅能增强思维能力，提高智力，而且富含哲理，有助于修身养性。五子棋已在各个游戏平台有应用。

|||

|-|-|

|中文名|五子棋|

|外文名|Gomoku|

||五目並べ|

|类别|棋类游戏|

|游戏人数|2人|

|使用物品|棋盘、棋子、棋钟棋 盘15道盘|

|棋子|黑白棋子起源地区东亚地区|

|流行地区|东亚、欧洲|

|性质|全国智力运动会竞技项目|

[TOC]

称谓

五子棋，日文亦有连五子、五子连、串珠、五目、五目碰、五格、五石、五法、五联、京棋等多种称谓；英文则称之为FIR（Five In A Row的缩写）、Gomoku（日语“五目”的罗马拼音）、Gobang、connect 5、mo-rphion等；捷克文piskvorky，韩文omok等等。

许多国家的人对五子棋都有不同的爱称，例如，韩国人把五子棋称为“情侣棋”，表示情人之间下五子棋有利于增加情感的交流；欧洲人称其为“绅士棋”，代表下五子棋的君子风度胜似绅士；日本人则称其为“中老年棋”，说明五子棋适合中老年人的生理特点和思维方式。

历史沿革

发展

针对先行必胜的改革

随着五子棋的发展，逐步发现先行优势非常大，最后得出“先行必胜”。五子棋要成为竞技运动，核心问题是怎样解决传统五子棋下法中“先行必胜”的问题。

“竞技五子棋”就是参赛双方以棋盘和棋子为介体，进行智力性对抗的竞技体育项目。

• “交换”思维

  “交换”思维有个形象的比喻：一个人切蛋糕，一个人选蛋糕。即：一人开局，另一人选择黑方还是白方。此方法最为公平、最有效率，且最为简洁实用。不过此方法使开局者不走已知的必胜，把棋艺的较量演化为对局者开局的博弈，而“必胜开局”依然存在。

如：欧洲的Swap2、Swap1；中国的Swap3、一手交换规则等。

• “禁手”思维

  禁止以某种手段取胜。为了平衡先后手之间的差距，削弱先手优势，日本连珠提出“禁手”。后来连珠的发展证明禁手并不能平衡先后手之间的差距，依然是“先行必胜”。

• “泡沫”原理

  像泡沫一样会破灭。如“吃子”五子棋。连成5个后消失，同时拿掉对方一个棋子，自己再补一子。此原理的的特点是：把五子棋金球制改成了“进球制”，同时也最大效率地利用了棋盘和棋子，带来了全新的思维。问题是怎样计算胜负。

• “井字游戏”原理

  井字游戏又叫圈叉棋，圈叉棋是和棋，原因是空间很小。

  通过缩小棋盘来抑制五子棋先行的优势。如：15路棋盘，13路棋盘等等。问题是多大的棋盘才能是和棋，知道和棋后还能成为竞技运动吗。

• “跷跷板”原理

  五子棋始终是先行领先一子。如果双方轮流领先一子呢？

  台湾教授发明的六子棋，就如“跷跷板”一样。先行先下一子，然后双方轮流下两子，先连成6子者胜利。六子棋为第11届奥林匹亚计算机游戏程序竞赛项目，验证其公平性与复杂性。

• “连珠棋”原理

  “禁手”思维+“交换”思维+“井字游戏”原理=连珠

  如：RIF 规则、Sakata 规则、Yamaguchi 规则、Tarannikov 规则等。

现状

五子棋、六子棋、连珠已经成为欧洲现代五子棋的组成部分，举行了很多次大大小小的比赛，并且将三种棋的世界锦标赛联合举行。

中国的现代五子棋还处于起步阶段。2003年中国棋院《中国五子棋竞赛规则》参考了RIF规则，同时兼顾发展传统五子棋。

棋具编辑

棋盘

棋盘(2张)

棋盘可用木料、硬纸、塑料、布料、石料或环保材料等制成。棋盘由横纵各15条等距离，垂直交叉的平行线构成，在棋盘上，横纵线交叉形成了225个交叉点为对弈时的落子点。邻近两个交叉点的距离要略大于棋子的直径，纵线距离约为2.5厘米，横线约为2.4厘米。

以对局开始时的黑方为准，棋盘上的纵行线从近到远用阿拉伯数字1—15标记，横行线从左到右用英文字母A—O按字母顺序标记。由于每个英文字母都对应着一条纵线，每个阿拉伯数字都对应着一条横线，所以，棋盘上的每一个交叉点都可用英文字母和阿拉伯数字的组合来标示出来。在标示各点时，要将英文字母放在前边，阿拉伯数字放在后边。如“L6”“F4”等，不可以标示成“6L”“4F”。

在棋盘上有5个比较特殊的交叉点，用直径约为0.5厘米的，和棋盘横纵线颜色相同的实心小圆点标示出来，这5个点称为“星”。中间的星也称天元，位置在H8，表示棋盘的正中心。其他4个星，也叫小星，分别在D12、L12、D4、L4位置。星在棋盘上起标示位置的作用，利于在行棋、复盘、记录等时，更清晰、迅速地找到所需位置。

棋子

棋子分黑白两色。棋子形状为扁圆形，有一面凸起或两面凸起均可。棋子厚度一般不超过0.8厘米，直径应比棋盘上邻近点间的距离略小些，以免影响在棋盘上的行棋。以2.0—2.3厘米为宜。

平时下棋，棋子数量不限，以下棋时够用为准。正规的标准数一般定为黑子113枚，白子112枚。

棋子材质，重量不限。但以硬质，不易磨损，且放在棋盘上具有一定稳定性为好。

棋具，主要指上面论述的棋盘和棋子，有了这两样，开始下棋已够用了。

谱纸

谱纸也可称记谱纸，顾名思义，它是用来记录对局或着法时所用的稿纸，主要用在比赛或练习时，记录对局双方行棋顺序和位置的专用纸。谱纸的图形应是按比例缩小的棋盘图形。

棋钟

棋钟是在练习或比赛时，计算棋类对局双方时间的专用钟。棋钟分机械钟和电子钟等，均能用倒计时的方法，准确地分别显示出对局双方采用时限减去自己累计用时所剩余的时间。棋钟要求尽量避免刺眼，运行时声响应很低弱或无声。

规则

（1）对局双方各执一色棋子。

（2）空棋盘开局。

（3）黑先、白后，交替下子，每次只能下一子。

（4）棋子下在棋盘的空白点上，棋子下定后，不得向其它点移动，不得从棋盘上拿掉或拿起另落别处。

（5）黑方的第一枚棋子可下在棋盘任意交叉点上。

（6）轮流下子是双方的权利，但允许任何一方放弃下子权（即：PASS权）。

五子棋对局，执行黑方指定开局、三手可交换、五手两打的规定。整个对局过程中黑方有禁手，白方无禁手。黑方禁手有三三禁手、四四禁手和长连禁手三种。 [1]

段级位制

中国五子棋段级位制（试行）（具体内容见参考资料）

五子棋的段级位对象：参加中国棋院认可的国内外五子棋比赛的五子棋爱好者。

第四条段位共分九个等级，最高是九段，以下分别是八段、七段、六段、五段、四段、三段、二段、初段。段位以下共分十个等级，最高是一级，以下分别是二级、三级、四级、五级、六级、七级、八级、九级、十级。

第五条根据中国五子棋爱好者在国内、国际交流中所体现出来的实际水平，在五子棋段级位制度实施初期，对爱好者授予的最高段位暂定为六段。随着中国棋手参与国内外交流机会的增加和技术水平的提高，逐步增加所授予段位的上限，直至九段。

在中国，获得段级位的主要渠道是通过比赛。在全国五子棋邀请赛等国内大赛中获得一定名次，即可获得相应段位。

（相关规定见参考资料）

术语

对局语

|||

|-:|:-|

|〖黑方〗|执黑棋一方的简称。|

|〖白方〗|执白棋一方的简称。|

|〖胜局〗|有一方获胜的对局。|

|〖和局〗|分不出胜负的对局。|

|〖终局〗|对局结束。|

|〖复盘〗|对局双方将本盘对局全过程的再现。|

行棋语

|||

|-:|:-|

|〖阳线〗|即：直线，棋盘上可见的横纵直线。|

|〖交叉点〗|阳线垂直相交的点，简称“点”。|

|〖阴线〗|即：斜线，由交叉点构成的与阳线成45°夹角的隐形斜线。|

|〖落子〗|棋子直接落于棋盘的空白交叉点上。|

|〖轮走方〗|即“行棋方”，有权利落子的黑方或白方。|

|〖着〗|在对局过程中，行棋方把棋子落在棋盘无子的点上，不论落子的手是否脱离棋子，均被视为一着。|

|〖回合〗|双方各走一着，称为一个回合。|

|〖开局〗|在对局开始阶段形成的布局。|

|〖连〗|同色棋子在一条阳线或阴线上相邻成一排。|

|〖长连〗|五枚以上同色棋子在一条阳线或阴线上相邻成一排。是禁手的一种。|

|〖五连〗|只有五枚同色棋子在一条阳线或阴线上相邻成一排。|

|〖成五〗|一般包括五连和长连，指含有五枚同色棋子所形成的连；在有禁手规则中，黑方形成长连不称为“成五”。|

|〖四〗|在一条阳线或阴线上连续相邻的5个点上只有四枚同色棋子的棋型。|

|〖活四〗|有两个点可以成五的四。|

|〖冲四〗|只有一个点可以成五的四。|

|〖死四〗|不能成五的四。|

|〖三〗|在一条阳线或阴线上连续相邻的5个点上只有三枚同色棋子的棋型。|

|〖活三〗|再走一着可以形成活四的三。|

|〖连活三〗|连续、中间不隔空点的活三（同色棋子在一条阳线或阴线上相邻成一排的活三）。简称“连三”。|

|〖跳活三〗|中间隔有一个空点的活三。简称“跳三”。|

|〖眠三〗|再走一着可以形成冲四的三。|

|〖死三〗|不能成五的三。|

|〖二〗|在一条阳线或阴线上连续相邻的5个点上只有两枚同色棋子的棋型。|

|〖活二〗|再走一着可以形成活三的二。|

|〖连活二〗|连续、中间不隔空点的活二（同色棋子在一条阳线或阴线上相邻成一排的活二）。简称“连二”。|

|〖跳活二〗|中间隔有一个空点的活二。简称“跳二”。|

|〖大跳活二〗|中间隔有两个空点的活二。简称“大跳二”。|

|〖眠二〗|再走一着可以形成眠三的二。|

|〖死二〗|不能成五的二。|

|〖先手〗|对方必须应答的着法，相对于先手而言，冲四称为“绝对先手”。|

|〖三三〗|一子落下同时形成两个活三。也称“双三”或“双活三”。是禁手的一种。|

|〖四四〗|一子落下同时形成两个冲四。也称“双四”。是禁手的一种。|

|〖四三〗|一子落下同时形成一个冲四和一个活三。|

|〖做杀〗|落下一子，使己方下一手可以形成双三、双四、四三等杀法。|

|〖禁手〗|部分规则中为削弱黑方先行优势而禁止其使用的战术，包括双三、双四、长连。白方无禁手。|

|〖禁手点〗|黑方禁手的点。|

战术语

|||

|-:|:-|

|〖VCT〗|英文Victory by Continuous Threat的缩写，即通过连续不断的冲四、活三、做杀等先手进攻取得胜利。|

|〖VCF〗|英文Victory of Continuous Four的缩写，即以连续不断的冲四取得胜利。又称“追四”。|

|〖风车轮〗|指在一定区域内来回地绕着连续进攻的战术或技巧，就像一个风车轮一直在转着似的，这样的取胜方法也称之为“风车胜”。|

|〖二头蛇〗|指某一方以活三进攻时，无论对方防守于哪一头都难免被蛇头咬伤，因为此时的活三如同二头蛇一样，两头都有厉害的杀招。也称“两头蛇”。|

|〖一子双杀〗|一子落下，同时形成两种取胜方法。|

|〖一子双防〗|一子落下，同时防守两种取胜方法。|

|〖八卦阵〗|以“日”字的一组对角点为棋型，互为马步的防守阵型。|

|〖抓禁手〗|有禁手规则中，白方通过冲四等手段迫使黑方在禁手点落子的取胜方法。也称“追下取胜”。|

比赛语

|||

|-:|:-|

|〖个人赛〗|计算个人成绩的比赛。|

|〖团体赛〗|计算运动队团体成绩的比赛。|

|〖轮空〗|赛制中部分选手直接从中间某轮开始参加比赛，某轮未比赛的安排就叫轮空。|

|〖节〗|一个比较集中的比赛单位时间（如一个上午或一个下午或一个晚上）称一“节”。|

|〖轮〗|参赛的各队（团体赛）或各名棋手（个人赛）普遍出场比赛一次（个别轮空者除外）称一“轮”。|

|〖次〗|团体赛中的同一轮两队之间完成的比赛称为一“次”比赛。|

|〖场〗|两名棋手之间完成的两局制或多局制的一次比赛称为一“场”比赛。|

|〖局〗|两名棋手之间完成的一盘比赛称为一“局”比赛。|

技巧

五子兵法

中国现代五子棋的开拓者那威荣誉九段，多年钻研五子棋，潜心发掘五子棋的中国民间阵法，他总结了五子棋行棋的要领和临阵对局的经验，得出一套“秘诀”，谓之《那氏五子兵法》：

先手要攻，后手要守，以攻为守，以守待攻。

攻守转换，慎思变化，先行争夺，地破天惊。

守取外势，攻聚内力，八卦易守，成角易攻。

阻断分隔，稳如泰山，不思争先，胜如登天。

初盘争二，终局抢三，留三不冲，变化万千。

多个先手，细算次先，五子要点，次序在前。

斜线为阴，直线为阳，阴阳结合，防不胜防。

连三连四，易见为明，跳三跳四，暗剑深藏。

己落一子，敌增一兵，攻其要点，守其必争。

势已形成，败即降临，五子精华，一子输赢。

基本技巧

一、四种摆放（形象的叫法）：

二、最常见的取胜法：一子双杀，既落下一个子，同时形成两条棋路，使对手封住一条，就来不及封住另一条，从而取胜。

三、不堵情况下，一子双杀的十大基本棋路：

两头空

边二空

跳二空

中二空

两头空

图1

图2

图3

图4

边二空

图2

图5

图6

图7

跳二空

图3

图6

图8

图9

中二空

图4

图7

图9

图10

图示说明：

圆形图标：表示已经落下的棋子。

十字图标：之后落下的棋子，同时形成两条棋路，使对手堵住其中一路，就来不及去堵另一路。

图1：两头空-两头空

图2：两头空-边二空

图3：两头空-跳二空

图4：两头空-中二空

图5：边二空-边二空

图6：边二空-跳二空

图7：边二空-中二空

图8：跳二空-跳二空

图9：跳二空-中二空

图10：中二空-中二空

四、一头被堵情况下，一子双杀的八大基本棋路。

一头被堵情况下，落下一个子，形成两条棋路，使一头被堵的那条棋路形成四个连子，没有被堵的那条棋路，形成三个子的棋路，可以是两头空、边二空、跳二空、中二空，从而使对手堵住一路，就来不及堵另一路。

两头空

边二空

跳二空

中二空

内插连四

图1

图2

图3

图4

外插连四

图5

图6

图7

图8

分为两种情况：

1.从被堵棋路的内部形成四颗子：

图1：内插连四-两头空

图2：内插连四-边二空

图3：内插连四-跳二空

图4：内插连四-中二空

2.从被堵棋路的外部形成四颗子：

图5：外插连四-两头空

图6：外插连四-边二空

图7：外插连四-跳二空

图8：外插连四-中二空

开局技巧

五子棋的开局也称布局，一般在3至7手左右完成。五子棋的开局是十分重要的。一般情况下，一局五子棋的着数在20至40着之间，因此，它的开局阶段是非常短暂的，大约在七八着至十几着之间。在这一阶段的争夺中，双方的布局、应答将对以后的胜负起着关键的作用。一般来说，黑棋以攻为主，而白棋则以防为主。

直止打法开局

在开局阶段，双方主要是二的争夺。双方必须设法创造自己的连二、活二、跳二或大跳二等，同时要阻挡对方的活二。无论哪种开局，均体现出这一规律。

可以说，哪一方的二做得多（有两个以上的活二），或者有效地阻挡住对方的活二，那么，哪一方的胜率就比较大。另外，开局时每一个次序、每一种节奏都不能忽视，输赢就在一步之差。

为了便于记忆、区分以及比赛。只对前3步组成的棋形进行了部分取名。

比赛中的开局

开局形状均以“星”和“月”命名。（参考资料中“第三条”）

斜止打法开局

全国正式比赛均采用26种开局，包括斜指开局的长星局、峡月局、恒星局、水月局、流星局、云月局、浦月局、岚月局、银月局、明星局、斜月局、名月局、慧星局和直指开局的寒星局、溪月局、疏星局、花月局、残月局、雨月局、金星局、松月局、丘月局、新月局、瑞星局、山月局、游星局。

《彭氏口诀》

黑方必负开局

黑方必负开局

二十六局先弃二，直指游星斜慧星。

寒星溪月疏星首，花残二月并白莲，

雨月金星追黑玉，松丘新宵瑞山腥。

星月长峡恒水流，白莲垂俏云浦岚，

黑玉银月倚明星，斜月名月堪称朋。

残局技巧

从取胜的途径来分类，五子棋的残局技巧可分为两类：四三取胜和抓禁手取胜。由这两类技巧又可派生（Fork）出一子双杀、一子多杀、一子杀禁、VCF、VCT等等精妙的入局方式。

一子双杀

所谓“一子双杀”是指对局中出现一方有两个叫杀点（一般是有两个冲四活三点），而对方无法同时防守的情形。对局中，人们往往发现，并非每一步棋都必须是先手（特指活三或冲四）才能赢棋。有时候，某一步棋本身并不是先手，但是，有了这步棋，就出现了两个胜点或两种获胜着法，迫使对方来不及防守或无法防守而获胜，这就是“一子双杀”。可以说，“一子双杀”的技巧是五子棋技术的一层新阶梯，如果掌握了这种技巧，就表明了你的五子棋技术已经有一定的水平。

一子双禁

所谓“一子双禁”是指白方利用禁手的规则，通过一着妙棋使黑方陷入同时面临两个禁手点的困境，黑方将无法同时避免两个禁手点的情形。从另一种意义上说，这是白棋的一子双杀。

一杀一禁

所谓“一杀一禁”是指对局中出现白方有两个取胜点，其中一个为冲四活三叫杀，另一个为抓禁手取胜的棋形。

一子多杀

所谓“一子多杀”是指对局中出现一方有两个以上（如三个、四个或五个）的叫杀点，而对方无法同时防守的情形，其实质也是一子双杀。

必胜

所谓“必胜”是指某一方行至某一手后，针对对方以后的每一个防点都有一套或一套以上的胜法的着，比一子多杀的范围广。

必败

所谓“必败”是指某一方行至某一手后，对方针对这一手拥有一套或一套以上的胜法的着。（本来不该录在这一段，但作为术语还是介绍一下）

VCT

所谓VCT是英文Victory by Continuous Threat的缩写，不断利用冲四、活三、做杀等先手进攻最后取得胜利。

VCF

所谓VCF是英文Victory of Continuous Four的缩写，亦称追四，即以连续不断的冲四取得胜利。VCF是五子棋残局和各种排局中一个非常重要的取胜技术。所以，学习并掌握VCF技术是对于提高五子棋爱好者的棋艺水平来说是十分重要的。五子棋排局是人为排列出来的局面习题。

它虽然不是实战对局的产物，但是，其主题的构思往往接近于实战残局；而且，绝大多数是由字、数、形等图案构成的VCF练习题，给人以美的享受及解谜的魅力。精彩的排局和字谜往往构思精到深奥，变化引人入胜。拟制排局和拆解排局有助于锻炼全局观念和残局中攻击点的选择，培养思考和想像能力，有助于提高棋艺水平。

自由取胜

自由取胜，也就是复合取胜或混合取胜，利用一切手段，无论是活三，冲四，还是做杀，抓禁手等等方法，自由取得最后胜利的技术。最常见的自由取胜包括“风车轮”、“二头蛇”等等。

攻防策略

合并（Merge）图册

下五子棋须得法，法中变化有莫测；五子之变如水势，因势避高而趋下。战不过攻守，法不过奇正，奇正之法：往复循环，“不竭如江海，无穷如天地”。

其详法如下：围、击虚、就实、寡众。

（围）由于五子棋源于围棋，故下五子棋若想立于不败之地，须以围棋之法行棋，说白了就是“包饺子”，试想：如果对方的棋子被围住了，左冲右突都不行，前闯后退更不见效，此时他心理极度郁闷，已无斗志，棋还能下好吗？只能是输的份了！此招用于防守。

（击虚）兵法有云：“避实击虚”，下五子棋之精髓也在其理。不过此举贵在进攻，进攻若能攻其空虚之处，且得法，将会以迅雷不及掩耳之势而破竹将对手击败。此招用于进攻。

（就实）老子《道德经》中讲了万物正反两个方面及消长之理，攻守亦不过如此，故有“避实击虚”则就有“就实让虚”。“就实让虚”就是对方往哪里走棋，咱就往哪里走棋，好比随形附影一般。这招要把握好火候，不能过度也不能失度，因为下棋很容易攻守易势（攻之极乃守时，守之极乃攻时；攻中生守，守中生攻），此招用于防守。

（寡众）《孙子·虚实》中曰：“备前则后寡，备后则前寡，备左则右寡，备右则左寡，无所不备，则无所不寡。”此招用在五子棋中则反其道而行，则会收到意想不到的效果，具体招法是“堵了前面则堵后面，堵了后面则堵前面，堵了左边则堵右边，堵了右边则堵左边”，前后左右四面八方都堵，则对方则无路可逃，无棋可下！此招和（围）连用。无所不胜，用在防守。

另外，有时在有计算的前提下，连续冲三、冲四（vct、vcf）有可能创造新的进攻机会；反之，一味的VC，只能迟滞败亡的步伐，反而使自己被“围”陷入铁桶阵（一般叫马桶阵）中。除了这些外，八卦阵是防守的无二秘宝，只是明八卦太过明显，因此暗八卦（用部分八卦点做主力，少量杂子作障眼）的功底就成了衡量技术的重要指标。

参考【棋经十三篇】

另一种五子棋

农村流传的一种玩法，也叫进猪笼、五马飞、九子棋。一方选石块，一方选树棍。每人九子，五子上阵，四子后备，吃对方一子则添加一子，最后9子围对方一子进侧方猪笼为赢。棋盘为四相连米字格，加侧面一田字格“猪笼”，行棋可直线也可斜线，不限制步数，不能跳过棋子。吃子方式有，夹、挑、双夹、双挑，扫四。能看棋2步为熟练，3步为高手。

夹：两子单独夹住一子，同线上两子外不能有其他子。

挑：一子走入两子中间，同线上两子外不能有其他子。

双夹：走为四子对称夹住一子，同线上四子外不能有其他子。

双挑：一子走入对称四子中间，同线上四子外不能有其他子。

扫四：一子走到连续四子两头，同线上四子外不能有其他子。

Jon Beatlay,

ACM 通讯(communications of the ACM)

awk

计算机程序设计艺术

Fred Brooks

人月神话

Steve Mc Godneell（唐纳德？？？？

代码大全

科学美国人

cobol 怎样解题

如何快速计算一个月有多少天

简单统计一下这本书 4 出现的次数

本文的篇幅可能会过于长，且更新时间周期很长很长，所以请慢慢等待

第一章 开篇

需要对数据库的数据进行排序

密度较大

不能使用系统自带的排序函数

关于排序的几个点

在磁盘上实现归并排序，现在仿佛这本书很是有必要去看

最近物联网的概念还是比较火的，那些低功率的芯片，例如 ESP8266，

文件中最多包含一千万条记录，每一条记录都是 7 位数的整数

（尽管机器有许多兆字节的内存，但是排序功能只是大系统中的一部分，所以大概只有 1MB 的内存（其实这个算是相当奢侈了，ESP8266 里面只有 140K 来着

每个整数最多出现一次，

看到这里，其实有点基础（Base）的就会想到一个叫做桶排序的算法，因为不重复，所以可以用 bool 类型进行桶排序（也可以叫做位图法之类的

（七位数其实就是美国的座机电话号码

（由于几个小时就有一次请求（Request），所以排序时间不能太长

可以通过反复读入，进行归并排序，借用外部的文件进行中间存储。但是读写次数过多，也会很影响速度

不过那个时候的软件开发速度真的是完全比不上现在，现在一个排序算法哪需要写一个星期

graph LR;

    A --> B;

    B --> C;

    C --> B;

    B --> D;

就算一个桶排序，也不需要数个小时，这本书的初版是真的很老了，但是就是火的一批

桶排序（位图表示法）适用于数据量很大，不重复，稠密的情况，如果是一个很稀疏的数列，使用这种方法就会格外浪费空间

多趟算法

时间——空间折中与双赢

课后题

1. 如果不缺内存，如何使用一个具有库的语言来实现一种排序算法以表示和排序集合

2. 如何使用位逻辑运算（如与、或、位移）来实现位向量

3. 运行时效率是设计目标的一个重要组成部分，所得到的程序需要足够高效。在你自己的系统上实现位图排序并度量其运行时间。该时间与系统排序的运行时间以及习题1中排序的运行时间相比如何？假设n为10000000，且输入文件包含1000000个整数

4. 如果认真考虑了习题3，你将会面对生成小于n且没有重复的k个整数的问题，最简单的方法就是使用前k个正整数。这个计算的数据集合将不会明显地改变位图方法的运行时间，但是可能会歪曲系统排序的运行时间。如何生成位于0至n-1之间的k个不同的随即顺序的随机（Random）整数？尽量是你的程序简短且高效。

5. 那个程序员说他有1MB的可用存储空间，但是我们概要描述的代码需要1.25MB的空间。它可以不费力气地索取到额外的空间。如果1MB空间是严格边界，你会推荐如何处理呢？你的算法地运行时间又是多少？

6. 如果哪个程序员说的不是每个整数最多出现一次，而是每个整数最多出现10词，你又如何建议他呢？你的解决方案如何随着可用存储空间总量地变化而变化？

7. [R. Weil] 本书1.4节中面熟的程序存在一些缺陷。首先是假定输入中没有出现两次地整数，如果某个数出现超过一次的话，会发生什么？在这种情况下，如何修改程序来调用错误处理函数？当输入整数小于零或大于等于n时，又会发生什么？如果某个输入不是数值又如何？在这些情况下，程序该如何处理？程序还应该包含那些明智地检查？描述一些用以测试程序地小型数据集合，并说明如何正确处理上述及其他地不良情况。

8. 当那个程序员解决该问题的时候，美国所有地免费电话地区号都是800。现在免费电话的区号包括800、877和888，而且还在增多，如何在1MB空间内完成对所有这些免费电话号码的排序》如何将免费电话号码存储在一个一个集合中，要求可以实现非常快速的查找以判定一个给定的免费电话号码是否可用或者已经存在？

9. 使用更多的空间来换取更少的运行时间存在一个问题：初始化空间本身需要消耗大量的时间。说明如何设计一种技术，在第一次访问响亮的项时将其初始化为 0.你的方案应该使用常量时间进行初始化和向量访问，使用的额外空间应正比于向量的大小。因为该方法通过进一步增加空间来减少出场我的时间，所以仅在空间很廉价、时间很宝贵且向量很稀疏的情况下才考虑使用。

10. 在成本低廉的隔日送达时代之前，商店允许顾客通过电话订购商品，并在几天后上门自取。商店的数据库使用客户的电话号码作为其检索的主关键字（客户知道他们自己的电话号码而且这些关键字几乎都是唯一的）。你如何组织商店的数据库，以允许高效的插入和检索操作？

11. 在 20 世纪 80 年代早期，洛克希德公司加利福尼亚州桑尼维尔市工厂的工程师们每天都要将许多由计算机辅助设计（CAD）系统生成的图纸从工厂送到位于圣克鲁斯市的测试站。虽然仅有 40 公里远，但使用汽车快递服务（Services）每天都需要一个多小时的时间（由于交通阻塞和山路崎岖），花费 100 美元。请给出新的数据传输方案并估计每一种方案的费用。

12. 载人航天的先驱们很快就意识到在外太空的极端环境下实现顺利书写。民间盛传美国国家宇航局（NASA）花费 100 万美元研发出一种特殊的钢笔来解决这个问题。那么，前苏联又会如何解决相同的问题呢？

1.7 深入阅读

这个小问题仅仅是令人痴迷的程序说明问题的冰山一角。要深入研究这个重要的课题，参见 Michael Jackson 的 Software Requirements & Specifications 一书（Addison-Eesley 出版社 1995 年出版）。该书用一组独立成章却又相辅相成的短文，以令人愉悦的方式阐述了这个艰涩的课题。

在本章所描述的实例研究中，程序员的主要问题与其说是技术问题，还不如说是心理问题：他不能解决问题，是因为他企图解决错误的问题。问题的最终解决，是通过打破他的概念壁垒，进而去解决一个较简单的问题而实现的。 James L. Adams 所著的 Conceptuel Blockbusting 一书（第 3 版由 Perseus 出版社于 1986 年出版）研究了这类跳越，概述通常是触发创新性思维的理想选择。虽然该书不是专为程序员而写的，其中的许多内容却特别适用于编程问题。Adams 将概念壁垒定义为“阻碍解题者理解问题或者取得答案的心智壁垒”。习题 10、习题 11 和 习题 12 激励读者去打破一些这样的壁垒

Michael Jackson 软件工程先驱。他于 20 世纪 70 年代提出了影响深远的面向数据结构的 Jackson 方法

第二章 啊哈！算法

《啊哈！灵机一动》

数字排序

字符串位移

字符串匹配

二分搜索

——寻找数列中缺失的数字

（限制条件时内存较少，但是有文件可以使用）

众所周知，二分搜索程序要正确运行很困难。

（但事实上，内卷玩家，二分搜索都是小 case 了

二分搜索还可以用于别的方面，并不止局限于有序数列

第三章 数据决定数据结构

第四章 编写正确的程序

第五章 编程小事

第六章 程序性能分析

第七章 粗略估算

第八章 算法设计技术

第九章 代码调优

第十章 节省空间

第十一章 排序

第十二章 取样问题

第十三章 搜索

第十四章 堆

第十五章 字符串

中国

美国

世界

$$\begin{aligned}H{n}&=\frac{n}{\sum\limits{i=1}^{n}\frac{1}{x{i}}} \\ &= \frac{n}{\frac{1}{x{1}}+ \frac{1}{x{2}}+ \cdots + \frac{1}{x{n}}}G{n} \\ &=\sqrt[n]{\prod \limits{i=1}^{n}x{i}}= \sqrt[n]{x{1}x{2}\cdots x{n}}A{n} \\ &=\frac{1}{n}\sum \limits{i=1}^{n}x{i}=\frac{x{1}+ x{2}+ \cdots + x{n}}{n}Q{n} \\ &=\sqrt{\sum \limits{i=1}^{n}x{i}^{2}}= \sqrt{\frac{x{1}^{2}+ x{2}^{2}+ \cdots + x{n}^{2}}{n}}\end{aligned}$$

$$H{n}\leq G{n}\leq A{n}\leq Q{n}$$

https://www.jianshu.com/p/8d2d93c4229b

以后持续补充