基础算法教案  目录

第一课 算法简介... 1

第二课 多精度数值处理... 1

第三课 排列与组合... 6

第五课 递归与回溯法... 25

算法是一组（有限个）规则它为某个特定问题提供了解决问题的运算序列。在信息学竞赛中就是计算机解题的过程。在这个过程中无论是形成解题思路还是编写算法，都是在实施某种算法前者是推理实現的算法，后者是操作实现的算法

计算机解题的核心是算法设计。一个算法应该具有以下五个重要特征：

③       输入：一个算法有零个或多個输入以描述运算对象的初始情况。所谓0个输入是指算法本身给出了初始条件；

④       输出：一个算法有一个或多个输出以反映对输入数據处理后的结果。没有输出的算法是毫无意义的；

为了获得一个既有效又优美的算法必须首先了解一些基本的常用算法设计思路。下面我们就对构成算法所依据的一些基本方法展开讨论，如递推法递归法，枚举法分治法，模拟法贪心法等。

第二课 多精度数值处理

課题：多精度数值的处理

知识目标：多精度值的加、减、乘、除

能力目标：多精度值的处理优化！

重点：多精度的加、减、乘

1）  输入两個正整数，求它们的和

2）  输入两个正整数求它们的差

3）  输入两个正整数，求它们的积

4）  输入两个正整数求它们的商

所谓多精度值处理，就是在对给定的数据范围用语言本身提供的数据类型无法直接进行处理（主要指加减乘除运算），而需要采用特殊的处理办法进行看看下面的例子。

例1 从键盘读入两个正整数求它们的和。

分析：从键盘读入两个数到两个变量中然后用赋值语句求它们的和，输出泹是，我们知道在pascal语言中任何数据类型都有一定的表示范围。而当两个被加数据大时上述算法显然不能求出精确解，因此我们需要寻求另外一种方法在读小学时，我们做加法都采用竖式方法如图1。

这样我们方便写出两个整数相加的算法。

如果我们用数组A、B分别存儲加数和被加数用数组C存储结果。则上例有

{ a,b,c都为数组a存储被加数，b存储加数c存储结果 }

通常，读入的两个整数用可用字符串来存储程序设计如下：

从键盘读入两个正整数，求它们的差

       分析：类似加法，可以用竖式求减法在做减法运算时，需要注意的是：被减数必須比减数大同时需要处理借位。

因此可以写出如下关系式

类似，高精度减法的参考程序：

从键盘读入两个正整数求它们的积。

       分析：类似加法可以用竖式求乘法。在做乘法运算时同样也有进位，同时对每一位进乘法运算时必须进行错位相加，如图3, 图4

分析C数组丅标的变化规律，可以写出如下关系式

由此可见C _i跟A[i]*B[j]乘积有关，跟上次的进位有关还跟原C _i的值有关，分析下标规律有

类似，高精度乘法的参考程序：

从键盘读入两个正整数求它们的商（做整除）。

       分析：做除法时每一次上商的值都在０～９，每次求得的余数连接以後的若干位得到新的被除数继续做除法。因此在做高精度除法时，要涉及到乘法运算和减法运算还有移位处理。当然为了程序简潔，可以避免高精度乘法用0～9次循环减法取代得到商的值。这里我们讨论一下高精度数除以单精度数的结果，采取的方法是按位相除法

实质上，在做两个高精度运算时候存储高精度数的数组元素可以不仅仅只保留一个数字，而采取保留多位数（例如一个整型或长整型数据等）这样，在做运算（特别是乘法运算）时可以减少很多操作次数。例如图5就是采用4位保存的除法运算其他运算也类似。具體程序可以修改上述例题予以解决程序请读者完成。

知识目标：如何利用程序就各种排列和组合

能力目标：排列组合的运用

重点：求出n嘚全排列和从m中取n个的组合

例5：有3个人排成一个队列问有多少种排对的方法，输出每一种方案

分析：如果我们将3个人进行编号，分别為1、2、3显然我们列出所有的排列，123132，213231，312321共六种。可用循环枚举各种情况参考程序：

上述情况非常简单，因为只有3个人但当有N個人时怎么办？显然用循环不能解决问题下面我们介绍一种求全排列的方法。

设当前排列为P₁ P₂ ,…,P_n则下一个排列可按如下算法完成：

1．求滿足关系式P_j-1 < P_j的J的最大值，设为I即

2．求满足关系式P_{i -1} < P_k的k的最大值，设为j即

4．4321的321部分逆转得到4123即是3421的下一个排列。

例6：求N个人选取M个人出来莋游戏共有多少种取法？例如：N=4M=2时，有1213，1423，2434共六种。

分析：因为组合数跟顺序的选择无关因此对同一个组合的不同排列，只需取其最小的一个（即按从小到大排序）因此，可以设计如下算法：

1．最后一位数最大可达N倒数第二位数最大可达N-1，…依此类推，倒数第K位数最大可达N-K+1

2．当存在C_j<N-R+J时，其中下标的最大者设为I即

知识目标：枚举算法的本质和应用

能力目标：枚举算法的应用！

重点：利鼡枚举算法解决实际问题

难点：枚举算法的次数确定

1）  简单枚举（例7、例8、例9）

2）  利用枚举解决逻辑判断问题（例10、例11）

3）  枚举解决竞赛問题（例12、例13、例14）

所谓枚举法,指的是从可能的解集合中一一枚举各元素,用题目给定的检验条件判定哪些是无用的,哪些是有用的.能使命题荿立,即为其解。一般思路：

枚举法的特点是算法简单但有时运算量大。对于可能确定解的值域又一时找不到其他更好的算法时可以采用枚举法

例7：求满足表达式A+B=C的所有整数解，其中AB，C为1~3之间的整数

分析：本题非常简单，即枚举所有情况符合表达式即可。算法如下：

上例采用的就是枚举法所谓枚举法，指的是从可能的解的集合中一一枚举各元素用题目给定的检验条件判定哪些是无用的，哪些是囿用的能使命题成立的，即为解

从枚举法的定义可以看出，枚举法本质上属于搜索但与隐式图的搜索有所区别，在采用枚举法求解嘚问题时必须满足两个条件：

例7中的解变量有3个：A，BC。其中

A解变量值的可能取值范围A∈{12，3}

B解变量值的可能取值范围B∈{12，3}

C解变量值嘚可能取值范围C∈{12，3}

则问题的可能解有27个

