详情
本书一共有10章。第1~7章分别就计数问题、信息查找问题、组合优化问题、图中搜索问题和数论问题展开算法的构思、设计和分析。第8章提供了10个让读者自解的计算问题，让读者有机会小试牛刀。第9-10章用书中给出的各问题的C++解决方案作为例子，书中一共收录了92个饶有兴趣的计算问题，每个问题都给出了完整的C++解决方案。
书名：趣题学算法
ISBN：978-7-115-44287-1
本书由人民邮电出版社发行数字版。版权所有，侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。
如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。
• 著 徐子珊
责任编辑 张 涛
• 人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
• 读者服务热线：(010)81055410
反盗版热线：(010)81055315
本书共分10章。第0章讲解了算法的概念及体例说明。第1～7章分别就计数问题、信息查找问题、组合优化问题、图中搜索问题和数论问题展开，讨论了算法的构思和设计，详尽介绍了解决这些问题的渐增策略、分治策略、回溯策略、动态规划和贪婪策略、广度优先搜索策略、深度优先搜索策略等。第8章提供了10个让读者自解的计算问题，让读者有机会小试牛刀。第9章用书中给出的各问题的C++解决方案作为例子，讨论了C++语言的强大编程功能。书中一共收录了92个饶有兴趣的计算问题，每个问题（包括第8章留给读者自解的题目）都给出了完整的C++解决方案。
本书适于作为程序员的参考书，高校各专业学生学习“数据结构”“算法设计分析”“程序设计”等课程的扩展读物，也可以作为上述课程的实验或课程设计的材料，还可以作为准备参加国内或国际程序设计赛事的读者的赛前训练材料。
念大学的时候曾经读过一本名字叫作Problem-Solving Through Problems（by Loren C. Larson 1983）的数学书，我对这本书的印象非常深刻。除了文字清新、易读易懂之外，这本书还让我明白了数学是学习科学、认识世界的有力工具，更重要的是它给了我一些很基本的也是应用极广的解决现实问题的数学方法和思想，例如，构造等价问题、绘制图形、利用对称性质、讨论限制条件、考虑极端情形等。直至今天，我还经常受惠于这些在我头脑中沉淀的思想。
Problem-Solving Through Problems之所以让读者感到易读易懂且印象深刻，应归功于它的一个写作特点，用今天的话来说就是“问题驱动”。它的每一章总是先提出一个引人入胜或有着广泛生活背景的问题，通过对问题的分析、理解引入相关的数学知识与解题思路，并用讨论得到的思想和方法解决一系列问题，使读者在阅读过程中产生兴趣，带动读者进行深入思考，通过解决问题激发读者进一步探索的好奇心及继续阅读的热情。
在机械和电子技术占主导地位的时代，数学思想扮演着科学与工程技术基石的角色。一本好的传播数学思想的书使学习科学与技术的年轻人受益终身。在信息时代，生活中几乎所有的活动都与计算有关。向朋友发的短信中的每个字符，行驶在高速路上的汽车中发动机的工作状态，载人航天器与空间站对接时连接口的接驳，都是某种计算的结果。计算有简单的也有复杂的。学习和掌握计算思想——集中体现在解决计算问题的算法及其计算机程序实现上——是现代人认识世界的最基本的也是最重要的思想工具。写一本问题驱动的算法、编程的书，为致力于学习信息技术的年轻朋友培养自身的计算思想素养助一臂之力，是我编著本书的动因。
本书将计算问题分成若干类，并对一类问题提出解决这类问题的若干经典算法思想，通过对若干个这类问题的算法设计与分析，与读者一起认识与体会这些经典算法设计的思想方法。第1～7章分别就计数问题、数据集合与信息查找、现实模拟、组合优化问题、动态规划与贪婪策略、图的搜索算法及数论问题展开讨论。每一类问题都是通过提出和解决十几个饶有兴趣的题目来展开的，对每一个题目均详尽地探讨了数据输入/输出的规范，以及解决一个测试案例的算法构思、算法描述和算法运行效率的分析。涉及的算法设计思想包括渐增策略、分治策略、回溯策略、动态规划、贪婪策略、深度与广度优先搜索等。
书中各章讨论、解决的问题很多有着实际的应用背景，例如问题1-7的糟糕的公交调度、问题2-9的通信系统、问题3-10的符号导数、问题5-5的人类基因功能、问题5-12的最短路及问题6-10的电网等。有一些问题则是计算机科学的基本问题的简化或雏形，例如问题2-10的计算机调度、问题3-8的内存分配、问题4-6的命题逻辑和问题5-2的形式语言等。还有一些问题则是当前一些热门课题的缩影，如问题3-5的稳定婚姻问题（实际上是经济理论中稳定匹配的简化模型）、问题4-4的一步致胜（棋类游戏的搜索算法）以及问题7-12的RSA因数分解（RSA密钥问题）等。通过对这些问题的研讨，读者能得到一些解决实际问题的灵感，在遇到计算机专业领域课题时会有某种亲切感，在科研领域中多一件计算思维工具。
计算机科学是教学理论与实践结合最紧密的学科。几乎所有的理论算法都可以立即在计算机上用程序加以验证。对书中的每一个计算问题，都给出了完整的C++解决方案，代码文件分别存储于各自的文件夹内。这些程序均在Microsoft Visual C++ 2010上调试通过。所有的代码和视频都放在百度空间中，下载地址为：http://pan.baidu.com/s/1c22U7PA。为防云盘可能受政策、服务变动等不可测因素的影响，各位可以到地址为https://github.com/xuzishan/Algorithm-learning-through-Problems/tree/master的github 仓库提取源代码。
书中各章内容相对独立，且按先易后难的顺序编排，即使在同一章内，题目也是按先易后难的顺序编排的，所以，对于算法和编程初入门的读者而言，可以先读懂前几章，每章中先读懂前3个题目，有了兴趣，再往后研读。喜欢追根溯源（笔者非常赞赏）的读者，如果对算法构思的理论背景在本书的文本介绍中仍感到不满足，可以在百度云中下载（地址同前）深入讨论相关课题的视频资料做进一步探究。对于高校相关课程的教师读者而言，第1～2章内容能满足程序设计课程的课程设计材料的需求，第2～3章的内容能满足数据结构课程实验材料需求，第4～5章适于算法设计与分析课程的基本实验材料需求，第6～7章可作为算法课程实验扩展材料。厨师都知道“众口难调”。笔者虽非厨师，但对此道理有着深切的体会，在写作中，尽量满足大家的需求。这本书若能让不同层次、不同需求的读者从中获得各自之需，实在是笔者的衷心所愿。“智者千虑，必有一失”，因而书中必会存留拙笔，望读者不吝赐教，让本书的后续版本不断完善。
笔者创建了读者QQ群“算法与程序”（210847302），欢迎加入参加讨论（新加入时请附言“读者”）。本书编辑联系和投稿邮箱为zhangtao@ptpress.com.cn。
徐子珊
记于依林书斋
0.1 App程序与算法
0.2 计算问题
0.3 算法的伪代码描述
0.4 算法的正确性
0.5 算法分析
0.6 算法运行时间的渐近表示
0.7 算法的程序实现
0.8 从这里开始
信息时代，人们时刻都在利用各种App解决生活、工作中的问题，或获取各种服务。早晨，手机里设定的闹钟铃声（或你喜欢的音乐）将你唤醒。来到餐厅，你用手中的IC卡到取餐处的刷卡机上支付美味早餐的费用。上班途中，打开手机上的音乐播放器，用美妙的乐声，打发掉挤在公交车上的乏味的时间。上班时，利用计算机中的各种办公软件处理繁忙的业务。闲暇时，你用平板电脑里的视频程序看一部热映的大片，或在淘宝网上选购你喜欢的宝贝。晚间，你用QQ或Facetime与远方的朋友聊天、交流情感……凡此种种，不一而是。
五彩缤纷的App后面是什么？这些神奇的体验是怎么创造出来的？如果你对这样的问题感兴趣的话，我们就成为朋友了。从这里开始，我们将探索创造App——计算机（及网络）应用程序的基本原理和基本技能。
其实，能用计算机（包括各种平板电脑、智能手机）解决的是所谓的“计算问题”，也就是有明确的输入与输出数据的问题。解决计算问题就是用一系列基本的数据操作（算术运算、逻辑运算、数据存储等）将输入数据转换成正确的输出数据。能达到这一目标的操作序列称为解决这一计算问题的“算法”。App就是在一定的计算机平台（计算机设备及其配备的操作系统）上，用这个计算机系统能识别的语言来实现算法的程序。
因此，对上述的第一个问题，我们的答案是：App背后的是算法。算法是解决计算问题的方案。要用计算机来解决应用问题，首先要能将该问题描述成计算问题——即明确该问题的输入与输出数据。只有正确、明白地描述出计算问题，才有可能给出解决该问题的算法。作为起点，本书并不着眼于如何将一个实际的应用形式化地描述为一个计算问题，而是向你描述一些有趣的计算问题，并研究、讨论如何正确、有效地解决这些问题。通过对这些问题的解决，使我们对日常面对的那些App有着更清醒、更理智的认识。可能的话，也许哪一天你也能为你自己，或者朋友、爱人创造出你和他们喜欢的App。
上面已经说到什么是计算问题，下面就来看一个有趣的计算问题。
问题描述
这个学期Amy开始学习一门重要课程——线性代数。学到行列式的时候，每次遇到对给定的序列计算其逆序数，她都觉得是个很闹心的事。所以，她央求她的好朋友Ray为她写一段程序，用来解决这样的问题。作为回报，她答应在周末舞会上让Ray成为她的伦巴舞舞伴。所谓序列A的逆序数，指的是序列中满足i<j，A[i]>A[j]的所有二元组<i, j>的个数。
输入
输入文件包含若干个测试案例。每个案例的第一行仅含一个表示序列中元素个数的整数N（1
N500000）。第二行含有N个用空格隔开的整数，表示序列中的N个元素。每个元素的值不超过1 000 000 000。N=0是输入数据结束的标志。
输出
每个案例仅输出一行，其中只有一个表示给定序列的逆序数整数。
输入样例
3☐
1 2 3
2
2 1
0输出样例
0
1这是本书要讨论，研究的一个典型的计算问题。理解问题是解决问题的最基本的要求，理解计算问题要抓住三个要素：输入、输出和两者的逻辑关系。这三个要素中，输入、输出数据虽然是问题本身明确给定的，如果输入包含若干个案例则要理清每个案例的数据构成。
例如，问题0-1的输入文件inputdata（本书所有计算问题的输入假设均存于文件中，统一记为inputdata）中含有若干个测试案例，每个案例有两行输入数据。第1行中的一个整数N表示案例中给定序列的元素个数。第二行含有表示序列中N个元素的N个整数。当读取到的N=0时意味着输入结束。
所谓输入、输出数据之间的逻辑关系，实质上指的是一个测试案例的输入、输出数据之间的对应关系。为把握这一关系，往往需要认真、仔细地阅读题面，在欣赏题面阐述的故事背景之余，应琢磨、玩味其中所交代的反应事物特征属性的数据意义，以及由事物变化、发展所引发的数据变化规律，由此理顺各数据间的关系，这是设计解决问题的算法的关键所在。
例如，如果我们把问题0-1的一个案例的输入数据组织成一个数组A[1..N]，我们就要计算出序列中使得i<j，A[i]>A[j]成立的所有二元组<i, j>，统计出这些二元组的数目，作为该案例的输出数据加以输出——作为一行写入输出文件outputdata（本书所有计算问题的输出假设均存于文件中，统一记为outputdata）。
对问题有了正确的理解之后，就需要根据数据间的逻辑关系，找出如何将输入数据对应为正确的输出数据的转换过程。这个过程就是通常所称的“算法”。通俗地说，算法就是计算问题的解决之道。
例如，对问题0-1的一个案例数据A[1..N]，为计算出它的逆序数，我们设置一个计数器变量count（初始化为0）。从j=N，A[j]开始，依次计算各元素与其前面的元素（A[1..j−1]）构成的逆序个数，累加到count中。当j<2时，结束计算返回count即为所求。
上一节最后一段使用自然语言（汉语）描述了解决“计算逆序数”问题的算法。即如何将输入数据转换为输出数据的过程。在需要解决的问题很简单的情况下（例如“计算逆序数”问题），用自然语言描述解决这个问题的算法是不错的选择。但是，自然语言有一个重要特色——语义二岐性。语义二岐性在文学艺术方面有着非凡的作用：正话反说、双关语……。由此引起的误会、感情冲突……带给我们多少故事、小说、戏剧……。但是，在算法描述方面，语义二岐性却是我们必须避免的。因为，如果对数据的某一处理操作的表述上有二岐性，会使不同的读者做出不同的操作。对同一输入，两个貌似相同的算法的运行，将可能得出不同的结果。这样的情况对问题的解决可能是灾难性的。所以，自然语言不是最好的描述算法的工具。
在计算机上，算法过程是由一系列有序的基本操作描述的。不同的计算机系统，同样的操作，指令的表达形式不必相同。本书并不针对特殊的计算机平台描述解决计算问题的算法，我们需要一个通用的、简洁的形式描述算法，并且能方便地转换成各种计算机系统上特殊表达形式（计算机程序设计语言）所描述的程序。描述算法的通用工具之一叫伪代码。例如，解决上述问题数据输入/输出的伪代码过程可描述如下。
1 打开输入文件inputdata
2 创建输出文件outputdata
3 从inputdata中读取案例数据N
4 while N>0
5 do 创建数组A[1..N]
6 for i←1 to N
7 do 从inputdata中读取A[i]
8 result←GET-THE-INVERSION(A)
9 将result作为一行写入outputdata
10 从inputdata中读取案例数据N
11 关闭inputdata
12 关闭outputdata
其中，第8行调用计算序列A[1..N]的逆序数过程GET-THE-INVERSION(A)是解决一个案例的关键，其伪代码过程如下。
GET-THE-INVERSION(A) ▷A[1..N]表示一个序列
1 N←length[A]
2 count←0
3 for j←N downto 2
4 do for i←1 to j-1
5 do if A[i]>A[j] ▷检测到一个逆序
6 then count←count+1 ▷累加到计数器
7 return count
算法0-1 解决“计算逆序数”问题的一个案例的算法伪代码过程
伪代码是一种有着类似于程序设计语言的严格外部语法（用if-then-else表示分支结构，用for-do、while-do或repeat-until表示循环结构），且有着内部宽松的数学语言表述方式的代码表示方法。它既没有二歧性的缺陷（严格的外部语法），又能用高度抽象的数学语言简练地描述操作细节。
本书所使用的伪代码书写规则如下。
① 用分层缩进来指示块结构。例如，从第3行开始的for循环的循环体由第4～6行的3行组成，分层缩进风格也应用于if-then-else语句，如第5～6行的if-then语句。
② 对for循环，循环计数器在退出循环后仍然保留。因此，一个for循环刚结束时，循环计数器的值首次超过for循环上界。例如在算法0-1中，当第3～6行的for循环结束时，j = N+1；而第4～6行的for循环结束时，i=1−1=0。
③ 符号“ ▷”表示本行的注释部分。例如，算法0-1的开头对参数A的意义进行了解释，第5行说明检测到一个逆序（i<j，A[i]>A[j]），而第6行说明将此逆序累加到逆序数count（count自增1）。
④ 多重赋值形式i ← j← e对变量i和j同赋予表达式e的值；它应当被理解为在赋值操作j ← e之后紧接着赋值操作i ← j。
⑤ 变量（如i，j，及count）都局部于给定的过程。除非特别需求，我们将避免使用全局变量。
⑥ 数组元素是通过数组名后跟括在方括号内的下标来访问。例如，A[i]表示数组A的第i个元素。记号“…”用来表示数组中取值的范围。因此，A[1…i]表示数组A的取值由A[1]到A[i]，i个元素构成的子序列。
⑦ 组合数据通常组织在对象中，其中组合了若干个属性。用域名[对象名]的形式来访问一个具体的域。例如，我们把一个数组A当成一个对象，它具有说明其所包含的元素个数的属性length。为访问数组A的元素个数，我们写length[A]。
表示数组或对象的变量被当成一个指向表示数组或对象的指针。对一个对象x的所有域f，设y ← x将导致f[y] = f[x]。此外，若设f[x]← 3，则不仅有f[x] = 3，且有f[y] = 3。换句话说，赋值y ← x后，x和y指向同一个对象。
有时，一个指针不指向任何对象，此时，我们给它一个特殊的值NIL。
⑧ 过程的参数是按值传递的：被调用的过程以复制的方式接收参数，若对参数赋值，则主调过程不能看到这一变化。
⑨ 布尔运算符“and”和“or”都是短回路的。也就是说，当我们计算表达式“x and y”时，先计算x。若x为FALSE，则整个表达式不可能为TRUE，所以我们不再计算y。另一方面，若x为TRUE，我们必须计算y以确定整个表达式的值。相仿地，在表达式“x or y”中，我们计算表达式y当且仅当x为FALSE。短回路操作符使得我们能够写出诸如“x ≠ NIL and f [x] = y”这样的布尔表达式而不必担心当x为NIL时去计算f [x]。
解决一个计算问题的算法是正确的，指的是对问题中任意合法的输入均应得到对应的正确输出。大多数情况下，问题的合法输入无法穷尽，当然就无法穷尽输出是否正确的验证。即使合法输入是有限的，穷尽所有输出正确的验证，在实践中也许是得不偿失的。但是，无论如何，我们需要保证设计出来的算法的正确性。否则，算法设计就是去了它的应用意义。因此，对设计出来的算法在提交应用之前，应当说明它的正确性。这就需要借助我们对问题的认识与理解，利用数学、科学及逻辑推理来证实算法是正确的。例如，对于解决“计算逆序数”问题的算法0-1，其正确性可以表述为如下命题：
当第3～7行的for循环结束时，count已记录下了序列A[1..N]中的逆序数。
如果我们能说明上述命题是真的，那就说明了算法0-1是正确的。由于数组A[1..N]的长度N是任意正整数，所以这是一个与正整数相关的命题。数学中要证明一个与正整数相关的命题有一个有力的工具——数学归纳法。下面我们对本命题中的N进行归纳。
当N=1时第3～7行的for循环重复0次。count保持初始值0，这与A[1..N]=A[1]没有任何逆序相符，结论显然为真。
设N>1且可用算法计算出A[1..N−1]的逆序数count。在此假设下，我们来证明对A[1..N]利用算法0-1也能得到正确的逆序数count。
考虑算法中第3～7行的for循环在j=N时的第一次重复的操作：第4～6行内嵌的for循环从i=1开始到j−1为止，逐一检测是否A[i]>A[j]。若是，意味着找到一个关于A[N]的逆序，第6行count自增1。当此循环结束时count中累积了关于A[N]的逆序数。由于N>1，故第3～6行的外围for循环必定会继续对A[1..N−1]做同样的操作。根据归纳假设，我们知道第3～6行的for循环接下来的重复操作能将A[1..N−1]中个元素的逆序数累加到count中。所以第3～6行for循环结束时，count已记录下了序列A[1..N]中的逆序数。
这样，我们就从逻辑上证明了算法0-1能正确地解决“计算逆序数”问题的一个案例，即算法0-1是正确的。
应当指出，解决一个计算问题时，算法不必唯一。数据的组织方式、解题思路的不同，会导致不同的算法。
例如，将计数器count设置为全局变量，并初始化为0。解决“计算逆序数”问题一个案例的算法还可以表示为如下的形式。
GET-THE-INVERSION(A, N) ▷A[1..N]表示一个序列
1 if N<2
2 then return
3 for i←1 to N-1
4 do if A[i]>A[N] ▷检测到一个逆序
5 then count←count+1 ▷累加到计数器
6 GET-THE-INVERSION(A, N-1)
算法0-2 解决“计算逆序数”问题一个案例的递归算法伪代码过程
这是一个“递归”算法，它在定义的内部（第6行）进行了一次自我调用。受上述算法0-1正确性命题证明的启发，这个算法的思想是基于先计算出A[1..N-1]中关于A[N]的逆序数count，然后将问题归结为计算A[1..N-1]的逆序数的子问题。用相同的方法解决子问题（递归调用自身，注意表示A的长度的第2个参数变成N-1）把子问题的解与count合并就可得到原问题的解。其实，算法0-2与算法0-1仅仅是表达形式不同，本质上等价的：后者用末尾递归（第6行递归调用自身）隐式地替代算法0-1中第3～6行的外层for循环。所以，算法0-2也是正确的。
解决同一问题的不同算法所消耗的计算机系统的时间（占用处理器的时间）和空间（占用内部存储器空间）资源量可能有所不同。算法运行所需要的资源量称为算法的复杂性。一般来说，解决同一问题的算法，需要的资源量越少，我们认为越优秀。计算算法运行所需资源量的过程称为算法复杂性分析，简称为算法分析。理论上，算法分析既要计算算法的时间复杂性，也要计算它的空间复杂性。然而，算法的运行时间都是消耗在已存储的数据处理上的，从这个意义上说，算法的空间复杂性不会超过时间复杂性。出于这个原因，人们多关注于算法的时间复杂性分析。本书中除非特别说明，所说的算法分析，局限于对算法的时间复杂性分析。
算法的运行时间，就是执行基本操作的次数。所谓基本操作，指的是计算机能直接执行的最简单的不可再分的操作。例如对数据进行的算术运算和逻辑运算，以及将数据存储于内存的某个单元。考虑算法0-1，当序列A的元素个数为N时：
GET-THE-INVERSION(A)
1 N← length[A] 耗时1个单位
2 count←0 耗时1个单位
3 for j← N downt o 2 耗时N个单位
4 do for i←1 to j-1 耗时
=N(N+1)/2-1个单位
5 do if A[i]>A[j] 耗时
=N(N+1)/2个单位
6 then count←count+1 耗时不超过=N(N+1)/2个单位
7 return count +） 耗时1个单位
3N2/2+N/2+2
具体地说，第1、2、7行各消耗1个单位时间，总数为3，第3行做N次j与2的比较耗时N，第4行作为外层循环的循环体中一个操作，每次被执行时做j次i与j−1的比较，所以总耗时为N+(N−1)+…+2=N(N+1)/2-1。相仿地，第5、6行作为内层循环的循环体每次被重复j−1次，但它们也在外层循环的控制之下，所以两者的耗时为2(1+ 2+…+N−1)=N(N−1)。把它们相加得到
N+3+N(N+1)/2-1+N(N-1)
=N+2+N2/2+N/2+N2-N
=3N2/2+N/2+2
一般而言，算法的时间复杂性与输入的规模（算法0-1中序列A的元素个数）相关。规模越大，需要执行的基本操作就越多，当然运行时间就越长。此外，即使问题输入的规模一定，不同的输入也会导致运行时间的不同。对固定的输入规模，使得运算时间最长的输入所消耗的运行时间称为算法的最坏情形时间。通常，人们以算法的最坏情形时间来衡量算法的时间复杂性，并简称为算法的运行时间。例如，在上述的算法0-1的分析中，第3～6行的嵌套循环的循环体的每次重复，第6行并非必被执行，所以我们说其耗时“不超过=N(N+1)/2个单位”。但我们要考虑的是最坏情形时间，所以运行时间是按N(N+1)/2加以计算的。
对于算法的输入规模为n的运行时间，常记为T(n)。以算法0-1的GET-THE- INVERSION(A)过程为例，数组A[1..N]的元素个数N越大，运行时间T(N)=3N2/2+N/2+2的值就越大。
对算法0-2而言，设其对输入规模为N的运行时间为T(N)。
GET-THE-INVERSION(A, N)
1 if N<2 耗时1个单位
2 then return 耗时不超过1个单位
3 for i←1 to N-1 耗时N个单位
4 do if A[i]>A[N] 耗时N-1个单位
5 then count←count+1 耗时不超过N-1个单位
6 GET-THE-INVERSION(A, N-1) +） 耗时T(N-1)
T(N)=T(N−1)+3N-1
这是一个在等式两端都含有未知式T的方程，称为递归方程。递归方程可以用迭代法来解，即
T(N)=T(N-1)+3N-1
=T(N-2)+3(N-1)+3N-2
=T(N-3)+3(N-2)+3(N-1)+3N-3
……
=T(1)+3*2+…+3(N-1)+3N-(N-1)
=2+3(1+2+3+…+N)-3-N+1
=3N(N+1)/2-N
=3N2/2+N/2
显然，这算法0-1的运行时间大同小异。注意，式中的T(1)指的是算法0-2的第2个参数N=1时的运行时间。显然，这将仅执行其中1～2行的操作，耗时为2个单位。
由于计算机技术不断地扩张其应用领域，所要解决的问题输入规模也越来越大，所以对固定的n来计算T(n)的意义并不大，我们更倾向于评估当n→∞时T(n)趋于无穷大的快慢，并以此来分析算法的时间复杂性。我们往往用几个定义在自然数集N上的正值函数Ỹ(n)：幂函数nk（k为正整数），对数幂函数lgkn（k为正整数，底数为2）和指数函数an（a为大于1的常数）作为“标准”，研究极限
（0-1）
若λ为一正常数，我们称Ỹ(n)是T(n)的渐近表达式，或称T(n)渐近等于Ỹ(n)，记为T(n)=Θ(Ỹ(n))，这个记号称为算法运行时间的渐近Θ-记号，简称为Θ-记号。例如，算法0-1的运行时间为T(n)=2n2+4n+3，取Ỹ(n)=n2，由于
所以，我们有T(n)=Θ(n2)，即此T(n)渐近等于n2。其实，在一个算法的运行时间T(n)中省略最高次项以外的所有项，且忽略最高次项的常数系数，就可得到它的渐近表达式。例如，用此方法也能得到算法0-1的运行时间T(N)=3N2/2+N/2+2=Θ(N2)，算法0-2的运行时间T(N)= 3N2/2+N/2=Θ(N2)。在这个意义上，我们可以再次断言——算法0-1和算法0-2是等价的。
如果两个算法的运行时间的渐近表达式相同，则将它们视为具有相同的时间复杂度的算法。显然，渐近时间为对数幂的算法优于渐近时间为幂函数的算法，而渐近时间为幂函数的算法则优于渐近时间为指数函数的算法。我们把渐近时间为幂函数的算法称为具有多项式时间的算法。渐近时间不超过多项式的算法我们称其为有效的算法。通常认为运行时间为指数式的算法不是有效的。
渐近记号除了Θ外，还有两个常用的记号O和Ω。它们的粗略意义如下：
考察定义域为自然数集N的正值函数Ỹ(n)和T(n)构成的极限式0-1的值λ，若λ1为一常数，则称函数T(n)渐近不超过函数Ỹ(n)，记为T(n) = O (Ỹ(n))；若λ>1为常数或为+∞，则称函数T(n)渐近不小于函数Ỹ(n)，记为T(n)= Ω(Ỹ(n))。例如lgkn=O(nk)，反之，lgkn=Ω(nk)。显然，T(n)=Θ(Ỹ(n))当且仅当T(n) = O (Ỹ(n))且T(n)= Ω(Ỹ(n))。对算法运行时间的深入讨论读者可参考配书的短视频“算法的运行时间”。
下面我们用以上讨论过的概念、术语、记号和方法再讨论一个计算问题。
问题描述
假定在坦佩雷〔芬兰城市〕地区的第四代移动电话基站如下述方式运行。该地区划分成很多四方块，这些四方形的小区域形成了S×S矩阵。该矩阵的行、列均从0开始编码至S-1。每个方块区域包含一个基站。方块内活动的手机数量是会发生变化的，因为手机用户可能从一个方块区域进入到另一个方块区域，也有手机用户开机或关机。每个基站会报告所在区域内手机活动数的变化。
写一个程序，接收这些基站发来的报告，并应答关于指定矩形区域内的活动手机数的查询。
输入
输入从标准输入设备中读取表示查询的整数并向标准输出设备写入整数以应答查询。输入数据的格式如下。每一行输入数据包含一个表示指令编号的整数及一些表示该指令的参数。指令编号及对应参数的意义如下表所示。
| 指令编号 |
参数 |
意义 |
|---|---|---|
| 0 |
S |
创建一个的S×S矩阵并初始化为0。该指令仅发送一次，且总是为第一条指令 |
| 1 |
X Y A |
区域（X, Y）增加A个活动手机 |
| 2 |
L B R T |
查询所有方块区域（X, Y）内活动手机数量之和。其中，L |
| 3 |
|
终止程序。该指令也仅发送一次，且必为最后一条指令 |
假定输入中的各整数值总是在合法范围内，无需对它们进行检验。具体说，例如A是一个负数，它不可能将某一方块区域中的手机数减小到0以下。下标都是从0开始的，即若矩阵规模为4×4，必有0X3且0 Y3。
我们假定：
矩阵规模：1×1S×S1024×1024。
任何时候方块区域内的活动手机数：0V32767。
修改值：−32768A32767。
不存在指令号：3U60002。
整个区域内的最大活动手机数：M= 230。
输出
你的程序对除了编号为2以外的指令无需做任何应答。若指令编号为2，程序须向标准输出设备写入一行应答的答案。
输入样例
0 4
1 1 2 3
2 0 0 2 2
1 1 1 2
1 1 2 -1
2 1 1 2 3
3输出样例
3
4解题思路
（1）数据的输入与输出
根据输入文件的格式，测试案例由若干条指令组成，每条指令占1行。依次读取各条指令存放于数组cmds中。指令3为结束标志。对指令序列cmds逐一执行，对指令2保存执行结果于数组result中。所有指令执行完毕后，将result中的数据逐行输出到输出文件。
1 打开输入文件inputdata
2 创建输出文件outputdata
3 创建指令序列cmds←Ø
4 从inputdata中读取案例数据cmd
5 while cmd≠3
6 do if cmd=0
7 then 从inputdata中读取S
8 INSERT(cmds, (cmd, S))
9 else if cmd=1
10 then 从inputdata中读取X, Y, A
11 INSERT(cmds, (cmd, X, Y, A))
12 else 从inputdata中读取L, B, R, T
13 INSERT(cmds, (cmd, L, B, R, T))
14 从inputdata中读取cmd
15 result←MOBIL-PHONE(cmds)
16 for each rresult
17 do 将r作为一行写入outputdata
18 关闭inputdata
19 关闭outputdata
其中，第15行调用计算指令序列cmds显示结果的过程MOBIL-PHONE(cmds)是解决一个案例的关键。
（2）解决一个案例的算法过程
首先创建数组result用来存储查询指令（指令2）的执行结果。cmds[1]是指令0，它的参数s决定了坦佩雷地区移动通信网的规模。用S创建一个二维数组tampere[0..S-1, 0..S-1]，并将所有元素初始化为0。从i=2开始逐一执行指令cmds[i]。若cmds[i]是指令1，则用其参数x, y, a在tampere[x][y]累加a。若cmds[i]是指令2，则在其参数l，b，r，t指定的（l, b）为左下角，（r, t）为右上角的范围内计算移动电话的数量，将计算结果加入数组result中。所有指令执行完毕后，返回result。
MOBIL-PHONE(cmds)
1 n←length[cmds]
2 析取指令cmds[1]的参数S
3 创建二维数组tampere[0..S-1, 0..S-1]并将元素初始化为0
4 创建数组result←Ø
5 for k←2 to n
6 do 从cmds[k]中析取cmd
7 if cmd=1
8 then 从cmds[k]中析取参数X, Y, A
9 tampere[X][Y] ← tampere[X][Y]+A
10 if tampere[X][Y]<0
11 then tampere[X][Y]=0
12 else从cmds[k]中析取参数L, B, R, T
13 count←0
14 for i←L to R
15 do for j←B to T
16 do count←count+tampere[i][j]
17 INSERT(result, count)
18 return result
算法0-3 解决“移动电话”问题的算法过程
这个算法的代码结构类似于算法0-1，算法的结构主体是嵌套在一起的若干个循环。由于我们用渐近表达式表示算法的运行时间，所以对这种结构的算法，在算法分析时循环之外常数时间完成的操作可以不予考虑。例如，本算法中第1～4行及第18行的操作，分析时可忽略。我们把目光聚焦于第5～17行的for循环。这个循环共重复Θ(n)（准确地说是n−1，但作为渐近式与n等价）次。循环体中是一个分支结构，分支之一是处理指令1的第8～11行操作，耗时为常数Θ(1)（准确地说是4，渐进等价于1）。另一分支是处理指令2的第12～17行，该分支中，除了第12、13、17行的常数时间操作外（第17行是在数组result的尾部添加新的元素，耗时亦为Θ(1)），第14～16行是一个两重嵌套for循环。这两重循环分别重复r-l和t-b次。循环体内的操作耗时Θ(1)（1次赋值操作）。所以这两重循环的耗时为Θ((R-L)(T-B))。这个结果看起来似乎很精致，但实际上我们并不知道L，B，R，T的具体值，但我们知道0L，B，R，TS。也就是说必有0R-L, T-BS。因此，用渐近表达式我们可以将这个嵌套循环的耗时记为O(S2)（意味着耗时不差过S2）。再由于它内嵌于第5～17行的最外层for循环之内，若n条指令中指令2数目m占有一定比例（即存在常数c使得n=cm）则第12～17行的操作耗时可表为O(nS2)。于是，我们得出算法0-3的运行时间为O(nS2)。
有了解决问题的正确算法，就可以利用一种计算机程序设计语言将算法实现为可在计算机上运行的程序。本书选用业界使用最广泛、最成熟的C++语言来实现解决每一个问题的算法。C++语言是面向对象的程序设计语言，它为程序员提供了一个庞大的标准库。有趣的是，C++脱胎于C语言。所以，读者若具有C语言某种程度的训练，对于理解本书提供的C++代码一定是大有裨益的。闲话少说，让我们先来一睹C++语言程序的“芳容”吧。
解决问题0-1“计算逆序数”的C++程序如下。
1 #include <fstream>
2 #include <iostream>
3 #include <vector>
4 using namespace std;
5 int getTheInversion(vector<int> A){
6 int N=int(A.size());
7 int count=0;
8 for (int j=N-1; j>0; j--)
9 for (int i=0; i<j; i++)
10 if(A[i]>A[j])
11 count++;
12 return count;
13 }
14 int main(){
15 ifstream inputdata("Get The Inversion/inputdata.txt");//输入文件流对象
16 ofstream outputdata("Get The Inversion/outputdata.txt");//输出文件流对象
17 int N=0;
18 inputdata>>N;
19 while (N>0) {
20 vector<int> A(N);
21 for (int i=0; i<N; i++)
22 inputdata>>A[i];
23 int result=getTheInversion(A);
24 cout<<result<<endl;
25 outputdata<<result<<endl;
26 inputdata>>N;
27 }
28 inputdata.close();
29 outputdata.close();
30 return 0;
31 }
程序0-1 实现解决“计算逆序数”问题算法的C++程序
关于C++语言的各种细节（语言基础、支持语言的库、运用语言的各种技术等），我们将在本书的第9章，通过实现本书中算法的实际代码展开讨论。此处，我们仅仅借程序0-1做一个初步的认识。
我们可以把程序分成三部分观察。第一部分就是程序中的第1～4行，执行预编译指令。第二部分是第5～13行的函数getTheInversion定义。第三部分是第14～31行，程序的主函数。下面我们就这三个部分逐一加以简单说明。
① #include指令用来为程序引入“库”——包含各种已定义的数据类型、类、函数等，实现优质代码的重用，以提高程序设计的工作效率和程序的质量——搭建一座方便之桥。由于C++中任何运算成分（类型、变量、常量、函数……）均需先声明、后使用，所以头文件中就声明了一组程序所需的具有特殊意义的运算成分。用include指令将指定的头文件加载进来，程序员就可以方便地访问这些成分了。此处，首行指令#include <fstream>意味着本程序可以使用系统提供的文件输入输出流类的对象，方便地输入、输出数据。本书中所有算法的实现代码涉及输入输出的操作都需要进行文件的读写操作，所以这条指令将出现在每一个程序文件的首要位置。后面的两条分别引入控制台输入输出对象（cin、cout）和向量类（vector，这是C++标准模板库STL提供的可变长数组类模板）。这些类、对象的引入给大家带来了极大的方便。语句using namespace std（语句以分号结尾）指出，以上引入的类或对象都是标准库中的，可按名称直接访问。
② 细心的读者可能已经发现，第5～13行定义的函数int getTheInversion(vector<int> A)就是对算法0-1中伪代码过程GET-THE-INVERSION(A)的实现。除了某些细节，程序代码与伪代码几乎是一样的。如果你也有这样的感觉，我们就有了一种默契：只要有了伪代码，我们就能很快地写出它的实现程序——算法伪代码就是程序开发的“施工蓝图”。
③ 第14～31行定义的main函数也就是我们在算法0-1之前描述的“计算逆序数”问题数据的输入与输出的伪代码的实现。如果了解到“>>”和“<<”是C++数据流（文本文件就是一个数据流）的输出、输入操作符，则会感觉到这段代码几乎就是伪代码的翻版。
程序0-1存储为文件夹Get The Inversion的文件Get The Inversion.cpp。读者要在计算机上运行这个程序，需要在你的计算机上安装一个C++开发软件（譬如，在PC上安装一个Visual C++软件，在iMac上安装一个Xcode），然后创建一个项目，在其中加载文件laboratory/Get The Inversion/Get The Inversion.cpp。
同样，解决问题0-2“移动电话”的C++程序是存于文件夹laboratory/Mobil Phone中的文件Mobil Phone.cpp。
作为本书讨论的起点，本章通过解决一个典型的计算问题“计算逆序数”，明确了诸如算法、伪代码、算法分析、C++程序等概念、术语或名称。通过讨论问题“移动电话”给出了本书每个问题讨论的体例：描述问题——理解问题——设计算法——分析算法的效率。
如果你是一位编程初学者，在看了这两个例子后是否会有这样的问题：怎么会想到这样解这些问题？其实，这和你在学校里学习数学时解应用题很相像。首先，看看题目是归类于代数、几何还是微积分？如果是代数题，再看是用解方程方法还是用计算的方法？本书以后的六章将常见的计算问题分成计数问题、集合与查找问题、简单模拟问题、组合问题、组合优化问题和图的搜索问题，针对每一类问题深入讨论了各种问题的思路、方法和技术。所有这些，都是通过一个个有趣的计算问题的解答而展开的。本书的第8章还为喜欢独立思考的读者提供了几个待解的计算问题，读者可试着用前几章讨论过的方法解决这些问题，说不定会给你带来别样的快乐体验。第9章就本书所解决的诸多问题的程序代码，与读者分享了用C++编程的乐趣。相信读者掩卷之时，必会对算法设计、程序运行等现代人应具有的计算思想有所认识，对解决这类问题的思路有所启发，这恰是笔者写这本书的愿望。
准备好了，我们就从这里开始吧。
1.1 累积计数法
1.2 简单的数学计算
1.3 加法原理和乘法原理
1.4 图的性质
1.5 置换与轮换
人类的智力启蒙发端于计数。原始人在狩猎过程中为计数猎获物，手指、结绳等都是曾经使用过的计数工具。今天，我们所面对、思考的问题更加复杂、庞大，计数的任务需要强大的计算机来帮助我们完成。事实上，很多计算问题本身就是计数问题。
这样的问题在实际中往往要通过几个步骤来解决，每个步骤都会产生部分数据，问题的目标是计算出所有步骤产生数据的总和。对这样的问题通常设置一个计数器（变量），然后依步骤（往往可以通过循环实现各步骤的操作）将部分数据累加到计数器，最终得到数据总和。
问题描述
国王用金币赏赐忠于他的骑士。骑士在就职的第一天得到一枚金币。接下来的两天（第二天和第三天）每天得到两枚金币。接下来的三天（第四、五、六天）每天得到三枚金币。接下来的四天（第七、八、九、十天）每天得到四枚金币。这样的赏赐形式一直延续：即连续N天骑士每天都得到N枚金币后，连续N+1天每天都将得到N+1枚金币，其中N为任一正整数。
编写一个程序，对给定的天数计算出骑士得到的金币总数（从任职的第一天开始）。
输入
输入文件至少包含一行，至多包含21行。输入中的每一行（除最后一行）表示一个测试案例，其中仅含一个表示天数的正整数。天数的取值范围为1～10000。输入的最后一行仅含整数0，表示输入的结束。
输出
对输入中的每一个测试案例，恰好输出一行数据。其中包含两个用空格隔开的正整数，前者表示案例中的天数，后者表示骑士从第一天到指定的天数所得到的金币总数。
输入样例
10
6
7
11
15
16
100
10000
1000
21
22
0输出样例
10 30
6 14
7 18
11 35
15 55
16 61
100 945
10000 942820
1000 29820
21 91
22 98解题思路
（1）数据的输入与输出
根据题面对输入数据格式的描述，我们知道输入文件中包含多个测试案例，每个测试案例的数据仅占一行，且仅含一个表示骑士任职天数的正整数N。N=0是输入结束标志。对于每个案例，计算所得结果为国王赐予骑士的金币数，作为一行输出到文件。按此描述，我们可以用下列过程来读取数据，处理后输出数据。
1 打开输入文件inputdata
2 创建输出文件outputdata
3 从inputdata中读取案例数据N
4 while N>0
5 do result←GOLDEN-COINS(N)
6 将"N result"作为一行写入outputdata
7 从inputdata中读取案例数据N
8 关闭inputdata
9 关闭outpudata
其中，第5行调用计算骑士执勤N天能得到金币数的过程GOLDEN-COINS(N)是解决一个案例的关键。
（2）处理一个案例的算法过程
问题中的一个案例，是典型的累积计数问题。如果测试案例给出的天数N 存在k，使得和数
恰为N，则骑士第N天总计所得金币数为
。例如题面中的第一个测试案例N=10(=1+2+3+4)就是这样的情形，所得金币数为12+22+32+42=30。一般地，有N=+j，其中0jk 。此时，只要计算出j，骑士所得金币就应是+(k+1)×j。例如，题面的第三个测试案例中的7=(1+2+3)+1，所得金币数为12+22+32+4×1=18。金币数中的部分显然可以用循环累加而得（同时跟踪天数）。由于计算金币数中部分时所跟踪的天数N，所以，N-就是N=+j中的j。这样，我们就可以将问题分成k个阶段，每个阶段的部分金币数为i2（1ik），必要时（N>）还有一个步骤。此时，设j=N−，这一步骤中所得金币数应为j(k+1)。将每一步骤中所得的部分金币数累加即为所求，可将其描述成如下伪代码过程。
GOLDEN-COINS(N)
1 coins←0, k←1, days←0
2 while days+k
N
3 do coins←coins+k*k ▷coins=
4 days←days+k ▷days=
5 k←k+1
6 j←N-days ▷计算N=+j中的j
7 coins←coins+k*j
8 return coins
算法1-1 对已知的天数N，计算从第1天到第N天总共所得金币数的过程
算法1-1中设置了两个计数器days和coins，分别表示骑士工作的天数和所得的金币数（在第1行初始化为0）。k是循环控制变量，第2～5行的while循环即实现coins的k步累加。第6～7行完成可能发生的第k+1（N>时）步计算。
算法中第1、6、7、8行所需都是常数时间，分别为3、2、3和1。第2～5行的while循环至多重复
次（这是因为1+2+…+kN当且仅当k2+k2N，当且仅当k<），每次重复，循环体中的操作耗时为常数时间Θ(1)，因此该循环的运行时间为O()。所以，GOLDEN-COINS过程的运行时间[1]为T(N)=9+。利用运行时间的渐近表示方式[2]，省略低次项，T(N)为O()。其实，如在第0章中分析算法0-2那样，为了得到一个算法的运行时间的渐近表达式，可以忽略常数时间的操作，而着眼于诸如循环或过程调用这样的操作的耗时。例如，本算法中，忽略第1、6、7、8行操作的耗时，由于第2～5行的while循环耗时，所以算法的运行时间为O()。
解决本问题的算法的C++实现代码存储于文件夹laboratory/Golden Coins中，读者可打开文件GoldenCoins.cpp研读，并试运行之。
问题描述
你能将一摞扑克牌在桌边悬挂多远？若有一张牌，你最多能将它的一半悬挂于桌边。若有两张牌，最上面的那张最多有一半伸出下面的那张牌，而底下的那块牌最多伸出桌面三分之一。因此两张牌悬挂于桌边的总长度为1/2 + 1/3 = 5/6。一般地，对n张牌伸出桌面的长度为1/2 + 1/3 + 1/4 + … + 1/(n + 1)，其中最上面的那块牌伸出其下的牌1/2，第二块牌伸出其下的那块牌1/3，第三块牌伸出其下的那块牌1/4，以此类推，最后那块牌伸出桌面1/(n+1)。如图1-1所示。
图1-1 一摞悬挂于桌边的纸牌
输入
输入包含若干个测试案例，每个案例占一行。每行数据包含一个有两位小数的浮点数c，取值于[0.01, 5.20]。最后一行中c为0.00，表示输入文件的结束。
输出
对每个测试案例，输出能达到悬挂长度为c的最少的牌的张数。需按输出样例的格式输出。
输入样例
1.00
3.71
0.04
5.19
0.00输出样例
3 card(s)
61 card(s)
1 card(s)
273 card(s)解题思路
（1）数据的输入与输出
根据题面描述，输入文件的格式与问题1-1的相似，含有多个测试案例，每个案例占一行数据，其中包含表示扑克牌悬挂于桌边的总长度的数据c。c=0.0是输入数据结束的标志。对每个案例数据c进行处理，计算所得的结果为能悬挂于桌边的总长度为c的扑克牌的张数，按格式“张数card(s)”作为一行输出文件。
1 打开输入文件inputdata
2 创建输出文件outputdata
3 从inputdata中读取案例数据c
4 while c≠0.0
5 do result← HANGOVER(c)
6 将"result card(s) "作为一行写入outputdata
7 从inputdata中读取案例数据c
8 关闭inputdata
9 关闭outpudata
其中，第5行调用计算能悬挂在桌边的长度为c的扑克牌张数的过程HANGOVER(c)是解决一个案例的关键。
（2）处理一个案例的算法过程
对每一个测试案例的输入数据c，根据题意就是要求出
。写出伪代码过程如下。
HANGOVER(c)
1 n←1, length←0
2 while length<c
3 do length←length+1/(n+1)
4 n←n+1
5 if length>c
6 then n←n-1
7 return n
算法1-2 对已知的纸牌悬挂长度c，计算纸牌张数的过程
算法中，第1行设置了两个计数器：n（初始化为1）和length（初始化为0）分别表示扑克牌张数和悬挂在桌边的长度。第2～4行的while循环的重复执行条件是length<c，每次重复将1/(n+1)累加到length，且n自增1。该循环结束时必有length
c（等价地，意味着n是第1个使得该条件成立的纸牌数）。若length>c，则意味着n应当减少1（这就是第5～6行的功能）。
算法的运行时间依赖于第2～4行的while循环重复次数n。由于
1/2+1/3+…+1/n
1+1/2+1/3+…+1/(2⌈n/2⌉-1)
=1+(1/2+1/3)+(1/22+1/(22+2)+1/(22+3))+…
+(1/2i+1/(2i+1)+…+1/(2i+2i-1))+…
+(1/2lg⌈n/2⌉+1/(2lg⌈n/2⌉+1)+…+1/(2lg⌈n/2⌉+2lg⌈n/2⌉-1))
<1+(1/2+1/2)+(1/22+1/22+1/22+1/22)+…
+(
)+…
+(
)
=
=Θ(lgn)
即c=Θ(lgn)，亦即n=Θ(2c)。于是该算法的运行时间T(c)=n=Θ(2c)。幸好c介于0.01～5.20之间，否则当c很大时，算法是极费时的。
解决本问题的算法的C++实现代码存储于文件夹laboratory/Hangover中，读者可打开文件Hangover.cpp研读，并试运行之。C++代码的解析请阅读9.1节中程序9-1的说明。
问题描述
魔法师百小度也有遇到难题的时候——现在，百小度正在一个古老的石门面前，石门上有一段古老的魔法文字，读懂这种魔法文字需要耗费大量的能量和脑力。
过了许久，百小度终于读懂了魔法文字的含义：石门里面有一个石盘，魔法师需要通过魔法将这个石盘旋转X度，以使上面的刻纹与天相对应，才能打开石门。
但是，旋转石盘需要N点能量值，而为了解读密文，百小度的能量值只剩M点了！破坏石门是不可能的，因为那将需要更多的能量。不过，幸运的是，作为魔法师的百小度可以耗费V点能量，使得自己的能量变为现在剩余能量的K倍（魔法师的世界你永远不懂，谁也不知道他是怎么做到的）。例如，现在百小度有A点能量,那么他可以使自己的能量变为(A-V)×K点（能量在任何时候都不可以为负，即：如果A小于V的话，就不能够执行转换）。
然而，在解读密文的过程中，百小度预支了他的智商，所以他现在不知道自己是否能够旋转石盘并打开石门，你能帮帮他吗？
输入
输入数据第一行是一个整数T，表示包含T组测试案例。
接下来是T行数据，每行有4个自然数N, M, V, K（字符含义见题目描述）。
数据范围如下：
T100
N, M, V, K 108
输出
对于每个测试案例，请输出最少做几次能量转换才能够有足够的能量点开门；如果无法做到，请直接输出“−1”。
输入样例
4
10 3 1 2
10 2 1 2
10 9 7 3
10 10 10000 0输出样例
3
-1
-1
0解题思路
（1）数据的输入与输出
题面告诉我们，输入文件的第一行给出了测试案例的个数T，其后的T行数据，每行表示一个案例，读取每个案例的输入数据N, M, V, K，处理后得到的结果是能量转换次数（若经过若干次能量转换能够打开石门）或−1（不可能打开石门），并将所得结果作为一行写入输出文件。表示成伪代码过程如下。
1 打开输入文件inputdata
2 创建输出文件outputdata
3 从inputdata中读取案例数T
4 for t←1 to T
5 do 从inputdata中读取案例数据N, M, V, K
6 result← ENERGY-CONVERSION(N, M, V, K)
7 将result作为一行写入outputdata中
8 关闭inputdata
9 关闭outpudata
其中，第6行调用计算百小度最少能量转换次数的过程ENERGY-CONVERSION(N, M, V, K)是解决一个案例的关键。
（2）处理一个案例的算法过程
对于问题输入中的一个案例数据N, M, V, K，需考虑两个特殊情况：
① M N，即百小度一开始就具有足够的能量打开石门。此时，百小度立刻打开石门。
② M<N且M<V ，百小度必须增加能量才可能打开石门，但按题面，一开始就不可能进行能量转换。所以百小度不可能打开石门。
一般情况下，（即M<N且MV），从A =M开始，模拟百小度反复转换能量A←(A-V)×K，设置跟踪转换能量的次数的计数器count，直至能量足以打开石门为止（即AN），count 即为所求。在这一过程中，需要监测能量转换A←(A−V)×K是否增大了能量A，如果检测到某次转换后A (A−V)×K，那意味着从此不可能增大能量，所以在这种情况下百小度也不能打开石门。
将上述思考写成伪代码如下。
ENERGY-CONVERSION(N, M, V, K)
1 A←M, count←0
2 if A
N ▷情形①
3 then return 0
4 if A<V ▷情形②
5 then return -1;
6 repeat
7 if A(A-V)*K ▷转换不能增大能量
8 then return -1;
9 A←(A-V)*K;
10 count ← count +1;
11 until AN
12 return count
算法1-3 对一个案例数据N, M, V, K，计算最少能量转换次数的过程
算法1-3中，第1、12行耗时为常数。第2～3行和第4～5行的if结构也都是常数时间的操作。第6～11行的repeat-until结构，A从M开始，循环条件是AN，每次重复第9行将使A至少增加1，所以至多重复N-M次。因此，过程ENERGY-CONVERSION的运行时间为O(N-M)。
解决本问题的算法的C++实现代码存储于文件夹laboratory/Energy Conversion中，读者可打开文件Energy Conversion.cpp研读，并试运行之。C++代码的解析请阅读第9章9.1.2节中程序9-3的说明。
描述
牛妞Betsy绕着谷仓闲逛时，发现农夫John建了一个秘密的暖房，里面培育了各种奇花异草，五彩缤纷。Betsy惊喜万分，她的小牛脑瓜里顿时与暖房一样充满了各色的奇思妙想。
“我要沿着农场篱笆挖上一排共F(7F10000)个种花的坑。”Betsy心里想着。“我要每3个坑（每隔2个坑）种一株玫瑰，每7个坑（每隔6个坑）种一株秋海棠，每4个坑（每隔3个坑）种一株雏菊……并且让这些花儿永远开放。”Betsy不知道如此栽种后还会留下多少个坑，但她知道这个数目取决于每种花从哪一个坑开始，每N个坑栽种一株。
我们来帮Betsy计算出会留下多少个坑可以栽种其他的花。共有K (1K100)种花，每种花从第L (1LF)个坑开始，每隔I-1个坑占据一个坑。计算全部栽种完成后剩下的未曾占用的坑。
按Betsy的想法，她可以将种植计划描述如下：
30 3 [30个坑；3种不同的花]
1 3 [从第1个坑开始，每3个坑种一株玫瑰]
3 7 [从第3个坑开始，每7个坑种一株秋海棠]
1 4 [从第1个坑开始，每4个坑种一株雏菊]
于是，花园中篱笆前开始时那一排空的坑形状如下：
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
种上玫瑰后形状如下：
R . . R . . R . . R . . R . . R . . R . . R . . R . . R . .
种上秋海棠后形状如下：
R . B R . . R . . R . . R . . R B . R . . R . B R . . R . .
种上雏菊后形状如下：
R . B R D . R . D R . . R . . R B . R . D R . B R . . R D .
留下13个尚未栽种任何花的坑。
输入
*第1行：两个用空格隔开的整数F和K。
第2～K+1行：每行包含两个用空格隔开的整数Lj和Ij，表示一种花开始栽种的位置和间隔。
输出
*仅含一行，只有一个表示栽种完毕后剩下的空坑数目的整数。
输入样例
30 3
1 3
3 7
1 4输出样例
13解题思路
（1）数据的输入与输出
本问题的输入仅含一个测试案例。输入的开头是表示栽种花的坑数目和栽种花的种数的两个数F和K。案例中还包含两个序列：每种花的栽种起始位置L[1..K]和栽种间隔I[1..K]。读取这些数据，处理计算出栽种完所有K种花后，F个坑中还剩多少个是空的，并把结果作为一行数据写入输出文件中。
1 打开输入文件inputdata
2 创建输出文件outputdata
3 从inputdata中读取案例数F，K
4 创建数组L[1..K]，I[1..K]
5 for i←1 to K
6 do 从inputdata中读取案例数据L[i], I[i]
7 result← THE-FLOWER-GARDEN(F, K, L, I)
8 将result作为一行写入outputdata中
9 关闭inputdata
10 关闭outpudata
其中，第7行调用过程THE-FLOWER-GARDEN(F, K, L, I)计算Betsy在篱笆前将K种花按计划裁种完毕还剩下的空坑数目是解决这个案例的关键。
（2）处理这个案例的算法过程
对于一个测试案例，设K种花中开始栽种位置最小的坑的编号为i，设置一个空坑计数器count，初始化为i-1，因为在i之前的坑必不会载上任何花。从当前位置开始依次考察每一个坑是否会栽上一株花。如果K种花按计划都不会占据这个坑，则count自增1。所有的位置考察完毕，累加在count中的数据即为所求。
THE-FLOWER-GARDEN(F, K, L, I)
1 i←MIN-ELEMENT(L) ▷最先开始栽种花的坑
2 count←i-1 ▷之前的坑当然是空的
3 while iF ▷逐一考察以后的每个坑
4 do for j←1 to K ▷逐一考察每一种花
5 do if i-1 Mod I[j]≡L[j] ▷查看第i个坑是否栽上第j种花
6 then break this loop
7 if j>K ▷若i号坑没有种上任何花
8 then count←count+1 ▷空坑计数器增加1
9 i ←i+1
10 return count
算法1-4 对一个案例数据F, K, L, I，计算剩下空坑数目的过程
算法1-4的运行时间取决于第3～9行的两重循环的最里层循环体（第5～6行的操作）的重复次数。由于外层的while循环最多重复F次，里层的for循环最多重复K次，所以时间复杂度为O(FK)。
解决本问题算法的C++实现代码存储于文件夹laboratory/ The Flower Garden中，读者可打开文件The Flower Garden.cpp研读，并试运行之。C++代码的解析请阅读第9章9.4.1节中程序9-38、程序9-39的说明。
以上那样利用循环重复将部分数据简单地累加，可以解决很多计数问题。然而，如果计数问题可以通过数学计算直接得出结果，往往可以大大改善算法的时间效率，请看下列问题。
问题描述
一年一度的百度之星大赛又开始了，这次参赛人数创下了吉尼斯世界纪录。于是，百度之星决定奖励一部分人：所有资格赛提交ID以x结尾的参赛选手将得到精美礼品一份。
小小度同学非常想得到这份礼品，于是他就连续提交了很多次，提交的ID从a连续到b。他想知道能得到多少份礼品，你能帮帮他吗？
输入
第一行一个正整数T表示测试案例数。
接下来T行，每行3个不含多余前置零的整数x，a，b（0x1018，1ab1018）。
输出
T行。每行为对应的数据下，小小度得到的礼品数。
输入样例
2
88888 88888 88888
36 237 893输出样例
1
6解题思路
（1）数据的输入与输出
题面中告诉我们，输入文件的第一个数据指出了所含的测试案例数T，每个案例的输入数据仅占一行，其中包含了3个分别表示ID尾数x、ID取值下界a和上界b的整数。计算所得结果为a～b内能够得到礼物的ID（尾数为x）个数，作为一行输出到文件中。表示成伪代码如下。
1 打开输入文件inputdata
2 创建输出文件outputdata
3 从inputdata中读取案例数T
4 for t←1 to T
5 do 从inputdata中读取案例数据x, a, b
6 result← GIFT(x, a, b)
7 将result作为一行写入outputdata中
8 关闭inputdata
9 关闭outpudata
其中，第6行调用过程GIFT (x, a, b)计算能够得到的礼物数是解决一个案例的关键。
（2）处理一个案例的算法过程
对一个测试案例x, a, b而言，很容易想到用列举法穷尽a～b所有的整数，检测每一个的尾数是否与x相等。跟踪相等的个数：
GIFT (x, a, b)
1 t← x的10进制位数
2 m←10t
3 count ←0
4 for i ←a to b
5 do if i Mod m=x
6 then count ←count+1
7 return count
算法1-5 对一个测试案例数据x, a, b，累加计算获得礼品数的算法过程
算法1-5中的第1、2行计算m=10t，其中t为x的10进制位数，可以用如下操作实现：
1 m←1
2 while m<x
3 do m←m*10
显然耗时为log10x，若a～b之间有n个数，则上述算法中第3～6行代码的运行时间是Θ(n)，于是算法1-5的运行时间为Θ(log10x)+ Θ(n)。借助数学计算，我们可以把解决这个问题的算法时间缩小为Θ(log10x)。设x的10进制位数为t，令m为10t。例如，若x=36，a=237，b=893，则t=2，m=100。设ar =a Mod m，aq=a/m 。即ar为a除以m的余数，aq为a除以m的商。相仿地，设br=b Mod m，bq=b/m。对于x=36，a=237，b=893，有ar =37，aq=2，br=93，bq=8。由于ar =37>36=x，所以a(=237)之后最小的位数为x(=36)的数应为336。而由于br=93>36=x，故在b=893之前最大的尾数为36的数为836。因此，介于a，b之间尾数为x的数为336，436，536，636，736，836，一共有bq− (aq+1)+1＝6个。
上例说明，对于x, a, b，若axb，计算出ar =a Mod m，aq=a/m ，br=b Mod m，bq=b/m后，检测ar是否大于x。若是，则aq增1。相仿地，检测br是否小于x，若是，则bq减1。bq−aq+1即为所求。写成伪代码过程如下。
GET-GIFT(x, a, b)
1 t← x的10进制位数
2 m←10t
3 ar ←a Mod m，aq←a/m
4 br ←b Mod m，bq←b/m
5 if ar>x
6 then aq←aq+1
7 if br<x
8 then bq←bq-1
9 return bq-aq+1
算法1-6 对一个测试案例数据x, a, b，直接计算获得礼品数的算法过程
算法1-6中的第1～2行与算法1-5中的一样，耗时Θ(log10x)。而算法其余部分耗时为Θ(1)。于是，算法1-6的运行时间为Θ(log10x)。
解决本问题的算法的C++实现代码存储于文件夹laboratory/Get Gift中，读者可打开文件getgift.cpp研读，并试运行之。
问题描述
农夫John养了一群牛妞。有些牛妞很任性，时常离家出走。一天，John 得知了他的一头在外流浪的牛妞出后想立刻去把她领回家。John从数轴上的点N (0N100 000)处出发，牛妞出没于同一数轴上点K (0K100 000)处。John有两种移动方式：走路或远距飞跃。
假定牛妞对自身的危险一无所知，一直在原地溜达，John最少要花多少时间才能够抓到她？
输入
输入文件的第一行仅含一个表示测试案例个数的整数T。其后跟着T行数据，每行数据描述一个测试案例，包括两个用空格隔开的整数：N和K。
输出
每个案例只有一行输出：John抓到牛妞的最少时间（分钟）。
输入样例
2
5 17
3 21输出样例
4
6解题思路
（1）数据的输入与输出
根据题面中对输入、输出数据的格式描述，我们可以将处理所有案例的过程表示如下。
1 打开输入文件inputdata
2 创建输出文件outputdata
3 从inputdata中读取案例数T
4 for t←1 to T
5 do 从inputdata中读取案例数据N, K
6 result←CATCH-THAT-COW(N, K)
7 将result作为一行写入outputdata中
8 关闭inputdata
9 关闭outpudata
其中，第6行调用过程CATCH-THAT-COW(N, K)计算John从N出发抓到位于K的牛妞要用的最短时间是解决一个案例的关键。
（2）处理一个案例的算法过程
John要想最快地从点N到达点K处，就要充分利用他的飞跃能力。需要注意的是，John步行时可来回走，而飞越只能是单向的。所以，当NK时，John 只能从N步行到K（见图1-2（a））。此时，需要走N-K分钟。
考虑N<K的情形。直观地看，从N 通过飞跃i次，到达2iN。设John 从N 飞跃q 次后N2qK而N2q+1>K（见图1-2（b））。最理想的情况是N2q=K， 此时q即为所求。否则John有两个可能的走法：
① 从N飞跃q 次到达N2q，再往前走K−N2q分钟到达K，即用时为q+K−N2q分钟。
② 从N飞跃q+1次到达N2q+1，再往回走N2q+1−K分钟到达K，即用时为q+1+ N2q+1−K分钟。
图1-2 John从N出发到K处的走法
取两者较小者可能是最优解。然而这并不全面，因为还有更加微妙的情况会出现。以题面的输入样例N=5，K=17为例。2×5<17，且22×5>17。按第①种方案，需用1+7=8分钟，而用第（2）种方案需用2+3=5分钟。但是，如果John先从N=5往回走1分钟，来到4(=22)处，然后从22处飞跃2次来到24(=16)处，再从24向前走1分钟就可到达K=17，这样所用的时间为4分钟，更短。
形式化地说，设不超过N的2的幂之最大者为2t，而不超过K的2的幂之最大者为2p。于是必有2tN<2t+1及2pK<2p+1（见图1（c））。此时，John 可以有4种不同的走法：
① 从N步行到2t，从2t飞跃到2p，再从2p走到K。用时：(N−2t)+(p−t)+(K−2p)。
② 从N步行到2t，从2t飞跃到2p+1，再从2p+1走到K。用时：(N−2t)+(p−t+1)+(2p+1−K)。
③ 从N步行到2t+1，从2t+1飞跃到2p，再从2p走到K。用时：(2t+1−N)+(p−t+1)+(K−2p)。
④ 从N步行到2t+1，从2t+1飞跃到2p+1，再从2p+1走到K。用时：(2t+1−N)+(p−t)+(2p+1− K)。
所以，若令a=q+K−2qN，b=q+1+2q+1N−K，c=(N−2t)+(p−t)+(K−2p)，d=(N−2t)+(p−t+1)+(2p+1−K)，e=(2t+1−N)+(p−t+1)+(K−2p)，f=(2t+1−N)+(p−t)+(2p+1−K)，则min{a, b, c, d, e, f}即为所求。上述算法可写成如下的伪代码。
CATCH-THAT-COW(N, K)
1 if NK
2 then return N-K
3 p←max{i|2iK}, q←max{i|2iNK}, t←max{i|2iN}
4 if N2q=K
5 then return q
6 a← q+K-N2q , b← q+1+ N2q+1-K, c←(N-2t)+(p-t)+(K-2p)
7 d←(N-2t)+(p-t+1)+(2p+1-K), e←(2t+1-N)+(p-t+1)+(K-2p), f ←(2t+1-N)+(p-t)+(2p+1-K)
8 return min{a, b, c, d, e, f}
算法1-7 计算农夫John 从N到K最少时间的算法过程
算法1-7中，第3行计算不超过某整数x的最大的2的整幂指数，可以通过如下过程进行。
CALCULATE(x)
1 p←1, t←0
2 while p<x
3 do p←p*2
4 t←t+1
5 if p>x
6 then t←t-1
7 return t and 2t
算法1-8 计算不超过最大的2的整幂指数的整数x的算法过程
由于tlgx，而第2～4行的while循环每次重复t（从0开始）都会增加1，所以该循环至多重复lgx次。于是算法1-8的运行时间为Θ(lgx)。算法1-7的第3行调用三次CALCULATE过程就可完成指数p，2p，q，N2q，t，2t的计算，而算法的其他部分均在常数时间内完成，所以算法1-7的运行时间为O(lgK)。
解决本问题的算法的C++实现代码存储于文件夹laboratory/Catch The Cow中，读者可打开文件Catch The Cow.cpp研读，并试运行之。
有些问题需要综合地使用数学计算和累加和方法加以解决。
描述
你是个暴脾气，最讨厌等待。你打算去新奥尔良拜访一位朋友。来到公交站你才发现这里的调度表是世界上最糟糕的。这个车站并没有列出各路公交车班车到达与出发的时间表，只列出各相邻班车的发车间隔时长。暴躁的你从包中抓出平板电脑，试图写一段程序以计算最近来到的班车还需要等待多久。嘿，看来你只能这样了，不是吗？
输入
本问题的输入包含不超过100个测试案例。每个案例的输入数据格式如下。
一个测试案例的数据包括四个部分：
开头行——只有一行，“START N”，其中的N表示公交车路数（1N20）。
路线发车间隔区间行——共有N行。每行由M（1M10）个发车间隔时长组成，这些数据表示这一路线的各班车上一班发车起到本班车出发时刻的间隔时间长度。每个间隔时长是一个介于1～1000之间的整数。
到达时间——仅一行。该行数据表示你到达车站开始等待的时间。这个数据表示的是从当天车站开始运行到你来到车站的时间单位数（所有的线路的车都是从时间0开始运行的）。这是一个非负整数（若为0，意味着班车在你到站时起步）。
结束行——单一的一行，“END”。
最后一个测试案例后有一行“ENDOFINPUT”，作为输入结束标志。
输出
对每一个测试案例，恰有一行输出。这一行仅包含一个表示你在下一趟班车到来之前需要等待的时间单位数。我们希望你等来的这班车是去往新奥尔良的！
注意
每班公交连续不断地循环运行于它的线路上。
若乘客在班车离开时刻到达，他/她将搭上这班车。
输入样例
START 3
100 200 300
400 500 600
700 800 900
1000
END
START 3
100 200 300 4 3 2 4 2 22
800
10 1000
32767
END
ENDOFINPUT输出样例
200
20解题思路
（1）数据的输入与输出
按题面对输入文件的格式描述，输入包含多个测试案例，每个案例的第一行包含两个部分：开头标志“START”和表示本案例中公交车的路数N。案例数据接下来的N行数据表示每一路车各相邻班车的发车间隔。接着一行仅含一个表示乘客到达时间的整数。最后一行是案例结束标志“END”。例如，输入样例中第一个案例的第1行数据START 3表示该案例有3路公交车。后面3行数据表示各路公交的各班车的发车间隔，例如第1行的数据100 200 300表示1路车的第1、2班车的发车间隔为100，第2、3班车的发车间隔为200，第3、1班车的发车间隔为300。以此类推。最后一行数据1000表示乘客到来的时刻。
文件的结束标志是一行“ENDOFINPUT”。
依次读取每个案例的数据，将发车间隔数据组织成一个表durations，到达时间记为arrival，对案例数据进行处理，计算得到乘客最小等待时间，并将结果作为一行写入输出文件。描述成伪代码如下：
1 打开输入文件inputdata
2 创建输出文件outputdata
3 从inputdata中读取一行到s
4 while s≠"ENDOFINPUT"
5 do 略过s中的"START"，并读取N
6 创建数组durations[1..N]
7 for i←1 to N
8 do从inputdata中读取一行到s
9 将s中的每一个整数数据添加到durations[i]中
10 从inputdata中读取arrival
11 result←WORLD-WORST-BUS-SCHEDULE(durations, arrival)
12 将result作为一行写入outputdata
13 在inputdata中略过一行"END"
14 从inputdata中读取一行到s
15 关闭inputdata
16 关闭outpudata
其中，第11行调用过程WORLD-WORST-BUS-SCHEDULE(durations, arrival)计算乘客最小的等车时间，是解决一个案例的关键。
（2）处理一个案例的算法过程
对一个案例而言，将各路车的出发间隔时长记录在一组数组durations中，durations[i][j]表示第i路车第j次发车距第j-1次发车的时间间隔。Ti=
表示第i路各班车运行一个循环所用的时间（i=1, 2,…,n）。若设本案例中乘客的到达时间为arrival，则Ri=arrival MOD Ti表示乘客来到车站时，第i路车运行完若干个循环周期后处于最新运行周期内的时间。例如，输入样例中的案例1中1路车3班车的一个运行周期T1为100+200+ 300=600，乘客到达时间arrival=1000，R1=arrival MOD T1=1000 MOD 600≡400。这意味着1路车的3班车已经运行了一个循环后400时乘客到达车站。于是，乘客需要等待的应该是当前周期内从开始到最近发车时间超过400的那班车。等待的时间自然就是从第一个使得差−Ri0（1kmi）的值。本例中此值为(100+200+300) −400 = 600 – 400=200。所有n路的等待时间中的最小值即为所求。以上算法思想写成伪代码过程如下。
WORLD-WORST-BUS-SCHEDULE(durations, arrival)
1 n←length[durations]
2 for i←1 to n
3 do mi←length[durations[i]]
4 Ti←
durations[i][j]
5 Ri← arrival MOD Ti
6 k←1
7 while 
durations[i][j]-Ri <0
8 do k←k+1
9 time[i] ←
durations[i][j]-Ri
10 return min(time)
算法1-9 计算乘客最小等待时间的算法过程
设案例中有n路公交，其中班次最多的班数为m。算法的运行时间取决于第2～9行的两层嵌套循环重复次数。外层for循环重复n次，里层的第4行实际上也是一个循环（计算累加和），重复次数最多为m。同样，第7～8行的while循环也至多重复m次。这两个内层的循环是并列的，所以运行时间为O(nm)。
解决本问题的算法的C++实现代码存储于文件夹laboratory/ World's Worst Bus Schedule中，读者可打开文件World's Worst Bus Schedule.cpp研读，并试运行之。
组合数学中有两条著名的原理——加法原理和乘法原理。利用这两条原理可以快速地解决一些计数问题。
加法原理：做一件事，完成它可以有n类办法，在第一类办法中有m1种不同的方法，在第二类办法中有m2种不同的方法，……，在第n类办法中有mn种不同的方法，那么完成这件事共有N＝m1＋m2＋m3＋…＋mn种不同方法。
乘法原理：做一件事，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法，……，做第n步有mn种不同的方法，那么完成这件事共有N＝m1×m2×m3×…×mn种不同的方法。
维基百科
问题描述
冒泡排序是一种简单的排序算法。该算法反复扫描欲排序的列表，比较相邻元素对，若两者顺序不对，就将它们交换。这样对列表的扫描反复进行直至列表中不存在需要交换的元素为止，这意味着列表已经排好序。算法之所以叫此名字，是缘于最小的元素就像“泡泡”一样冒到列表的顶端，这是一种基于比较的排序算法。
冒泡排序是一种非常简单的排序算法，其运行时间为O(n2)。每趟操作从列表首开始，以此比较相邻项，需要时交换两者。重复进行若干趟这样的操作直至无需再做任何交换操作为止。假定恰好做了T趟操作，序列就按升序排列，我们就说T为对此序列的冒泡排序趟数。下面是一个例子。序列为“5 1 4 2 8”，对其施行的冒泡排序如下所示。
第一趟操作：
( 51 4 2 8 ) −> ( 1 5 4 2 8 )，比较头两个元素，并将其交换。
( 1 5 4 2 8 ) −> ( 1 4 5 2 8 )，交换，因为5 > 4。
( 1 4 5 2 8 ) −> ( 1 4 2 5 8 )，交换，因为5 > 2。
( 1 4 2 5 8 ) −> ( 1 4 2 5 8 )由于这两个元素已经保持顺序（8>5），算法不对它们进行交换。
第二趟操作：
( 1 4 2 5 8 ) −> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) −> ( 1 2 4 5 8 )，交换，因为4 > 2。
( 1 2 4 5 8 ) −> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) −> ( 1 2 4 5 8 )
在T = 2趟后，序列已经排好序，所以我们说对此序列冒泡排序的趟数为2。
ZX在算法课中学习冒泡排序，他的老师给他留了一个作业。老师给了ZX一个具有N个两两不等的元素的数组A，并且已经排成升序。老师告诉ZX，该数组是经过了K趟的冒泡排序得来的。问题是：A有多少种初始状态，使得对其进行冒泡排序，趟数恰为K？结果可能是一个很大的数值，你只需输出该数相对于模20100713的剩余。
输入
输入包含若干个测试案例。
第一行含有一个表示案例数的整数T (T100 000)。
跟着的是T行表示各案例的数据。每行包含两个整数N和K(1N1,000,000, 0KN−1)，其中N表示序列长度而K表示对序列进行冒泡排序的趟数。
输出
对每个案例，输出序列的初始情形数对模20100713的剩余，每个一行。
输入样例
3
3 0
3 1
3 2输出样例
1
3
2解题思路
（1）数据的输入与输出
根据输入文件格式的描述，首先在其中读出测试案例个数T。然后依次读取案例数据N和K。对每个案例计算进行K趟处理就能实现冒泡排序的数组A[1..N]有多少种可能的初始状态，并将所得结果作为一行写入输出文件。
1 打开输入文件inputdata
2 创建输出文件outputdata
3 从inputdata中读取案例数T
4 for t←1 to T
5 do 从inputdata中读取案例数据N, K
6 BUBLLE-SORT-ROUNDS(N, K, k, x, count)
7 将count作为一行写入outputdata中
8 关闭inputdata
9 关闭outpudata
其中，第6行调用过程BUBLLE-SORT-ROUNDS(N, K, k, x, count)计算进行K趟处理就能实现冒泡排序的数组A[1..N]有多少种可能的初始状态，是解决一个案例的关键。
（2）处理一个案例的算法过程
为方便计，我们假定序列A中的N个数为0，1，…，N-1。注意，冒泡排序的第k趟操作，总是将当前范围（A[0..k−1]）内的最大的元素推至当前范围的最后位置A[k−1]。
除了针对趟数K=0的唯一初始状态A[0..N−1]已经有序外，我们归纳K=k(1k<N)的各种情形。
K=1时，初始状态只能是1，…， N−1中的一个元素不出现在自己应有的位置上，而其他元素均处于相对顺序的位置上。对于1而言，它要出现在A[0]处；对于2而言，它可以出现在A[0]、A[1]处之一；…一般地，对于i（0<i<N），可以出现在A[0..i−1]中的任一位置处。根据加法原理，我们有初始状态共有1+2+…+N−1种。
K=2时，初始状态可以是1，…， N−1中的两个元素不出现在应有的位置上，而其他元素均处于相对顺序的位置上。对于0<i1<i2<N−1，i1有i1种可行的位置，i2有i2种可行的位置，根据乘法原理共有i1i2种初始状态。再根据加法原理K=2时序列A共有
种初始状态，使得对其进行冒泡排序恰要进行K=2趟操作。
一般地，K=k(1k<N)时，序列A共有
种初始状态，使得对其进行冒泡排序恰要进行K=k趟操作。注意，该和式中的每一项恰为K个因子之积。
若将1～N-1中的K个数0<i1<i2<…<iK<N保存在数组x[0..K-1]中，数组A[0..N-1]的初始状态数保存在变量count中，则上述的算法可写成如下的递归过程。
BUBLLE-SORT-ROUNDS(N, K, k, x, count) ▷k表示递归层次
1 if kK ▷得到一个积
2 then item←1
3 for i←1 to K
4 do item←(itemxi) MOD 20100713
5 count←(count+item) MOD 20100713
6 return
7 if k=0
8 then begin←N-1, end← K ▷顶层，x[0]的取值范围
9 else begin←xk-1-1, end← K-k ▷k>1时，x[k]的取值范围
10 for p←begin downto end ▷确定第k个因子
11 do xk ← p
12 BUBLLE-SORT-ROUNDS(N, K, k+1)
算法1-10 计算具有N个不同元素恰做K趟操作完成排序的序列初始状态数的过程
对测试案例数据N和K，上述过程运行如下。这是一个递归过程。递归层次由参数k表示，表示计算一个积中第k个因子。最顶层的调用应该是BUBLLE-SORT-ROUNDS(N, K, 0, x, count)，即k=0。
第1～7行当检测到k>K时，意味着得到一个积的所有因子。由于20100713是一个素数，以它为模的剩余类[3]对加法和乘法运算是封闭的，所以，可以对每一步乘法运算求关于模20100713的剩余，也可以在将积累加到count时进行求关于模20100713的剩余。
第7～8行if-then-else结构针对k是否为1决定第k个因子的取值范围begin～end。
第9～12行的for循环完成对第k个因子xk的确定后，调用自身确定xk+1。
由于
中每个项
中构成各因子（it−1）的it满足0<i1…ik<N-1，即i1，…，ik取自于2，3，…，N。共有
[4]种不同的组合方式，每种方式要进行第3～4行的累积计算，所以第5行要被执行次。算法1-10的运行时间为*K。
解决本问题的算法的C++实现代码存储于文件夹laboratory/Bubble Sort中，读者可打开文件BubbleSort.cpp研读，并试运行之。
有的计数问题所涉及的事物间存在着某种关系，这样的问题往往可以表示成一个图（Graph）：问题中的每个事物视为一个顶点，两个顶点之间如果存在这关系，就在这两个顶点之间做一条称为边的弧。形式化描述为由问题中的各事物构成的集合，记为顶点集V={v1,v2,…,vn}，边集E={(vi, vj)| vi, vj ∈V且vi和vj具有关系}。
例如，图1-3将五个人Adward、John、Philips、Robin和Smith之间的朋友关系表示成了一个图。其中，Adward与Robin和Smith是朋友，John与Philips和Robin是朋友，Philips与John、Robin和Smith是朋友，Smith与Adward、Philips和Robin是朋友，Robin与其他所有人都是朋友。
图1-3 表示五个人之间朋友关系的图
图G记为<V, E>。数学家们对图的研究已经有了百年的历史，有很多很好用的性质能帮助我们轻松地解决计数问题。例如，图论中有一个著名的“握手”定理。
定义1-1
设G=<V，E>为一无向图，vV，称v作为边的端点次数之和为v的度数，简称为度，记为d(v)。
对图中所有顶点的度数有如下所述的结论。
定理1-1（握手定理）
设G=<V，E>为任意无向图，V={v1,v2,…,vn}，|E|=m，则
即所有顶点的度数之和为边数的2倍。
证 G中每条边（包括环）均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，当然，m条边，共提供2m度。
握手定理说明，图中各顶点的度数之和必为偶数。
问题描述
百度之星总决赛既是一群编程大牛一决高下的赛场，也是圈内众多网友难得的联欢，在为期一周的聚会中，总少不了各种有趣的游戏。
某年的总决赛聚会中，一个有趣的游戏是这样的：
游戏由Robin主持，一共有N个人参加（包括主持人），Robin让每个人说出自己在现场认识的人数（如果A认识B，则默认B也认识A），在收到所有选手报出的数据后，他来判断是否有人说谎。Robin说，如果他能判断正确，希望每位选手都能在毕业后来百度工作。
为了帮Robin留住这些天才，现在请您帮他出出主意吧。
特别说明：
1．每个人都认识Robin。
2．认识的人中不包括自己。
输入
输入数据包含多组测试用例，每组测试用例有2行，首先一行是一个整数N (1<N100)，表示参加游戏的全部人数，接下来一行包括N-1个整数，表示除主持人以外的其余人员报出的认识人数。
N为0的时候结束输入。
输出
请根据每组输入数据，帮助主持人Robin进行判断：如果确定有人说谎，请输出“Lie absolutely”；否则，请输出“Maybe truth”。
每组数据的输出占一行。
输入样例
7
5 4 2 3 2 5
7
3 4 2 2 2 3
0输出样例
Lie absolutely
Maybe truth解题思路
（1）数据的输入与输出
根据题面中对输入文件格式的描述，文件中有若干个测试案例，每个案例的数据以表示人数的整数N开头，然后有N-1个整数表示除主持人以外的每个人所报告的相识人数。对案例判断其中是否有人说谎，根据计算结果输出一行“Maybe truth”（无人说谎）或“Lie absolutely”（有人说谎）。N=0是输入结束的标志。
1 打开输入文件inputdata
2 创建输出文件outputdata
3 从inputdata中读取人数N
4 while N≠0
5 do 创建数组a[1..N]
6 for i←1 to N-1
7 do 从inputdata中读取a[i]
8 a[N] ←N-1 ▷Robin认识每个人
9 result← PARTY-GAME(a)
10 if result=true
11 then 将"Maybe truth"作为一行写入outputdata
12 else将"Lie absolutely"作为一行写入outputdata
13 从inputdata中读取案例数据N
14 关闭inputdata
15 关闭outpudata
其中，第9行调用过程PARTY-GAME(a)判断N个人中是否有人说谎，是解决一个案例的关键。
（2）处理一个案例的算法过程
在一个案例中，把两个人相互认识看成一种关系，n个人之间的认识关系将可表示成一个无向图G=<V, E>。其中，顶点集V={v1,v2,…,vn}表示这n个人，边集E中元素表示两个人之间的认识关系。
利用握手定理，我们将问题中的每一个案例的所有人所报的认识的人数（包括主持人报的n−1）相加，考察和数的奇偶性，若为奇数，则肯定有人撒谎。等价地，设置一个计数器count（初始为0），检测每个人（包括主持人）所报的认识的人数，若是奇数则count增加1，根据count的奇偶性进行判断。伪代码过程表示为如下：
PARTY-GAME(a)
1 n←length[a]
2 count←0
3 for i←1 to n ▷检测每一个人报告的认识人数
4 do if a[i] is odd
5 then count←count+1
6 return count is even
算法1-11 利用握手定理判断晚会中是否有客人说谎的过程
对一个案例而言，假定包括主持人在内，晚会上有n个人，则第3～5行的for循环将重复n次。所以算法对一个案例的运行时间是Θ(n)。
解决本问题的算法的C++实现代码存储于文件夹laboratory/Party Game中，读者可打开文件partygame.cpp研读，并试运行之。
设有n个两两不等的元素a1, a2, …, an构成的集合A，考虑A到自身的一个1-1变换σ：a'1=σ(a1)， a'2=σ(a2)，…，a'n=σ(an)。换句话说，a'1，a'2，…，a'n是a1, a2, …, an的一个重排。数学中，称这样的对应关系σ为A的一个置换。
【例1】集合A={2，4，3，1}，σ(2)=1，σ(4)=2，σ(3)=3，σ(1)=4就是A上的一个置换。
设σ为A={a1, a2, …, an}的一个置换： a2=σ(a1)， a3=σ(a2)，…，an=σ(an−1)，则称σ为A上的一个轮换。
【例2】例1中，由于σ(2)=1，σ(1)=4，σ(4)=2，故σ可视为A的子集合A1={2，1，4}上的一个轮换σ1。
【例3】单元素集合A={a}上的恒等变换σ(a)=a视为轮换。
置换与轮换之间有如下的重要命题。
定理1-2
集合A={a1, a2, …, an}上的任何一个置换σ，均可唯一[5]地分解成A的若干个两两不相交的子集上的轮换，且这些子集的并即为A。
【例4】例1中A={2，4，3，1}上的置换σ可以分解成例2中A1上的σ1：2→1，1→4，4→2和A2={3}上的恒等变换σ2：3→3，且A= A1∪A2，A1∩A2=Ø。
定理1-2的证明如下。
对集合A所含的元素个数n做数学归纳。当n=1时，A上的任何变换就是恒等变换，所以本身就是一个轮换。对n>1，假定对元素个数k<n的集合，命题为真。下证元素个数为n的集合，命题亦为真。任取ai1∈A，设ai2=σ(ai1)，ai3=σ(ai2)，……，由于变换σ是单射，且A是有限集，因此这个首尾相接的映射链必存在1kn，使得ai1=σ(aik)。这就得到了一个{ai1, ai2, …, aik}=A1⊆A上的一个轮换。若k=n，则σ本身就是一个轮换，命题为真。今设1k<n，将上述A1上的轮换记为σ1。记A2=A−A1，则A2的元素个数为n−k<n。根据归纳假设，σ限制在A2上必可分解成若干个轮换。连同σ1，我们得到σ的分解。由于将σ限制在A1上得到变换是唯一的，根据归纳假设，A2上的分解也是唯一的，于是连同σ1，我们得到σ在A上的分解是唯一的。
问题描述
农夫John有N（1 N 10 000）头牛妞，晚上她们要排成一排挤奶。每个牛妞拥有唯一的一个值介于1～100000的表示其暴脾气程度的指标。由于暴脾气的牛妞更容易损坏John的挤奶设备，所以John想把牛妞们按暴脾气指数的升序（从小到大）重排牛妞们。在此过程中，两个牛妞（不必相邻）的位置可能被交换，交换两头暴脾气指数为X、Y的牛妞的位置要花费X+Y个时间单位。
请你帮助John计算出重排牛妞所需的最短时间。
输入
输入文件中包含若干个测试案例数据。每个测试案例由两行数据组成：
第1行是一个表示牛妞个数的整数N。
第2行含N个用空格隔开的整数，表示每个牛妞的暴脾气指数。
N=0是输入数据结束的标志。对此案例无需做任何处理。
输出
对每一个测试案例输出一行包含一个表示按暴脾气指数升序重排牛妞所需的最少时间的整数。
输入样例
3
2 3 1
6
4 3 1 5 2 6
0输出样例
7
18解题思路
（1）数据的输入与输出
本问题输入文件包含若干个测试案例，每个案例的输入数据有两行：第1行含有1个表示牛妞个数的整数N，第2行含有N个表示诸牛妞脾气指数的整数。N=0为输入数据结束标志。可以将案例中牛妞脾气指数组织成一个数组，对此数组计算按脾气指数升序排列重排牛妞的最小代价。将计算所得结果作为1行写入输出文件。
1 打开输入文件inputdata
2 创建输出文件outputdata
3 从inputdata中读取人数N
4 while N≠0
5 do 创建数组a[1..N]
6 for i←1 to N
7 do 从inputdata中读取a[i]
8 result←COW-SORTING(a)
9 将result作为一行写入outputdata
10 从inputdata中读取案例数据N
11 关闭inputdata
12 关闭outpudata
其中，第8行调用过程COW-SORTING(a)计算将牛妞们按脾气指数升序排序所花的最小代价，是解决一个案例的关键。
（2）处理一个案例的算法过程
对于一个案例，设置计数器count，初始化为0。设n个牛妞的脾气指数为a1, a2, …, an，按升序排列为a'1, a'2, …, a'n。这实际上就是集合A={a1, a2, …, an}上的一个置换σ。按定理1-2知，该置换可表示为A的m（1mn）个两两不相交子集A1，A2，…，Am（且
）上的轮换σ1，σ2，…，σm。利用定理1-2的证明中的构造方法，依次分解出每个子集Ai={ai1, ai2, …, aik}（1im），若Ai是单元素集合，则定义在其上的轮换就是恒等变换，不发生任何代价。今设k>0，直接完成轮换即ai1→ai2→…→aik→ai1。每个元素都参加2次交换，故代价为
。设{ai1, ai2, …, aik}中的最小者为ti，利用该元素做如下的对换：将ti与应该在其位置上元素交换。这样，除了ti本身，每个元素都按这样的方式做了一次交换，从而到达了合适的位置，而ti做了k−1次交换，故代价为
。这显然比优越，但是有一种情况也许比这更好：将A={a1, a2, …, an}中的最小值元素amin先与上述{ai1, ai2, …, aik}中的最小元素ti交换，产生代价amin+ti。然后按上述方式进行操作，产生代价
。最后再amin将与ti交换，产生代价amin+ti。将三者相加得到此方式的总代价：
。这样，我们只需选取min{，
}即为完成子集{ai1, ai2, …, aik}对换的最小代价。按此方法将每个子集对换的最小代价累加到计数器count中，即为案例所求。将算法思想表达为伪代码过程如下。
COW-SORTING(a)
1 n←length[a], count←0
2 copy a to b
3 SORT(b)
4 amin←b[1]
5 while n>0
6 do j←a中首个非0元素下标
7 ti←∞, sum←a[j]
8 k←1, ai←a[j]
9 a[j]←0, n←n-1
10 while b[j]≠ai
11 do k←k+1
12 sum←sum+b[j]
13 if ti>b[j]
14 then ti←b[j]
15 j←FIND(a, b[j])
16 a[j]←0, n←n-1
17 if k>1
18 then count←count+sum+min{(k-2)*ti, (k+1)*amin}
19 return count
算法1-12 计算将牛妞们按脾气指数升序重排的最小代价的算法过程
算法中设置b为数组a按升序排序的结果（第2～3行）。a、b元素之间的对应关系是根据对应下标确定的，即
（1in）。第5～18行的while循环每次重复构造A的一个轮换子集，并计算完成该子集元素交换的最小代价，累加到计数器count（第1行初始化为0）中。具体地说，第6行取a中未曾访问过的元素（a中访问过的元素置为0）下标为j，设新的子集上轮换的首元素ai。第10～15行的while循环按条件b[j]≠ai重复，构造一个轮换子集。一旦该条件为假（b[j]=ai）意味着轮换完成。在构造过程中，第11行子集元素个数k自增1，第12行将新发现的元素添加到和sum（第7行初始化为该子集的首元素ai）中，第13～14行跟踪该子集的最小元素ti（第7行初始化为∞）。第15行找出下一个对应元素下标j，第16行将已经完成访问的a[j]置为0，且将尚未访问过的元素个数n（第1行初始化为a的元素个数）自减1。一旦完成一个轮换子集的构造（第10～16行的while循环结束），第17～18行根据子集元素个数k是否大于1，按此前讨论的公式决定count的增加值。
算法的运行时间取决于第11～16行操作被重复的次数。由于每次重复a中的一个元素值被值为0，而外层循环条件为a中非0元素个数n>0，所以第11～16行的操作一定被重复a的元素个数次N（即牛妞的个数）。在11～16行的各条操作中，第15行调用FIND过程在a中查找值为b[j]的元素下标，这将花费O(N)时间，所以整个算法的运行时间是O(N2)。
解决本问题的算法的C++实现代码存储于文件夹laboratory/Cow Sorting中，读者可打开文件CowSorting.cpp研读，并试运行之。C++代码的解析请阅读第9章9.4.2节中程序9-53的说明。
计数问题是最基本、最常见的计算问题。本章通过解决10个计算问题讨论了解决计数问题的几个常用的算法设计方法，包括累积法（问题1-1、问题1-2、问题1-3和问题1-4）、数学计算法（问题1-5、问题1-6和问题1-7）、加法原理和乘法原理（问题1-8）、图的性质（问题1-9）和置换与轮换（问题1-10）。
[1] 见本书0.5节。
[2] 见本书0.6节。
[3] 参阅本书第7章节7.3。
[4] 。
[5] 此处的唯一性指的是将轮换作为元素构成的集合是唯一的。
