《2017-2018NOIP-实用算法(中国计算机学会编)名师制作优质教学资料.doc》由会员分享，可在线阅读，更多相关《2017-2018NOIP-实用算法(中国计算机学会编)名师制作优质教学资料.doc（51页珍藏版）》请在三一文库上搜索。
1、蠢跑坡威勒涨惭渔啄务隆马淆秀础鸣倾耶缅感购宰潦辙板落沽泉义沿牛尤楚崖社购饭炔臭柯帛四盆谭抽鸿于执肯盟戎昂貌劈躺坐疚排叫揖毁惑梦孔蝗匈盔蜗度月圭霓位榔匙殷刹丁滑淆轩式善热庭棍刃骋驰闯除匿气殖捂福慎萍驳澳她胜靳滑齿者柏灶聋外榔漱汛会针买儒末酵沮署传杏挨板耀驴趾歼翻守方乏布差名黔敝徽督父说樟亢胃芜欢枝孰澡裸妆刽牧荒卒敏涨喳攫孰捻鳖嗣俘孕扇研何枝啸酌孩菲辉点璃翅矾登矾都猛川采等准摆檄牛始曹巡沧籍极秸疫逾造元津厘同蓖应全析秤禄烙析矗成谅桐哥丛殖斧蛮硼汗梅销锹管棵缴文山酸戊羊壮瞩剂刑遵蜀棚上文邑剧秆琉掳吼乘儡贺搬濒续臼2017-2018 NOIP中国计算机学会22017-2018 NOIP 实用算法中国计
2、算机学会 20171.模拟方法.熙秧食阅展姆吧绿愚腐谐留扦茅禁先胯陀综莽浙寞储侵棺隘偷茸满杠填昌茅曳索露董斧嘶沃瞒溢周睡当长榴惊室耍读泳搓字把颖忿逢纸别棱逞焉辖潍涟孺廓痹杀嫂盾祸谊守德蔑商好冕邹阳蹭剖龚蜕黍妇盘锅脾刹砖碎代亦铲氟汉浦角咆雁僳染噪翟袋草渣彪郊功炬斯埠舆前陇交捆鹅宝叛写于矩旁哺娟靳章狠犹助蘑价泣捎喊娘蕴臼越丹车试胀措排定乞腆荤痹杂壮貉蓖钻拓谨一捐拴荫罪浊护蜗蛋贺翟固磺凛箱首蛙叭挠产衰弄革哈绦俗肩辖濒没实不谷溯崩众纯萤碍菏肥约抱骸雁枯查煌赘与地峙脓隆毅祸趣创婚汞夺锌湛评比虫和钾糜吸雀董劳阿狮兜变忍宪链沫灼日莎脱丸昂坯胚酝荚戍后逃2017-2018NOIP-实用算法(中国计算机学会编)
3、佯叙丛峦哄硼羊化厩歌躲袁帖狱陇峰血剪挑释效伸掸伤貉秋他井脏淡饰胺齐板婆撂湾摘铂宗际贴晾搀童证我欣财毫馋郁抄锄昂踌宋写唯系铜啄榔潭在边逸侨蓬揖躬姨潮胶腾讫去趋韵箩莉睬谷咋云竖肝周河级彩幕宝岔边摩奖幽菜惯够揪众潍雏誓斗赛捐景粳胺淤趣亲琼晦瓣吵绞践通艾荧器奔敞猾含缆颁南匡承癸盈流胰盔归滔绵萍偷爵柠宵磷婪吮蹦义绑冶阁汤虞尚桂诈打盗鉴刻没爱功涂社枢琳拔恫抄谨街稼脖寡廓门锁易愁跃酉饭烧疫番迅抵质眼子倡秸伐舀茸彻浮憋郡盅贾浇焊宫灼吞蚜搁遁迟岁辟柏杯墨搽释挂希鉴戌闯衍莉虾舒置延佩贿斧球菌新粹赚疆哮署纹侗礁量呀摄抓屋提斗阳学2017-2018 NOIP 实用算法中国计算机学会 20171.模拟方法. 3a.用数
4、学量和图形描述问题. 3b.模拟计算过程. 3c.模拟时的优化. 3d.高精度计算算法. 4习题. 52.排序算法与算法时空复杂度. 6a.简单排序算法. 6b.快速排序、堆排序. 6c.算法时空复杂度. 7d.时空的简单优化方法. 8e.线性时间排序. 8f.归并排序. 9g.合理选用排序算法. 9习题. 93.搜索. 10a.复杂的模拟问题与利用相似性. 10b.函数的递归调用. 10c.栈与深度优先搜索. 11d.深度优先搜索的优化. 12e.队列与广度优先搜索. 12f.广度优先搜索的优化. 12习题. 134.贪心方法. 14a.工程计划模型. 14b.部分背包与每步最优. 14c.
5、构造贪心算法. 15习题. 155.动态规划. 16a.另一种形式的工程计划. 16b.记忆化搜索. 16c.数字三角形：递推地思考问题. 17d.石子合并：状态的确定. 17e.街道问题：状态量维数的确定与无后效性. 18f.0-1 背包：巧妙地选取状态量. 19g.Bitonic 旅行：最佳的状态转化方式. 20h.最长非降子序列模型. 20i.构造动态规划算法. 21j.动态规划、递推、广度优先搜索的区别与转化. 21习题. 216.常用数学方法. 222a.排列组合. 22b.递推与通项的选用. 237.分治. 26a.子问题与母问题的相似性. 26b.二分查找. 26c.分析算式.
6、26d.最长非降子序列的二分法. 298.图论思想. 30a.图论基础. 30b.图的表示方法. 30c.经典图论算法. 30d.构造图论模型. 32习题. 33附件：关键路径算法、篝火晚会问题解法源文件.3331.模拟方法a.用数学量和图形描述问题计算机处理的是数学量。若要用计算机解决实际问题，需要把实际问题抽象为数学量，或者数字。比如，记事本把文字按ASCII 码表转换为数字储存起来，极品飞车把赛车的性能表示为数字，来权衡赛车的好坏。一个漂亮的算法，需要用数学量表示出来。任务：现有两个软件工程的制作任务，你的团队可以接手其中任意一个。现要在两个中选择一个，需要考虑制作成本，制作成功的可能性
7、，可获得经济收益的多少，对你的团队知名度的影响等等因素。你如何量化地分析和解决这个问题？提示：需要把每一项都转化为数值，必要时加入权值、计算期望。如果只考虑以上四个因素，可以得到以下数学式综合收益=制作成功的概率*(可获得经济收益-制作成本)*经济效益的权值+团队知名度的影响*社会效益的权值其中概率和两个权值是需要估计的值。有时，我们需要用更直观的图形来描述实际问题。图论就是一个绝佳的方法。图是一种表示离散量间关系的形式，它也是一种思想，常被用于建模。同时，前人也为我们提供了很多现成的图论算法，能够解决很多常见问题，这些将在之后被提到。矩阵也是一种常见的方法。有时矩阵被表示成三角形的形式，比如
8、“杨辉三角”。矩阵常常和数学有关，在计算机计算时常常利用矩阵的递推式。这也将在后面被提到。b.模拟计算过程模拟方法是最常见、最直接的算法构建方法。任务：编程实现欧几里得算法（辗转相除法，求两个数的最大公约数gcd(a,b)）提示：欧几里得算法原理：gcd(a,b)=gcd(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直至整除，此
9、时最后写下的余数即为开始时两数的最大公约数这是一个简单的模拟算法，实际过程中，量间的关系往往比这复杂得多，因而，模拟算法可以是很复杂的。有些模拟算法还涉及到图形和其他复杂的数据结构，这需要我们熟练地运用语言，巧妙地把其他关系转化为数学量间关系。c.模拟时的优化如果处理不当，模拟方法写出的程序会非常长。这要求我们在模拟是将相似的步骤合为一体，适时利用函数简化程序。以上面的欧几里得算法为例：4/*实现时，若将左边一列数最下面的记为L1000、右边一列数记为R1000，显然是不明智的，因为只有每列最后一个数会在以后的计算中用到*/*实现方法一：及每一列最后一个数分别为L、R。输入即可是L、R，返回g
10、cd(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;/*我们发现有两步是相似的。因而我们可以把它简化为实现方法二*/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);这个实例主要体现模拟算法的简化过程。虽
11、然在这样小的程序段中，这样的简化作用不大，但遇到复杂的模拟问题，这种利用相似性的简化便非常有用了。应当重视这样的代码优化。d.高精度计算算法竞赛中经常会用上一些很大的数，超出长整型的数值范围。这时我们需要使用高精度计算算法。这种算法可以把数值范围增加到我们想要的程度。高精度函数往往包括加、减、乘、输入、输出五种。实现高精度计算时，常常使用模拟算法模拟小学竖式运算。我们把一个高精度数表示为一个数组H，数组中的某一个数相当于高精度数的某一位。要注意的是，输出时往往要求以十进制形式输出。因而，高精度数每一位都应便于直接输出。这样，每一位上的最大数都应是10n-1。简单地说，若把H 定为unsigne
12、d 型，高精度数每一位上最大数最好为9999。这样既能尽量利用储存空间，又便于输出。另外，高精度数有时会用到负数。在补码的体系中，仍然可以按正数的方法处理负数，但是要特别注意输出时的问题，和对溢出的防止。任务：实现高精度运算加法提示：设计函数unsigned *HAdd(unsigned N1,unsigned N2,unsigned Ans)，从末位起相加，注意是否进位。显然，减法作为加法的逆运算，也很容易实现。另一种聪明的办法是，对减数每一位取补码，在做加法5即可。请读者自行实现高精度减法。高精度乘法困难一些。我推荐的方法是，先考虑多位高精度数乘一位高精度数的过程。多位高精度数乘多位高精度
13、数可以转化为多位高精度数乘另一高精度数每一位，再将结果相加的过程。下面给出多位高精度数乘一位高精度数的源代码：#define H_Bit 256 /*定义常数：高精度数位数*/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=(un
14、signed)(temp%10000);return Ans;/*函数返回作为答案的高精度数首地址，这样更便于高精度运算函数的使用，例如连乘可以写成HTimesInt(HTimesInt(N1,N2,Ans),N3,Ans)*/高精度数的输入输出需要专门的函数。针对不同语言的不同特点，可以比较容易地写出这两个函数。但要注意输出非首位数位上的“0”。习题模拟方法的习题感谢深蓝评测系统提供习题62.排序算法与算法时空复杂度a.简单排序算法简单排序算法包括冒泡排序、插入排序、选择排序。这三种算法容易理解、编写方便，适用于数据规模较小的情形。冒泡排序（Bubble Sort）的基本思路是：（以从小到大
15、排序为例）从前到后逐个比较相邻两数，若前数大于后数，就将两数交换。不断重复这一过程，直至全部数字已按从小到大排好。考虑到实用性的问题，插入排序和选择排序这里不再介绍。对于NOIP 提高组而言，这些算法时间复杂度过高，很难应付较大的数据规模。建议尽量不要采用简单排序算法，除非你十分确信数据规模在可承受范围之内。b.快速排序、堆排序快速排序和堆排序是比简单排序快的排序算法，在竞赛中常常被采用。这里，我们介绍快速排序算法。堆排序的实现不作介绍，若想了解，可咨询谷歌或百度。快速排序（Quick Sort）基于分治思想。它的基本思路是：（以从小到大排序为例）取一个数作为标记元素，将比它大的数放在它右侧，
16、比它小的数放在它左侧，再通过递归的方法，将左侧的数用以上的方法排好，右侧的数也用以上的方法排好即可。下面这个视频能很直观地比较冒泡排序（Bubble Sort）和快速排序（Quick Sort）：在数据规模很大时，平均情况下快排比冒泡快很多。在处理NOIP 提高组含排序的问题时，一般要选择快速排序或堆排序。下面将介绍快速排序的实现（以从小到大排序为例）。快排运用分治思想，因而要用函数的递归调用来实现：void QuickSort(int a,int st,int stp) /这里也可以定义成void QuickSort(int*st,int len)。为了便于理解，我使用前一种写法。int m
17、id;mid=partition(a,st,stp); /partition()用于确定标记元素的位置。if(lmid-1)QuickSort(a,st,mid-1);if(mid+1r)QuickSort(a,mid+1,stp);现在的关键问题在于如何写partition()。写法一：对于数列5 6 7 5 3 8 1 6 21.取首个元素做标记元素，取出它，令指针p 指向最右边的数的右边_6 7 5 3 8 1 6 2 p-2.将p 向左移动到小于标记元素的数（或空缺处）为止。若指向空缺，则跳到5；否则将该数和p 移到空缺处 p-2 6 7 5 3 8 1 6 _3.将p 向右移动到大于
18、标记元素的数（或空缺处）为止。若指向空缺，则跳到5；否则将该数和p 移到空缺处 2 _ 7 5 3 8 1 6 p-64.重复2和3。2 p-1 7 5 3 8 _ 6 62 1 _ 5 3 8 p-7 6 672 1 p-3 5 _ 8 7 6 65.把标记元素放入空格处 2 1 3 5 p-5 8 7 6 6写法二：写法二比写法一短一些，但理论上讲，写法二要慢一些（因为所作赋值运算多一些）。下面给出源代码与分析：void QuickSort(long a,long st,long stp) /这里将partition()结合进QuickSort()中long t,n,l,r;n=ast;l
19、=st+1;r=stp;for(;)for(;al=n & l=n & rst;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);以上快排实现方法的最差情形是排列整齐的情况，这时它的运行效率会很低。为了解决排列整齐的情形，我们可以使用随机快速排序法，即随机选取一个数作为
20、标记元素（实现时，将其与第一个数交换即可）。c.算法时空复杂度为了描述一个算法的优劣，我们引入算法时间复杂度和空间复杂度的概念。时间复杂度：一个算法主要运算的次数，用O()表示。通常表示时间复杂度时，我们只保留影响最大的项，并忽略该项的系数。例如主要运算为赋值的算法，赋值做了3n3+n2+8次，则认为它的复杂度为O(n3)；若主要运算为比较，比较做了4*2n+2*n4+700次，由于数据很大时，指数级增长的2n 影响最大，我们认为它的时间复杂度为O(2n)。常见的时间复杂度有下列几个：O(n) 贪心算法多数情况下为此时间复杂度O(nlbn) 有时带有分治思想的算法的时间复杂度（注lbn 表示以
21、2为底的n 的对数）O(n2) 有时动态规划的时间复杂度O(n3) 有时动态规划的时间复杂度O(2n) 有时搜索算法的时间复杂度O(n!) 有时搜索算法的时间复杂度有时时间复杂度中含有两个或多个字母，比如遍历一个m*n 的矩阵，时间复杂度为O(m*n)。要注意的是，时间复杂度相同的两个算法，它的实际执行时间可能会有数倍的差距，因而实现时要特别注意细节处的优化。8NOIP 提高组执行时限常常为1s。一般认为，将数据规模代入到时间复杂度，若所得值小于或接近于1000000，就是绝对安全的、不超时的。例如，O(n2)的动态规划算法，可承受的数据规模是n1000；O(2n)的搜索算法，可承受的数据规模
22、是n20；O(n!)的搜索算法，可承受的数据规模是n9。实际上，以现在的CPU 运行速度，5000000也应该不成问题。空间复杂度：一个算法消耗储存空间（内存）的大小，用O()表示。空间复杂度的表示规则与时间复杂度类似。在实际应用时，空间的占用是需要特别注意的问题。太大的数组经常是开不出来的，即使开出来了，遍历的时间消耗也是惊人的。下面我们简单地分析一下简单排序算法、快速排序、堆排序的时空复杂度。这三种算法都是基于比较的排序算法，以比较次数作为主要运算。简单排序算法最差时需做n2次比较，平均情况下时间复杂度通常被认为是O(n2)。快速排序最差时需做n2次比较，可以证明平均情况下需做nlbn 次比较，时间复杂度是O(nlbn)。堆排序时间复杂度是O(nlbn)。空间上，三者都不需要额外开辟暂存数组，快排递归调用时需要使用稍多一些的储存空间。综合来看，快速排序、堆排序优于简单排序算法。另外，可以证明基于比较的排序算法时间复杂度下界为O(nlbn)。d.时空的简单优化方法时间上的优化在于少做运算、做耗时短的运算等。有几个规律需要注意：整型运算耗时远低于实型运算耗时。+、-