（AB，C）∈{（11，1）（1，12），（11，3）

在上述可能解集合中，满足题目给定的检验条件嘚解元素即为问题的解。

如果我们无法预先确定解的个数或各解的值域则不能用枚举，只能采用搜索等算法求解由于回溯法在搜索烸个可能解的枚举次数一般不止一次，因此对于同样规模的问题，回溯算法要比枚举法时间复杂度稍高

例8 给定一个二元一次方程aX+bY=c。从鍵盘输入a,b,c的数值求X在[0，100]Y在[0，100]范围内的所有整数解

       分析：要求方程的在一个范围内的解，只要对这个范围内的所有整数点进行枚举看这些点是否满足方程即可。参考程序：

从上例可以看出所谓枚举法,指的是从可能的解集合中一一枚举各元素,用题目给定的检验条件判萣哪些是无用的,哪些是有用的.能使命题成立,即为其解。

    将1～9这九个数字填入九个空格中每一横行的三个数字组成一个三位数。如果要使苐二行的三位数是第一行的两倍, 第三行的三位数是第一行的三倍, 应怎样填数如图6:

分析：本题目有9个格子，要求填数如果不考虑问题给絀的条件，共有9！=362880种方案在这些方案中符合问题条件的即为解。因此可以采用枚举法

但仔细分析问题，显然第一行的数不会超过400实際上只要确定第一行的数就可以根据条件算出其他两行的数了。这样仅需枚举400次因此设计参考程序：

例10 在某次数学竞赛中, A、B、C、D、E五名學生被取为前五名。请据下列说法判断出他们的具体名次, 即谁是第几名

条件1: 你如果认为A, B, C, D, E 就是这些人的第一至第五名的名次排列, 便大错。洇为:

没猜对任何一个优胜者的名次

也没猜对任何一对名次相邻的学生。

说对了其中两个人的名次

还猜中了两对名次相邻的学生的名次順序。

分析：本题是一个逻辑判断题一般的逻辑判断题都采用枚举法进行解决。5个人的名次分别可以有5！=120种排列可能因为120比较小，因此我们对每种情况进行枚举然后根据条件判断哪些符合问题的要求。

{ABCDE没猜对一个人的名次}

{DAECB猜对了两个人的名次}

{ABCDE没猜对一对相邻名次}

{DAECB猜对叻两对相邻人名次}

例11：来自不同国家的四位留学生A,B,C,D在一起交谈,他们只会中、英、法、日四种语言中的2种,情况是, 没有人既会日语又会法语;A会ㄖ语,但D不会,A和D能互相交谈,B不会英语,但A和C交谈时却要B当阴使人求义士可共成事者翻译,B,C,D三个想互相交谈,但找不到共同的语言,只有一种语言3人都會,编程确定A,B,C,D四位留学生各会哪两种语言

分析：将中、法、日、英四种语言分别定义为CHN、FRH、JPN、ENG,则四种语言中取两种共有(CHN,ENG),（CHN,FRH）,(CHN,JPN),( ENG,FRH),( ENG,JPN),(FRH,JPN)六种组合，分別定义为1、2、3、4、5、6据已知，没有人既会日语又会法语;因此组合6不会出现；A 会日语，所以A只可能等于3、5；D不会日语, 所以D只可能等于1、2、4；B不会英语所以B只可能等于2、3；见下表。如果我们对A、B、C、D分别进行枚举根据判定条件，即可找到答案

在一位数学家的藏书中夹囿一张古旧的纸片。纸片上的字早已模糊不清了, 只留下曾经写过字的痕迹, 依稀还可以看出它是一个乘法算式, 如图7所示这个算式上原来的數字是什么呢？夹着这张纸片的书页上,“素数”两个字被醒目的划了出来难道说, 这个算式与素数有什么关系吗？有人对此作了深入的研究, 果然发现这个算式中的每一个数字都是

素数, 而且这样的算式是唯一的请你也研究一番, 并把这个算式写出来。

分析：实际上只要知道塖数和被乘数就可以写出乘法算式，所以我们可以枚举乘数与被乘数的每一位然后再判断是不是满足条件即可。计算量是4⁵=1024对于计算机來说，计算量非常小

是不是都是由素数组成}

{它们分别是两个四位数，一个五位数}

{满足其他数都是由质数构成}

在图8所示的3*3矩阵中有9个时钟我们的目标是旋转时钟指针，使所有时钟的指针都指向12点允许旋转时钟指针的方法有9种，每一种移动用一个数字号（12，…9）表示。图2-11示出9个数字号与相应的受控制的时钟这些时钟在图中以灰色标出，其指针将顺时针旋转90度

由输入文件INPUT.TXT读9个数码，这些数码给出了9個时钟时针的初始位置数码与时刻的对应关系为：

图2-11中的例子对应下列输入数据：

将一个最短的移动序列（数字序列）写入输出文件OUTPUT.TXT中，该序列要使所有的时钟指针指向12点若有等价的多个解，仅需给出其中一个在我们的例子中，相应的OUTPUT.TXT的内容为：

具体的移动方案如图10所示

首先，我们分析一下表示时钟时针初始位置的数码j（0≦j≦3）与时刻的对应关系：

每移动一次时针将顺时针旋转90度。由此我们可以嘚出：

对于任意一个时钟i（1≦i≦9）来说从初始位置j出发至少需要C_i=（4-j） mod 4次操作，才能使得时针指向12点而对每种移动方法要么不采用，要麼采用1次、2次或3次因为操作四次以后，时钟将重复以前状态因此，9种旋转方案最多产生4⁹个状态

移动方案选取与顺序无关。样例中朂佳移动序列为5849，同样4589序列也可达到目标因此，求解过程中可以直接选取序列中从小至大排列的移动序列即可

设 p_i表示第i种旋转方法的使用次数（0≦p_i≦3，1≦i≦9）

则可能的解的集合为{P₁，P₂……，P₉}该集合共含4⁹个状态。从图2.11中我们可以分析出9个时钟分别被哪些方法所控制，见下表：

因此我们可以设计如下枚举算法：

显然上述枚举算法枚举了所有4⁹=262144个状态，运算量和运行时间颇大我们可以采取缩小可能解范围的局部枚举法，仅枚举第1、2、3种旋转方法可能取的4³个状态根据这三种旋转方法的当前状态值，由下述公式

得出其余P₄……P₉的相应状态徝然后将P₁，P₂…，P₉代入下述三个检验条件

一一枚举以求得确切解。

由此可见上述局部枚举的方法（枚举状态数为4³个）比较全部枚举嘚方法（枚举状态数为4⁹个）来说，由于大幅度削减了枚举量减少运算次数，因此其时效显著改善是一种优化了的算法。

    {读入9个时钟指針的初始位置求出每个时钟从初始到12点的最少移动次数}

在上例中，由于事先能够排除那些明显不属于解集的元素使得算法效率非常高。而减少重复运算、力求提前计算所需数据、使用恰当的数据结构进行算法优化等方法也是优化枚举算法的常用手段

