2017-2018NOIP-实用算法(中国计算机学会编).doc

1、2017-2018 NOIP 中国计算机学会12017-2018 NOIP 实用算法中国计算机学会 20172017-2018 NOIP 中国计算机学会21.模拟方法. 3a.用数学量和图形描述问题. 3b.模拟计算过程. 3c.模拟时的优化 . 3d.高精度计算算法. 4习题. 52.排序算法与算法时空复杂度. 6a.简单排序算法. 6b.快速排序、堆排序. 6c.算法时空复杂度 . 7d.时空的简单优化方法. 8e.线性时间排序. 8f.归并排序. 9g.合理选用排序算法. 9习题. 93.搜索. 10a.复杂的模拟问题与利用相似性. 10b.函数的递归调用. 10c.栈与深度优先搜索 .

2、 11d.深度优先搜索的优化. 12e.队列与广度优先搜索. 12f.广度优先搜索的优化. 122017-2018 NOIP 中国计算机学会3习题. 134.贪心方法. 14a.工程计划模型. 14b.部分背包与每步最优. 14c.构造贪心算法 . 15习题. 155.动态规划. 16a.另一种形式的工程计划. 16b.记忆化搜索. 16c.数字三角形：递推地思考问题. 17d.石子合并：状态的确定. 17e.街道问题：状态量维数的确定与无后效性. 18f.0-1 背包：巧妙地选取状态量. 19g.Bitonic 旅行：最佳的状态转化方式. 20h.最长非降子序列模型. 20i.构造动态规划算

3、法. 21j.动态规划、递推、广度优先搜索的区别与转化. 21习题. 216.常用数学方法. 222a.排列组合. 22b.递推与通项的选用. 237.分治. 26a.子问题与母问题的相似性. 262017-2018 NOIP 中国计算机学会4b.二分查找. 26c.分析算式. 26d.最长非降子序列的二分法. 298.图论思想. 30a.图论基础. 30b.图的表示方法. 30c.经典图论算法 . 30d.构造图论模型. 32习题. 33附件：关键路径算法、篝火晚会问题解法源文件.3331.模拟方法a.用数学量和图形描述问题计算机处理的是数学量。若要用计算机解决实际问题，需要把实际问题抽象为

4、数学量，或者数字。比如，记事本把文字按ASCII 码表转换为数字储存起来，极品飞车把赛车的性能表示为数字，来权衡赛车的好坏。一个漂亮的算法，需要用数学量表示出来。任务：现有两个软件工程的制作任务，你的团队可以接手其中任意一个。现要在两个中选择一个，需要考虑制作成本，制作成功的可能性，可获得经济收益的多少，对你的团队知名度的影响等等因素。你如何量化地分析和解决这个问题？提示：需要把每一项都转化为数值，必要时加入权值、计算期望。如果只考虑以上四个因素，可以得到以下数学式综合收益=制作成功的概率*( 可获得经济收益-制作成本)*经济效益的权值+ 团队知名度的影响*社会效益的权值其中概率和两个权值是需

5、要估计的值。有时，我们需要用更直观的图形来描述实际问题。图论就是一个绝佳的方法。图是一种表示离散量间关系的形式，它也是一种思想，常被用于建模。同时，前人也为我们提供了很多现成的图论算法，能够解决很多常见问题，这些将在之后被提到。矩阵也是一种常见的方法。有时矩阵被表示成三角形的形式，比如“杨辉三角”。矩阵常常和数学有关，在计算机计算时常常利用矩阵的递推式。这也将在后面被提到。b.模拟计算过程模拟方法是最常见、最直接的算法构建方法。2017-2018 NOIP 中国计算机学会5任务：编程实现欧几里得算法（辗转相除法，求两个数的最大公约数gcd(a,b)）提示：欧几里得算法原理：gcd(a,b)=g

6、cd(b,a mod b)欧几里得算法的图形描述| 168 63 | | 168 63 | 2| 42 |1.写下两个数2.将两数相除，余数写在较大的数下面| 168 63 | 2 | 168 63 | 21 | 42 21 | 1 | 42 21 | 2 整除3.将每列最下面的数相除，余数写在被除数下面4. 重复步骤3 直至整除，此时最后写下的余数即为开始时两数的最大公约数这是一个简单的模拟算法，实际过程中，量间的关系往往比这复杂得多，因而，模拟算法可以是很复杂的。有些模拟算法还涉及到图形和其他复杂的数据结构，这需要我们熟练地运用语言，巧妙地把其他关系转化为数学量间关系。c.模拟时的优化如果

7、处理不当，模拟方法写出的程序会非常长。这要求我们在模拟是将相似的步骤合为一体，适时利用函数简化程序。以上面的欧几里得算法为例：4/*实现时，若将左边一列数最下面的记为L1000、右边一列数记为 R1000，显然是不明智的，因为只有每列最后一个数会在以后的计算中用到*/*实现方法一：及每一列最后一个数分别为L、R。输入即可是 L、R，返回gcd(L,R)*/int Euclid_1(int L,int R)for(;)L=L%R;if(L=0)return R;R=R%L;if(R=0)return L;2017-2018 NOIP 中国计算机学会6/*我们发现有两步是相似的。因而我们可以把它简

8、化为实现方法二*/int Euclid_2(int L,int R)int t;for(;)t=R; R=L%R; L=t;if(R=0)return L;/*甚至我们可以写成递归形式。以下是实现方法三*/int Euclid_3(int L,int R)if(L%R=0)return R;else return Euclid_3(R,L%R);这个实例主要体现模拟算法的简化过程。虽然在这样小的程序段中，这样的简化作用不大，但遇到复杂的模拟问题，这种利用相似性的简化便非常有用了。应当重视这样的代码优化。d.高精度计算算法竞赛中经常会用上一些很大的数，超出长整型的数值范围。这时我们需要使用高精度