例14：最佳游览线路 （NOI94）

某旅游区的街道成网格状（图2.13）。其中东西向的街道都是旅游街南北向的街道都是林荫道。由于游客众多旅游街被规定为单行道，游客在旅游街上只能从西向东走在林阴道上则既可从南向北走，也可以从北向南走

阿龙想到这个旅游区游玩。他的好友阿福给了他┅些建议用分值表示所有旅游街相邻两个路口之间的街道值得游览的程度，分值时从-100到100的整数所有林阴道不打分。所有分值不可能全昰负分

例如图11是被打过分的某旅游区的街道图：

阿龙可以从任一个路口开始游览，在任一个路口结束游览请你写一个程序，帮助阿龙找一条最佳的游览线路使得这条线路的所有分值总和最大。

输入文件是INPUT.TXT文件的第一行是两个整数M和N，之间用一个空格符隔开M表示有哆少条旅游街（1≦M≦100），N表示有多少条林阴道（1≦M≦20001）接下来的M行依次给出了由北向南每条旅游街的分值信息。每行有N-1个整数依次表礻了自西向东旅游街每一小段的分值。同一行相邻两个数之间用一个空格隔开

输出文件是OUTPUT.TXT。文件只有一行是一个整数，表示你的程序找到的最佳游览线路的总分值

我们将网格状的旅游区街道以林荫道为界分为N – 1个段，每一段由M条旅游街的对应段成即第J段成为{L_1J，L_2J……，L_MJ}（1≦ J ≦ N – 1）由于游览方向规定横向自西向东，纵向即可沿林阴道由南向北亦可由北向南，而横行的街段有分值纵行无分值，因此最佳游览路现必须具备如下三个特征：

设L_i为第I个段中的分值最大的段即L_i=Max{L_1I，L_2I……，L_MI}（1≦I≦N – 1）例如对于样例数据：

有了以上的基础，我们便可以通过图示描述解题过程见图12。

我们把将段设为顶点所在段的最大分值设为顶点的权，各顶点按自西向东的顺序相连组荿一条游览路线。显然如果确定西端为起点、东段为终点，则这条游览路线的总分值最大

问题是某些段的最大分值可能是负值，而最優游览路线的起点和终点任意在这种情况下，上述游览路线就不一定最佳了因此，我们只能枚举这条游览路线的所有可能的子路线從中找出一条子路线IàI+1à……àJ（1 ≦ I<J ≦ N – 1），使得经过顶点的权和L_I+L_I+1+……+L_J最大

设Best为最佳游览路线的总分值，初始时为0；

Sum为当前游览路线的总汾值

我们可以得到如下算法：

显然，这个算法的时间复杂度为O（N²）而N在1~20001之间，时间复杂度比较高于是，我们必须对这个算法进行优囮

仍然从顶点1开始枚举最优路线。若当前子路线延伸至顶点I时发现总分值Sum≦0则应放弃当前子路线。因为无论L_I+1为何值当前子路线延伸臸顶点I+1后的总分值不会大于LI+1。因此应该从顶点I+1开始重新考虑新的一条子路线通过这种优化，可以使得算法的时间复杂度降到了O（N）

优囮后的算法描述如下:

{旅游街数和林阴道数}

{最佳游览路线的总分值}

{读入旅游街数和林阴道数}

{当前游览路线的总分值}

{统计当前游览路线的总分徝}

知识目标：递归概念与利用递归进行回溯

能力目标：回溯算法的应用

2）  利用递归回溯解决实际问题（例14、例15、例16、例17、例18）

3）  利用回溯算法解决排列问题（例19）

什么是递归？先看大家都熟悉的一个民间故事：从前有座山山上有座庙，庙里有一个老和尚在给小和尚讲故事故事里说，从前有座山山上有座庙，庙里有一个老和尚在给小和尚讲故事故事里说……。象这样一个对象部分地由它自己组成，戓者是按它自己定义我们称之是递归。

例如我们可以这样定义N!，N!=N*(N-1)!因此求N!转化为求 (N-1)!。这就是一个递归的描述

因此，可以编写如下递歸程序：

图13展示了N=3的执行过程由上述程序可以看出，递归是一个反复执行直到递归终止的过程

设一个未知函数f，用其自身构成的已知函数g来定义：

为了定义f(n)必须先定义f(n-1)，为了定义f(n-1)又必须先定义f(n-2) ，…上述这种用自身的简单情况来定义自己的方式称为递归定义。

与递嶊一样每一个递推都有其边界条件。但不同的是递推是由边界条件出发，通过递推式求f(n)的值从边界到求解的全过程十分清楚；而递歸则是从函数自身出发来达到边界条件，在通过边界条件的递归调用过程中系统用堆栈把每次调用的中间结果（局部变量和返回地址）保存起来，直至求出递归边界值f(0)=a然后返回调用函数。返回的过程中中间结果相继出栈恢复，f(1)=g(1,a)àf(2)=g(2,f(1))à……à直至求出f(n)=g(n,f(n-1))

由此可见递归算法的效率往往很低，费时和费内存空间但是递归也囿其长处，它能使一个蕴含递归关系且结构复杂的程序简洁精炼增加可读性。特别是在难于找到从边界到解的全过程的情况下如果把問题进一步，其结果仍维持原问题的关系则采用递归算法编程比较合适。

递归算法适用的一般场合为：

① 数据的定义形式按递归定义

洳裴波那契数列的定义：

这类递归问题可转化为递推算法，递归边界为递推的边界条件例如上例转化为递推算法即为

② 数据之间的关系（即数据结构）按递归定义。如树的遍历图的搜索等。

③ 问题解法按递归算法实现例如回溯法等。

对于②和③可以用堆栈结构将其轉换为非递归算法，以提高算法的效率以及减少内存空间的浪费

下面以经典的N皇后问题为例，看看递归法是怎样实现的以及比较递归算法和非递归算法效率上的差别。

在N*N的棋盘上放置N个皇后而彼此不受攻击（即在棋盘的任一行任一列和任一对角线上不能放置2个皇后），编程求解所有的摆放方法

由于皇后的摆放位置不能通过某种公式来确定，因此对于每个皇后的摆放位置都要进行试探和纠正这就是“回溯”的思想。在N个皇后未放置完成前摆放第I个皇后和第I+1个皇后的试探方法是相同的，因此完全可以采用递归的方法来处理

下面是放置第I个皇后的的递归算法：

{搜索第I行皇后的位置}

 对放置皇后的位置释放标记；

N皇后问题的递归算法的程序如下：

{搜索第I个皇后的可行位置}

N皇后问题的非递归算法的程序：

{继续放置下一个皇后}

使用递归可以使蕴含复杂关系的问题，结构变得简洁精炼看看下面的例题。

例16:新漢诺（hanoi）塔问题

设有n各大小不等的中空圆盘按从小到大的顺序从1到n编号。将这n个圆盘任意的迭套在三根立柱上立柱的编号分别为A、B、C，这个状态称之为初始状态问题要求找到一种步数最少的移动方案，使得从初始状态转变为目标状态移动时有如下要求：

输入：输入攵件第1行是状态中圆盘总数；第2~4行是分别是初始状态中A、B、C柱上的圆盘个数和从上到下每个圆盘的编号；第5~7行是分别是目标状态A、B、C柱上嘚圆盘个数和从上到下每个圆盘的编号。

输出：每行写一步的移动方案格式为：

样例所描述的状态如图15所示。

要从初始状态移动到目标狀态就是把每个圆盘分别移动到自己的目标状态。而问题的关键一步就是：首先考虑把编号最大的圆盘移动到自己的目标状态而不是朂小的，因为编号最大的圆盘移到目标位置之后就可以不再移动了而在编号最大的圆盘未移到目标位置之前，编号小的圆盘可能还要移動编号最大的圆盘一旦固定，对以后的移动将不会造成影响

根据上面的分析可设计如下过程

表示把编号K的圆盘从当前所在柱移动到W柱嘚过程。

将6号盘移动到B柱在此之前一定将经历如图16所示的状态

要移动6号盘首先要把1~5号盘全部移开，也就是说既不能移动到6号盘的初始竝柱上，也不能移动到6号盘的目标立柱上显然这里要将它们移动到A柱。然后再将6号盘移到位此时状态如图17所示。

同时我们注意到：把1~5盤移动到目标的过程和将6号盘移动到B柱的过程从形式上是一样的，只是盘的编号不同而已显然这是个递归过程，可以采用递归法实现

{编号K的圆盘从当前所在柱移动到W柱}

{将K号盘移动到目标位置}

已知一个容量大小为M重量的背包和N种物品，每种物品的重量为Wi若将物品放入褙包将得到Pi的效益，求怎样选取物品将得到效益最大

分析：本题可以用递归求解：设当前有N个物品容量为M；因为这些物品要么选，要么鈈选我们假设选的第一个物品编号为I（1~I-1号物品不选），问题又可以转化为有N-I个物品（即第I+1~N号物品）容量为M-Wi的子问题……如此反复下去，然后在所有可行解中选一个效益最大的便可

另外，为了优化程序我们定义一个函数如下：

F[I]表示选第I~N个物品能得到的总效益。不难推絀：

假设当前已选到第I号物品如果当前搜索的效益值+F[I+1]的值仍然比当前的最优值小，则没有必要继续搜索下去

{Ou，Out数组记录选择物品的具體方案}

给出一个矩阵及一些国都名：

要求从这个矩阵中找出这些国都名并输出它们的起始位置及方向。

输入：在文本文件input.txt中的第一行有┅个整数M和N表示该字符矩阵的长和宽。接下来就是M*N的字符矩阵字符矩阵后有一个整数K，表示国家都名的个数接下来的K行，每一行都昰一个国都名

输出：在文本文件output.txt中共有K行，第I行写入第I个国都名的起始位置及方向起始位置用坐标表示，方向定义见图18如没有找到國都名，输出‘No found’

分析：将字符矩阵读入到二维数组，然后对每一个国都名进行搜索首先需要在矩阵中找到国都名的第一个字符，然後沿八个方向进行搜索直到找到国都名为止。若在矩阵中没有找到则输出相应的信息。

在搜索过程时类似八皇后问题，建立一个标誌数组标识已经搜索过的方向，在对八个方向搜索时可以建立一个方向数组，使得程序更加简洁明了

{为了节约边界条件的判断，故增加边界范围}

{采用重定向的手段将输入文件与标准输入联系起来，

这样对标准输入（键盘）的操作相当对输入文件的操作}

{采用重定向嘚手段，将输出文件与标准输出联系起来

这样对标准输出（屏幕）的操作，相当对输出文件的操作}

{搜索路径T为国都名的字符位置，XY為当前搜索的坐标}

例19采用递归方法，求N个元素中取出M个的排列。

（1）每个元素只能取一次

（2）每个元素可以取任意多次（即可重复的排列）。

分析：此题用简单的递归搜索设x[I]排列中的第I个元素，依次搜索每一个x[I]即可

{继续搜索排列的下一个}

知识目标：递推概念与利用递嶊解决实际问题

递推就是逐步推导的过程我们先看一个简单的问题。

例20：一个数列的第0项为0第1项为1，以后每一项都是前两项的和这個数列就是著名的裴波那契数列，求裴波那契数列的第N项

分析：我们可以根据裴波那契数列的定义：从第2项开始，逐项推算直到第N项。因此可以设计出如下算法：

从这个问题可以看出在计算裴波那契数列的每一项目时，都可以由前两项推出这样，相邻两项之间的变囮有一定的规律性我们可以将这种规律归纳成如下简捷的递推关系式：F_n=g(F_n-1)，这就在数的序列中建立起后项和前项之间的关系。然后从初始条件（或是最终结果）入手按递推关系式递推，直至求出最终结果（或初始值）很多问题就是这样逐步求解的。

对一个试题我们偠是能找到后一项与前一项的关系并清楚其起始条件（或最终结果），问题就可以递推了接下来便是让计算机一步步了。让高速的计算機从事这种重复运算真正起到“物尽其用”的效果。

递推分倒推法和顺推法两种形式算法流程如下：

所谓倒推法，就是在问题的解或目标是由初始值递推得到的问题中已知解或目标，根据递推关系采用倒推手段，一步步的倒推直至求得这个问题的初始陈述的方法因为这类问题的运算过程是一一映射的，故可分析其递推公式看看下面的例题。

一辆重型卡车欲穿过1000公里的沙漠卡车耗汽油为1升/公里，卡车总载油能力为500公升显然卡车装一佽油是过不了沙漠的。因此司机必须设法在沿途建立若干个贮油点使卡车能顺利穿过沙漠。试问司机如怎样建立这些贮油点每一贮油點应存储多少汽油，才能使卡车以消耗最少汽油的代价通过沙漠

编程计算及打印建立的贮油点序号，各贮油点距沙漠边沿出发的距离以忣存油量格式如下：

设Way[I]——第I个贮油点到终点（I=0）的距离；

oil[I]——第I个贮油点的贮油量；

我们可以用倒推法来解决这个问题。从终点向始點倒推逐一求出每个贮油点的位置及存油量。图19表示倒推时的返回点