9、计算算法。这种算法可以把数值范围增加到我们想要的程度。高精度函数往往包括加、减、乘、输入、输出五种。实现高精度计算时，常常使用模拟算法模拟小学竖式运算。我们把一个高精度数表示为一个数组H，数组中的某一个数相当于高精度数的某一位。2017-2018 NOIP 中国计算机学会7要注意的是，输出时往往要求以十进制形式输出。因而，高精度数每一位都应便于直接输出。这样，每一位上的最大数都应是10n-1。简单地说，若把H 定为unsigned 型，高精度数每一位上最大数最好为9999。这样既能尽量利用储存空间，又便于输出。另外，高精度数有时会用到负数。在补码的体系中，仍然可以按正数的方法处理负数，但是要特

10、别注意输出时的问题，和对溢出的防止。任务：实现高精度运算加法提示：设计函数unsigned *HAdd(unsigned N1,unsigned N2,unsigned Ans)，从末位起相加，注意是否进位。显然，减法作为加法的逆运算，也很容易实现。另一种聪明的办法是，对减数每一位取补码，在做加法5即可。请读者自行实现高精度减法。高精度乘法困难一些。我推荐的方法是，先考虑多位高精度数乘一位高精度数的过程。多位高精度数乘多位高精度数可以转化为多位高精度数乘另一高精度数每一位，再将结果相加的过程。下面给出多位高精度数乘一位高精度数的源代码：#define H_Bit 256 /*定义常数：高精度数

11、位数*/unsigned *HTimesInt(unsigned N1,int N2,unsigned Ans) /*N1为多位高精度数，N2为高精度数的一位，Ans为另一高精度数，用于储存结果*/*这里允许N1与Ans 相同*/unsigned i,up=0;unsigned long temp;for(i=H_Bit-1;i=H_Bit;i-)temp=N1i*N2+up;up=temp/10000;Ansi=(unsigned)(temp%10000);return Ans;/*函数返回作为答案的高精度数首地址，这样更便于高精度运算函数的使用，例如连乘可以写成2017-2018 NOIP

12、 中国计算机学会8HTimesInt(HTimesInt(N1,N2,Ans),N3,Ans)*/高精度数的输入输出需要专门的函数。针对不同语言的不同特点，可以比较容易地写出这两个函数。但要注意输出非首位数位上的“0”。习题模拟方法的习题 感谢深蓝评测系统提供习题62.排序算法与算法时空复杂度a.简单排序算法简单排序算法包括冒泡排序、插入排序、选择排序。这三种算法容易理解、编写方便，适用于数据规模较小的情形。冒泡排序（Bubble Sort）的基本思路是：（以从小到大排序为例）从前到后逐个比较相邻两数，若前数大于后数，就将两数交换。不断重复这一过程，直至全部数字已按从小到大排好。考虑到实用性的

13、问题，插入排序和选择排序这里不再介绍。对于NOIP 提高组而言，这些算法时间复杂度过高，很难应付较大的数据规模。建议尽量不要采用简单排序算法，除非你十分确信数据规模在可承受范围之内。b.快速排序、堆排序快速排序和堆排序是比简单排序快的排序算法，在竞赛中常常被采用。这里，我们介绍快速排序算法。堆排序的实现不作介绍，若想了解，可咨询谷歌或百度。快速排序（Quick Sort）基于分治思想。它的基本思路是：（以从小到大排序为例）取一个数作为标记元素，将比它大的数放在它右侧，比它小的数放在它左侧，再通过递归的方法，将左侧的数用以上的方法排好，右侧的数也用以上的方法排好即可。下面这个视频能很直观地比较冒

14、泡排序（Bubble Sort）和快速排序（Quick Sort）：在数据规模很大时，平均情况下快排比冒泡快很多。在处理NOIP 提高组含排序的问题时，一般要选择快速排序或堆排序。下面将介绍快速排序的实现（以从小到大排序为例）。快排运用分治思想，因而要用函数的递归调用来实现：void QuickSort(int a,int st,int stp) /这里也可以定义成 void QuickSort(int*st,int len)。为了便于理解，我使用前一种写法。int mid;mid=partition(a,st,stp); /partition()用于确定标记元素的位置。2017-2018 N

15、OIP 中国计算机学会9if(l=n r-); /从左找，找到一个大于标记元素的数if(l=r)break; /如果l 在 r 右侧，则跳出t=al;al=ar;ar=t; /交换，使小于标记元素的在左，大于标记元素的在右ast=ar; /取出最右侧的小于标记元素的数写入空缺ar=n; /空缺处放入标记元素if(r-st1)QuickSort(a,st,r-1);if(stpl)QuickSort(a,l,stp);以上快排实现方法的最差情形是排列整齐的情况，这时它的运行效率会很低。为了解决排列整齐的情形，我们可以使用随机快速排序法，即随机选取一个数作为标记元素（实现时，将其与第一个数交换即可）。c.算法时空复杂度为了描述一个算法的优劣，我们引入算法时间复杂度和空间复杂度的概念。时间复杂度：一个算法主要运算的次数，用O()表示。通常表示时间复杂度时，我们只保留影响最大的项，并忽略该项的系数。例如主要运算为赋值的算法，赋值做了3n3+n2+8 次，则认为它的复杂度为 O(n3)；若主要运算为比较，比较做了4*2n+2*n4+700次，由于数据很大时，指数级增长的2n 影响最大，我们认为它的时间复杂度为O(2n)。常见的时间复杂度有下列几个：O(n) 贪心算法多数情况下为此时间复杂度