从贮油点I向贮油点I+1倒推的方法是：卡车在贮油点I和贮油点I+1间往返若干次。卡车每次返回I+1点时应该正好耗尽500公升汽油而每次从I+1点出发时又必须装足500公升汽油。两点之间的距离必须满足在耗油最少的条件丅使I点贮足I*500公升汽油的要求（0≦I≦n-1）。具体来说第一个贮油点I=1应距终点I=0处500km，且在该点贮藏500公升汽油这样才能保证卡车能由I=1处到达终點I=0处，这就是说

此时的状况如图20所示

为了在I=2处贮藏1000公升汽油，卡车至少从I=3处开三趟满载油的车至I=2处所以I=3处至少贮有3*500公升汽油，即oil[3]=500*3=1500加仩I=2至I=3处的二趟返程空车，合计5次路途耗油亦应500公升，即d₂₃=500/5

此时的状况如图21所示。

此时的状况如图22所示

{置始点到终点的距离值}

顺推法是從边界条件出发，通过递推关系式推出后项值再由后项值按递推关系式推出再后项值……，依次类推直至从问题初始陈述向前推进到這个问题的解为止。

科学家在热带森林中发现了一种特殊的昆虫这种昆虫的繁殖能力很强。每对成虫过x个月产y对卵每对卵要过两个月長成成虫。假设每个成虫不死第一个月只有一对成虫，且卵长成成虫后的第一个月不产卵(过X个月产卵)问过Z个月以后，共有成虫多少对x>=1,y>=1,z>=x

输入：x,y,z的数值

分析：首先我们来看样例：每隔1个月产2对卵，求过8月（即第8+1=9月）的成虫个数

设数组A[i]表示第I月新增的成虫个数

由于新成虫烸过x个月产y对卵，则可对每个A[I]作如下操作:

因为A [i]的求得只与A[1]~A[i-1]有关即可用递推求法。

例23：实数数列（NOI94第3题）

一个实数数列共有N项已知

键盘輸入N，da₁，a_nm，输出a_m

变形得，a_i+1=a_i-1-2a_i+2d因此该数列的通项公式为：a_i=a_i-2-2a_i-1+2d，已知a₁如果能求出a₂，这样就可以根据公式递推求出a_m

一直迭代下去直到最後，可以建立a_i和a₁与a₂的关系式

将初值P₁、Q₁、R₁和P₂、Q₂、R₂代入②③④可以求出P_n、Q_n、R_n

然后根据公式①递推求出a_m，问题解决

但仔细分析，上述算法有┅个明显的缺陷：在求由于在求a₂要运用除法因此会存在实数误差，这个误差在以后递推求a_m的过程又不断的扩大在实际中，当m超过30时求出的a_m就明显偏离正确值。显然这种算法虽简单但不可靠。

为了减少误差我们可设计如下算法：

根据公式⑤，可以顺推a₂、a₃、…、a_M虽嘫仍然存在实数误差，但由于P_n-k+2递减因此最后得出的a_m要比直接利用公式①精确得多。

知识目标：贪心的原理递与贪心的实现

若在求解一个問题时能根据每次所得到的局部最优解，推导出全局最优或最优目标那么，我们可以根据这个策略每次得到局部最优解答，逐步而嶊导出问题这种策略称为贪心法。

下面我们看一些简单例题

例24：在N行M列的正整数矩阵中，要求从每行中选出1个数使得选出的总共N个數的和最大。

分析：要使总和最大则每个数要尽可能大，自然应该选每行中最大的那个数因此，我们设计出如下算法:

读入N, M,矩阵数据；

  選择第I行最大的数,记为K；

输出最大总和Total；

从上例中我们可以看出和递推法相仿，贪心法也是从问题的某一个初始解出发向给定的目标遞推。但不同的是推进的每一步不是依据某一固定的递推式，而是做一个局部的最优选择即贪心选择（在例中，这种贪心选择表现为選择一行中的最大整数）这样，不断的将问题归纳为若干相似的子问题最终产生出一个全局最优解。

特别注意的是是局部贪心的选擇是否可以得出全局最优是能否采用贪心法的关键所在。对于能否使用贪心策略应从理论上予以证明。下面我们看看另一个问题

给定┅个最大载重量为M的卡车和N种食品，有食盐白糖，大米等已知第i种食品的最多拥有W_i公斤，其商品价值为V_i元/公斤编程确定一个装货方案，使得装入卡车中的所有物品总价值最大

分析：因为每一个物品都可以分割成单位块，单位块的利益越大显然总收益越大所以它局蔀最优满足全局最优，可以用贪心法解答方法如下：先将单位块收益按从大到小进行排列，然后用循环从单位块收益最大的取起直到鈈能取为止便得到了最优解。

因此我们非常容易设计出如下算法：

按V_i从大到小将商品排序；

在解决上述问题的过程中首先根据题设条件，找到了贪心选择标准(V_i)并依据这个标准直接逐步去求最优解，这种解题策略被称为贪心法

因此，利用贪心策略解题需要解决两个问題：

首先，确定问题是否能用贪心策略求解；一般来说适用于贪心策略求解的问题具有以下特点：

①   可通过局部的贪心选择来达到问题嘚全局最优解。运用贪心策略解题一般来说需要一步步的进行多次的贪心选择。在经过一次贪心选择之后原问题将变成一个相似的，泹规模更小的问题而后的每一步都是当前看似最佳的选择，且每一个选择都仅做一次

②   原问题的最优解包含子问题的最优解，即问题具有最优子结构的性质在背包问题中，第一次选择单位质量最大的货物它是第一个子问题的最优解，第二次选择剩下的货物中单位重量价值最大的货物同样是第二个子问题的最优解，依次类推

其次，如何选择一个贪心标准正确的贪心标准可以得到问题的最优解，茬确定采用贪心策略解决问题时不能随意的判断贪心标准是否正确，尤其不要被表面上看似正确的贪心标准所迷惑在得出贪心标准之後应给予严格的数学证明。

下面来看看0-1背包问题

给定一个最大载重量为M的卡车和N种动物。已知第i种动物的重量为W_i其最大价值为V_i，设定MW_i，V_i均为整数编程确定一个装货方案，使得装入卡车中的所有动物总价值最大

分析：对于N种动物，要么被装要么不装，也就是说在滿足卡车载重的条件下如何选择动物，使得动物价值最大的问题

从直观上来看，我们可以按照上例一样选择那些价值大而重量轻的動物。也就是可以按价值质量比（V_i/W_i）的大小来进行选择可以看出，每做一次选择都是从剩下的动物中选择那些V_i/W_i最大的，这种局部最优嘚选择是否能满足全局最优呢我们来看看一个简单的例子：

设N=3，卡车最大载重量是100三种动物A、B、C的重量分别是40，5070，其对应的总价值汾别是80、100、150

情况A：按照上述思路，三种动物的V_i/W_i分别为2,2,2.14显然，我们首先选择动物C得到价值150，然后任意选择A或B由于卡车最大载重为100，洇此卡车不能装载其他动物

情况B：不按上述约束条件，直接选择A和B可以得到价值80+100=180，卡车装载的重量为40+50=90没有超过卡车的实际载重，因此也是一种可行解显然，这种解比上一种解要优化

问题出现在什么地方呢？我们看看图2-18

从图23中明显可以看出情况A，卡车的空载率比凊况B高也就是说，上面的分析只考虑了货物的价值质量比，而没有考虑到卡车的运营效率因此，局部的最优化不能导致全局的最優化。

因此贪心不能简单进行，而需要全面的考虑最后得到证明。

有N个人排队到R个水龙头去打水他们装满水桶的时间为T1，T2…，Tn为整数且各不相等应如何安排他们的打水顺序才能使他们花费的时间最少？

分析：由于排队时越靠前面的计算的次数越多，显然越小的排在越前面得出的结果越小（可以用数学方法简单证明这里就不再赘述），所以这道题可以用贪心法解答基本步骤：

例27：旅行家的预算（NOI99分区联赛第3题）

一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱时空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途加油站数N（N可以为零）油站i离出发点的距离Di、烸升汽油价格Pi（i=1，2……，N）

计算结果四舍五入至小数点后两位。

如果无法到达目的地则输出“No Solution”。

26.95（该数据表示最小费用）

分析：需要考虑如下问题：

1）  出发前汽车的油箱是空的故汽车必须在起点（1号站）处加油。加多少油

2）  汽车行程到第几站开始加油，加多少油

可以看出，原问题需要解决的是在哪些油站加油和加多少油的问题对于某个油站，汽车加油后到达下一加油站可以归结为原问题嘚子问题。因此原问题关键在于如何确定下一个加油站。通过分析我们可以选择这样的贪心标准：

对于加油站I，下一个加油站J可能第┅个是比油站I油价便宜的油站若不能到达这样的油站，则至少需要到达下一个油站后继续进行考虑。

对于第一种情况则油箱需要（d（j）-d（i））/m加仑汽油。对于第二种情况则需将油箱加满。

Value[i]：第i个加油站的油价；

Over[i]：在第i站时的剩油；

Way[i]：起点到油站i的距离；

X[I]：X记录问题嘚最优解X[I]记录油站I的实际加油量。

若T<X[I]则汽车无法从起点到达第k个加油站；与假设矛盾。

若T<X[I]则表示在第I站的加油量会超过汽车的实际載油量，显然是不可能的

若T>X[I]，则表示在第I站的不加满油而将一部分油留待第K站加，而Value[I]<Value[k]所以这样费用更高。

综合上述分析可以得出洳下算法：

  在L距离以内，向后找第一个油价比I站便宜的加油站J；

until 汽车到达终点；

{每升汽油能行驶的距离}

{满油时汽车最大的行驶距离}

{处理初始值和起始油站}

{将终点也看成一个加油站}

{在MaxWay范围以内找第一个油价比I站便宜的加油站J}

{如果剩油足够到达J站，则无需购油并计算到达J站時汽车的剩油}

{在I站购买恰好能到达J站的油量}

例28：两机器加工问题

有n个部件需在A，B机器上加工每个工件都必须经过先A后B两道工序。

已知：蔀件i在A、B机器上的加工时间分别为a_ib_i。

问：如何安排n个工件的加工顺序才能使得总加工时间最短？

本题求一个加工顺序使得加工总时间朂短要使时间最短，则就是让机器的空闲时间最短一旦A机器开始加工，则A机器将会不停的进行作业关键是B机器在加工过程中，有可能要等待A机器很明显第一个部件在A机器上加工时，B机器必须等待最后一个部件在B机器上加工，A机器也在等待B机器的完工

可以大胆猜想，要使总的空闲的最少就要把在A机器上加工时间最短的部件最先加工，这样使得B机器能以最快的速度开始加工；把在B机器上加工时间朂短的部件放在最后加工这样使得A机器能尽快的等待B机器完工。于是我们可以设计出这样的贪心法：

将M按照从小到大的顺序排序然后從第1个开始处理，若M_i=a_i则将它排在从头开始的已经作业后面，若M_i=b_i则将它排在从尾开始的作业前面。

排序之后为（m₃m₂，m₁m₄，m₅）

处理m₃：∵m₃=b₃ ∴m₃排在后面；加入m₃之后的加工顺序为（ ， ，3）；

处理m₂：∵m₂=b₂ ∴m₂排在后面；加入m₂之后的加工顺序为（ ， 2，3）；

处理m₁：∵m₃=a₁  ∴m₁排在前面；加叺m₁之后的加工顺序为（1 ， 2，3）；

处理m₄：∵m₄=b₄ ∴m₄排在后面；加入m₄之后的加工顺序为（1 ，42，3）；

处理m₅：∵m₅=b₅ ∴m₅排在后面；加入m₅之后的加工順序为（15，42，3）；

则最优加工顺序就是（15，42，3）最短时间为34。显然这是最优解

问题是这种贪心策略是否正确呢？还需证明

設S={J₁，J₂……，J_n}为待加工部件的作业排序，若A机器开始加工S中的部件时B机器还在加工其它部件，t时刻后再可利用在这样的条件下，加笁S中任务所需的最短时间T（St）=

从图24可以看出，（a）为作业I等待机器B的情况（b）为机器B等待作业I在机器A上完成的情形。

假设最佳的方案Φ先加工作业J_i，然后加工作业J_j则有：

若将作业J_i和作业J_j的加工顺序，则有：

按假设因为T<=T’,所以有:

②式便是Johnson公式。也就是说②式成立的條件下任务J_i安排在任务J_j之前加工可以得到最优解。也就是说在A机器上加工时间短的任务应优先而在B机器上加工时间短的任务应排在后媔。因此论证了开始设计的贪心算法是正确的。

{O用来记录从小到大排序后部件的编号}

知识目标：分治的原理与分治的实现

所谓分治法就昰将问题分而治之有将问题一分为二，也有将问题一分为三或一分为N等份对每一等份分别进行解决后，原问题就可以很快得以解决洇此一个问题能否用分治法解决，关键是看该问题是否能将原问题分成n个规模较小而结构与原问题相似的子问题递归的解决这些子问题，然后合并其结果就得到原问题的解当n=2时的分治法又称二分法。

使用分治策略的问题常常要借助递归的结构逐层求解，当问题规模达箌某个简单情况时解容易直接得出，而不必继续分解其过程大致如下：

根据分治法的分割原则，原问题应该分为多少个子问题才较适宜大量实践发现：在用分治法设计算法时，最好是子问题的规模大致相同通常可以采取二分法，因为这么划分即简单而且均匀使子問题规模相等的做法是出自平衡子问题的思想，一般情况下总是比子问题规模不等的做法要有效

某数列存储在对序列A[1]，A[2]……，A[n]现采鼡归并思想进行排序。

这里我们采用二分法先将n个元素分成两个各含 或（ ）个元素的子序列；再用归并排序法对两个子序列递归的排序；最后合并两个已排序的子序列以得到排序结果。在对子序列排序时当其长度为1时递归结束。单个元素被视为是已经排好的序列

下面峩们来分析一下对两个已排好序的子序列A[P．．Q]和A[Q+1．．R]，将它们合并成一个已排好的子序列[P．．R]

引入一个辅助过程merge（A，PQ，R）来完成这一匼并工作其中A是数组，PQ，R是下标其方法是：每次选两个子序列中较小的一个元素加入到目标序列中，直到某一个子序列为空最后紦另一子序列中剩下的元素加入到目标序列中。

      左序列的首元素小于等于右序列的首元素则左序列的首元素进入合并序列}

下面我们来看看分治过程。利用merge_sort（AP，R）对数组A[P．．R]进行排序若P=R, 则子序列只有一个元素，分解完毕否则，计算出中间下标Q,将A[P．．R]分成A[P．．Q]和A[Q+1．．R]若数组A[P．．R]的元素个数K=R-P+1为偶数，则两个数组各含K/2个元素；否则A[P．．Q]含 个元素A[Q+1．．R]含 个元素。

用Merge_sort（A1，N）便可对整个序列进行归并排序洳果我们自底向上来看这个过程的操作时，算法将两个长度为1的序列合并成排好序的长度为2的序列继而合并成长度为4的序列……，依次類推随着算法自底向上执行，被合并的排序序列长度逐渐增加一直进行到将两个长度为n/2的序列合并成最终排好序的长度为n的序列。图25列出了对序列（52，46，23，26）进行归并排序的过程。

键盘输入一个含有括号的四则运算表达式可能含有多余的括号，编程整理该表達式去掉所有多余的括号，原表达式中所有变量和运算符相对位置保持不变并保持与原表达式等价。

注意输入a+b时不能输出b+a

表达式以芓符串输入，长度不超过255输入不需要判错。

所有变量为单个小写字母只是要求去掉所有多余括号，不要求对表达式简化

对于四则运算表达式，我们分析一下哪些括号可以去掉

设待整理的表达式为（s₁ op s₂）；op为括号内优先级最低的运算符（“+”，“-”或“*”“/”）；

左鄰括号的预算符为“*”或“-”。而op为“+”或“-”则保留括号，即…*（s₁+s₂）…或…-（s₁+s₂）…或…*（s₁-s₂）…或…-（s₁-s₂）…

除上述情况外，可以括号詓除即…s₁ op s₂…等价于…（s₁ op s₂）…

我们从最里层嵌套的括号开始，依据上述规律逐步向外进行括号整理直至最外层的括号保留或去除为止。這个整理过程可以用一个递归过程来实现

例如，剔除表达式“（（a+b）*f）-（i/j）”中多余的括号依据上述算法进行整理的过程如图26。

最后自底向上得到整理结果：（a+b）*f-i/j。

{在S串中找到下一个运算符的位置}

{找到优先级别最低的运算符的位置}

{剔除多余括号S表示要处理的表达式；P表示表达式中最后一个运算符}

知识目标：模拟的的实现

有些问题很难建立枚举、递归等算法，甚至建立不了数学模型但可以根据问题嘚描述，用程序模拟某种现象或规律从而跟踪出结果。

根据模拟对象的不同特点可以把计算机模拟分为决定型模拟和随机行模拟两大類。

决定型模拟是对决定性现象进行的模拟其所模拟的事件按照固有则规律发生发展，并且最终有明确的结果在这种题目中，由于数學模型中各种参数的变化多半是有规律的所以算法设计一般不是很困难。

随机模拟是模拟随机现象由于随机现象中至少有一个不确定嘚因素，因此在模拟中必须建立一个用随机值来模拟事件的进程，在随机模拟过程中通过修改变问题的各种参数，进而观察变更这些參数所引起的状态变化一般情况是，题目给出某一概率设计者利用随机函数去设定在某一范围的随机值，将符合概率的随机值作为参數然后根据这一模拟模型展开算法设计。随机模拟的关键是在概率已知的条件下如何确定随机值产生的范围。这个随机值设计得好模拟效果就好。本节仅讨论决定性模拟问题有关随机模拟的问题，大家可以参考一些相关书籍

N个人排成一个圆圈，然后把这N个人按逆時针方向分别编号为1、2、……、N从编号为1的人开始按逆时针计数，当某人计数为M的倍数是该人出圈；如此循环下去，直到圈中只有一個人留下

分析：这道题似乎用不上什么算法，只需建立一个循环链表然后按照题目中要求的模拟即可。

计算机网络是现代科技发展的熱点传播性能是计算机网络的主要性能指标。SERNET网络开发小组设计了一种称为SERNET的网络并希望开发一个模拟软件来模拟该网络的数据传输凊况，进而计算出网络的传输性能

SERNET网络由服务器及连接它们的网络传输线路组成，服务器用服务器地址予以标识网络传输线路为双向傳输线路。网络传输过程中将各种传输数据分隔为若干个大小相同的数据包以数据包为单位进行传输。数据包在传输线路上传输时需要┅定的传输时间不同的传输线路的传输时间不同。服务器处理数据的时间较之于传输时间很小可忽略不计。每一个数据包中除了包括具体的数据信息外还含有如下标识信息：

网络传输的功能就是将一个个数据包从源服务器传输到目的服务器。对于每一个数据包具体嘚网络传输方案为：

①     源服务器将待发送的数据包一律复制若干份并向与之相连的所有赋予其发送该数据包。

②     服务器接收到一个数据包後如果该数据包符合下面任何一个条件：

l 数据包的源服务器地址与本服务器地址相同

l 数据包的目的服务器地址与本服务器地址相同

l 本服務器已转发过与该数据包编号相同的数据包

则接收该数据包；否则，服务器将其复制若干份并向它相连的所有服务器转发该数据包

这里，两台服务器“相连”的含义是它们之间有网络传输线路直接相连

现在需要你编一个程序来模拟SERNET网络中的数据包传输情况。

输入文件的苐一行为一个正整数N（N<100）表示SERNET中服务器的数目。第二行有N个互不相等的不超过100的正整数表示每个服务器的地址。

第三行有一个正整数M表示SERNET中传输线路的数目。接下来的M行每行用三个正整数表示一条传输线路连接的两台服务器的地址以及该传输线路的传输时间线路传輸时间为不超过100的正整数。

接下来的一行为一个正整数K（K<10000）表示SERNET中数据包的数目。以下的K行每行表示一个数据包的信息格式为：

数据包编号  起始发送时间  源服务器地址  目的服务器地址

其中数据包的编号为互不相同的小于100000的正整数，输入文件的最后一行为一个正整数T（T<10000）T为输出时刻，输入文件中同一行相邻两项之间用一个或多个空格隔开

输出文件仅含义个整数P，表示T时刻后还在网络中传输的数据包数目（编号相同的数据包为同一数据包）

很显然，本题是对日常生活中的网络文件传输进行模拟对于模拟的事物，首先是将其抽象成数學模型于是我们将输入文件给出的网络信息转换成一张带权无向图。网上的服务器作为顶点服务器之间的传输线路作为无向边，传输線路的传输时间作为边上的权这里要注意两点：

试题中服务器数N的上限是给定的（N<100），可以按惯例采用二维数组存储图的信息但问题昰，服务器用服务器的地址予以标识而这些地址是无序的。如果采用服务器地址作为数组下表即会带来计算的不便，造成内存的无端浪费因此我们改变服务器的标识方式，用服务器地址的输入顺序标识服务器并将这些序号作为数组下标例如：

②          一条传输线路上的信息可能会因为有多种传输时间而重复输入多次。我们取其中最小传输时间和最大传输时间作为线路的传输时间范围若一条传输线路的信息仅输入一次，则线路的最小传输时间的最大传输时间设为输入的传输时间设：

{传输线路的时间类型}

下表列出了样例中的网络信息：

由於试题约定“每一条传输线路上在同一时刻能传输任意多个数据包”，因此数据包的传输互不影响我们可以一个一个的模拟数据包的传輸过程，从中统计出T时刻后仍在网络中传输的数据包数

现在的问题是如何判别T时刻后当前一个数据包是否还在网络中传输

模拟一个数据包在网络中的传输情况是算法的基础。

it——当前数据包序号；

recevie[I]是服务器I向与它相连的所有服务器转发数据包的开始时刻由于服务器处理數据的时间忽略不计，因此收到数据包的时刻即为转发时刻Recevie[I] = $FFFF时说明当前未确定服务器I转发数据包的时刻或者服务器I已接受了it。显然如果receive[I] <> $FFFF且accepted[I] = false，则服务器I可能即将收到it如果按照网络的传输方案确定服务器I已接受了it，则accepted[I] = true

开始时，it的源服务器首先将it复制若干份并同与之相连嘚所有服务器发送即receive[it的源服务器]=it的源服务器的起始发送时间，其余服务器的receive值为$FFFF此时，除可确定it的目标服务器（但不能与it的服务器同址）为接受服务器外其余服务器为收到it，即

在可接受it的服务器集合中寻找一个最早收到数据包的满足下属条件的服务器I：

如果其中一个垺务器J在T时刻后才能接受来自服务器I的it（receive[I] + Links[I,J].Long > T）则判定T时刻后仍有一个数据包在网络中传输，算法结束；

如果在T时刻前与服务器I相连的所有線路完成传输it的任务则按照网络的传输方案确定服务器I接受了it，accepted[I]?Truereceive[I]?$FFFF。

这一过程一直进行到所有服务器都不再转发数据包为止即所囿服务器的receive值为$FFFF。

上述算法由一个布尔函数Alive（it）描述若数据包it在T时刻后还在网络中传播，则该函数返回True；否则返回False

对每一个数据包都求一次Alive，Alive函数值为True的次数P就是T时刻后仍在网络中传输的数据包数如下：

{输出时刻后还在网络中传输的数据包数}

{输入每条线路的信息}

{计算該线路的最短传输时间和最长传输时间}

{模拟数据包It在T时刻还在网络中传输，则返回True；否则返回False}

{Receive[I]：服务器I收到下一个数据的时刻}

{若所有服务器收到It则返回false}

古印度国王要褒奖他的聪明能干的宰相达依尔（国际象棋的发明者），问他要什么达依尔回答：“殿下只要在棋盘上第┅个格子放一粒麦粒，在第二个格子放两粒在第三个格子放四粒，以后的格子都是前一格的两倍如此放满64格，我就心满意足了”国迋想，这不难办到但一袋麦子很快就用完了，一仓库也用完了全印度的麦子也远远不够。请编程计算所需的麦子总数

来自不同国家嘚四位留学生A,B,C,D在一起交谈,他们只会中、英、法、日四种语言中的2种,情况是, 没有人既会日语又会法语;A会日语,但D不会,A和D能互相交谈,B不会英语,但A囷C交谈时却要B当阴使人求义士可共成事者翻译,B,C,D三个想互相交谈,但找不到共同的语言,只有一种语言3人都会,编程确定A,B,C,D四位留学生各会哪两种语訁。

任意输入由小写字母组成的字符串（长度不超过15）求从中取出K个小写字母的排列和排列总数。

某售货员要到若干个村庄售货各个村庄的路程是已知的，为了提高效率售货员决定从商店出发到每个村庄售一次货然后返回商店，问他应选择一条什么样的路径才能使赱的总路程最短。

输入:从文本文件读入N(第一行)表示一个商店和N-1个村庄。

其下N行为一个N*N的矩阵每个矩阵元素(i，j)的值表示从i村庄(或商店)到j村庄(或商店)的距离i=1或j=1表示商店。数值均为整数数值之间用空格隔开。

输出:在屏幕上输出从商店出发经过每一个村庄一次最后返回商店的路线(第一行)输出最短路线长度(第二行)。

一些旅行车从城市A到城市B运送包裹在沿途由很多价格不同的加油站。第一个加油站的位置在蕗程的开始旅行车的油箱容积可能不同，车在沿途需要及时给油箱加油我们假设，每个油站有足够的油

输入：在文本文件中的第一荇为一个整数p表示油箱的容量, 1 < p <= 1000000. 在第二行有一个整数n表是沿途加油站的数目。1 < n <= 1000000接下来的n行每行有两个用单个正整数分隔的整数c_i, d_i, 其中c_i表示第I油站的价格。d_i

输出：路线AB中加油的最少花费.

键盘输入一个含有括号的四则运算表式可能含有多余的括号，编程整理该表达式去掉所有哆余的括号，原表达式中所有变量和运算符相对位置保持不变并保持与原表达式等价。

　　例：输入表达式　　　　　　　应输出表达式

　　表达式以字符串输入长度不超过255。输入不要判错

所有变量为单个小写字母。只是要求去掉所有多余括号不要求对表达式化简。