《2021年NOIP初赛复习14基本算法思想总结》由会员分享，可在线阅读，更多相关《2021年NOIP初赛复习14基本算法思想总结（26页珍藏版）》请在金锄头文库上搜索。
1、不问收获，但问耕耘，把最好的资料送给最好的自己！最新NOIP初赛复习14基本算法思想总结姓名：XXX时间：20XX年X月X日NOIP初赛复习14基本算法思想 一个程序往往要包含两个方面的描述：一是对数据组织的描述，就是数据的类型和数据的组织形式（例如数组），称作数据结构；一是对程序操作流程的描述，就是程序的操作步骤，也就是所谓算法。正如著名的计算机科学家沃思（Nikiklaus Wirth）提出的公式：数据结构+算法=程序。 算法，广义地讲就是解决问题的方法和过程。可以使用自然语言、伪代码、流程图等多种不同的方法来描述。如果把一个程序比喻成一个具有生命的人，那么数据结构就是这个人的躯体，而算法
2、则是这个人的灵魂。 枚举 枚举法，又称穷举法，或称为暴力破解法，是一种针对于密码的破译方法，即将密码进行逐个推算直到找出真正的密码为止。 基本思想：在可能的解空间中穷举出每一种可能的解，并对每一个可能解进行判断，从中得到问题的答案。虽然枚举法本质上属于搜索策略，但是它与后面讲的回溯法或宽度优先搜索有所不同。总的来说，枚举就是通过列举所有的可能性进行一一判断检查。 适用条件： 1、可预先确定每个状态的元素个数n。 2、可预先确定每个状态元素a1,a2,an的值域。 注意事项：使用枚举思想解决实际问题，最关键的步骤是划定问题的解空间，并在该解空间中一一枚举每一个可能的解。这里有两点需要注意。一是解
3、空间的划定必须保证覆盖问题的全部解。如果解空间集合用H表示，问题的解集用h表示，那么只有当时，才能使用枚举法求解。二是解空间集合及问题的解集一定是离散的集合，也就是说集合中的元素是可列的、有限的。 常见类型：枚举排列、枚举子集。 常见方法：递归地枚举，这种方法往往更为直观；递推（循环）地枚举，这种方法往往写起来更为简洁。 主要优点：由于枚举算法一般是现实问题的“直译”，且是建立在考察大量状态、甚至是穷举所有状态的基础之上的，因此比较直观，易于理解，其算法的正确性也比较容易证明。 主要缺点：枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价，因此效率比较低。在某些情况下，我们可以通过利用题
4、目的特点去除相当大的一部分情况的列举，从而提高枚举的效率。 算法优化： 1、提取有效信息; 2、减少重复计算; 3、将原问题化为更小的问题; 4、根据问题的性质进行截枝; 5、引进其他算法。 例：NOIP20XX玩具谜题、NOIP20XX生活大爆炸版石头剪刀布等 递推 递推是一种用若干步可重复的简运算（规律）来描述复杂问题的方法。给定一个数的序列H0,H1,Hn,若存在整数n0，使当n>n0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hi(0<i<n)联系起来，这样的式子就叫做递推关系。 基本思想：递推是按照一定的规律来计算序列中的每个项，通常是通过计算机前面的一
5、些项来得出序列中的指定项的值。把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法利用了计算机速度快和不知疲倦的机器特点。 主要步骤：建立递推关系式；确定边界条件；递推求解。 应用分类：一般递推问题；组合计数类问题；一类博弈问题的求解；动态规划问题的递推关系。 动态规划与递推的关系 1、一般递推边界条件很明显，动态规划边界条件比较隐蔽，容易被忽视； 2、一般递推数学性较强，动态规划数学性相对较弱； 3、一般递推不划分阶段，动态规划一般有较为明显的阶段。 五种典型的递推关系 1、Fibonacci数列 在所有的递推关系中，Fibonacci数列应该是最为大家所熟悉的。在最基础的程序设计语言
6、Logo语言中，就有很多这类的题目。而在较为复杂的Basic、Pascal、C语言中，Fibonacci数列类的题目因为解法相对容易一些，逐渐退出了竞赛的舞台。可是这不等于说Fibonacci数列没有研究价值，恰恰相反，一些此类的题目还是能给我们一定的启发的。 Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”(又称“Fibonacci问题”)。 问题的提出：有雌雄一对兔子，假定过两个月便可繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子？ 解：设满x个月共有兔子Fx对，其中当月新生的兔子数目为Nx对。第x-1个月留下的兔子数目设为Fx
7、-1对。则： Fx=Nx+Fx-1 Nx=Fx-2 (即第x-2个月的所有兔子到第x个月都有繁殖能力了) Fx=Fx-1+Fx-2 边界条件：F0=0，F1=1 由上面的递推关系可依次得到 F2=F1+F0=1，F3=F2+F1=2，F4=F3+F2=3，F5=F4+F3=5，。 Fabonacci数列常出现在比较简单的组合计数问题中，例如以前的竞赛中出现的“骨牌覆盖”问题。在优选法中，Fibonacci数列的用处也得到了较好的体现。 2、Hanoi塔问题 问题的提出：Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大到小依次套在a柱上，如图所示。 要求把a柱上n
8、个圆盘按下述规则移到c柱上： 1、一次只能移一个圆盘； 2、圆盘只能在三个柱上存放； 3、在移动过程中，不允许大盘压小盘。 问将这n个盘子从a柱移动到c柱上，总计需要移动多少个盘次？ 解：设hn为n个盘子从a柱移到c柱所需移动的盘次。显然，当n=1时，只需把a 柱上的盘子直接移动到c柱就可以了，故h1=1。当n=2时，先将a柱上面的小盘子移动到b柱上去；然后将大盘子从a柱移到c 柱；最后，将b柱上的小盘子移到c柱上，共记3个盘次，故h2=3。以此类推，当a柱上有n(n2)个盘子时，总是先借助c柱把上面的n-1个盘子移动到b柱上，然后把a柱最下面的盘子移动到c柱上；再借助a柱把b柱上的n-1个盘
9、子移动到c柱上；总共移动hn-1+1+hn-1个盘次。 hn=2hn-1+1 边界条件：h1=1 3、平面分割问题 问题的提出：设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。 解：设an为n条封闭曲线把平面分割成的区域个数。 由图3-13可以看出：a2-a1=2；a3-a2=4；a4-a3=6。 从这些式子中可以看出an-an-1=2(n-1)。当然，上面的式子只是我们通过观察4幅图后得出的结论，它的正确性尚不能保证。下面不妨让我们来试着证明一下。当平面上已有n-1条曲线将平面分割成an-1个区域后，第n-
10、1条曲线每与曲线相交一次，就会增加一个区域，因为平面上已有了n-1条封闭曲线，且第n条曲线与已有的每一条闭曲线恰好相交于两点，且不会与任两条曲线交于同一点，故平面上一共增加2(n-1)个区域，加上已有的an-1个区域，一共有an-1+2(n-1)个区域。所以本题的递推关系是an=an-1+2(n-1)，边界条件是a1=1。 4、Catalan数 Catalan数首先是由Euler在精确计算对凸n边形的不同的对角三角形剖分的个数问题时得到的，它经常出现在组合计数问题中。 问题的提出：在一个凸n边形中，通过不相交于n边形内部的对角线，把n边形拆分成若干三角形，不同的拆分数目用hn表示，hn即为Ca
11、talan数。例如五边形有如下五种拆分方案，故h5=5。求对于一个任意的凸n边形相应的hn。 NOIP初赛复习（三）栈与卡特兰数>>> Catalan数是比较复杂的递推关系，尤其在竞赛的时候，选手很难在较短的时间里建立起正确的递推关系。当然，Catalan数类的问题也可以用搜索的方法来完成，但是，搜索的方法与利用递推关系的方法比较起来，不仅效率低，编程复杂度也陡然提高。 5、第二类Stirling数 在五类典型的递推关系中，第二类Stirling是最不为大家所熟悉的。也正因为如此，我们有必要先解释一下什么是第二类Strling数。 定义：n个有区别的球放到m个相同的盒子中，要
12、求无一空盒，其不同的方案数用S(n,m)表示，称为第二类Stirling数。 下面就让我们根据定义来推导带两个参数的递推关系第二类Stirling数。 解：设有n个不同的球，分别用b1,b2,bn表示。从中取出一个球bn，bn的放法有以下两种： 1、bn独自占一个盒子；那么剩下的球只能放在m-1个盒子中，方案数为S2(n-1,m-1)； 2、bn与别的球共占一个盒子；那么可以事先将b1,b2,bn-1这n-1个球放入m个盒子中，然后再将球bn可以放入其中一个盒子中，方案数为mS2(n-1,m)。 综合以上两种情况，可以得出第二类Stirling数定理： S2(n,m)=mS2(n-1,m)+S
13、2(n-1,m-1) (n>1,m1) 边界条件可以由定义2推导出： S2(n,0)=0；S2(n,1)=1；S2(n,n)=1；S2(n,k)=0(k>n)。 小结：通过上面对五种典型的递推关系建立过程的探讨，可知对待递推类的题目，要具体情况具体分析，通过找到某状态与其前面状态的联系，建立相应的递推关系。 递归 一个函数、过程、概念或数学结构，如果在其定义或说明内部又直接或间接地出现有其本身的引用，则称它们是递归的或者是递归定义的。在程序设计中，过程或函数直接或者间接调用自己，就被称为递归调用。其中直接调用自己称为直接递归，而将A调用B，B以调用A的递归叫做间接递归。 基本思想：
14、 1、递归是借助于一个递归工作栈来实现。递归=递推+回归。 2、递推：问题向一极推进, 这一过程叫做递推。这一过程相当于压栈。 3、回归：问题逐一解决，最后回到原问题，这一过程叫做回归。这一过程相当于弹栈。 注意事项： 1、递归就是在过程或函数里调用自身； 2、在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。 主要优点：采用递归方法编写的问题解决程序具有结构清晰，可读性强等优点，且递归算法的设计比非递归算法的设计往往要容易一些，所以当问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的时候，往往采用递归算法来解决。 主要缺点：执行的效率很
15、低，尤其在边界条件设置不当的情况下，极有可能陷入死循环或者内存溢出的窘境。递归实现的代价是巨大的栈空间的耗费，那是因为过程每向前递推一次，程序将本层的实在变量（值参和变参）、局部变量构成一个“工作记录”压入工作栈的栈顶，只有退出该层递归时，才将这一工作记录从栈顶弹出释放部分空间。由此可以想到，减少每个“工作记录”的大小便可节省部分空间。例如某些变参可以转换为全局变量，某些值参可以省略以及过程内部的精简。 应用分类： 1、递归的定义问题。树结构是由递归定义的。因此，在解决与树有关的问题时，常常可以采用递归的方法。 2、解决搜索问题。因为搜索产生的节点成树状结构，所以可以用递归方法解决。这类例子很
16、多，如“N皇后”问题，全排列，哈密顿回路，图的可着色性等搜索问题。 3、实现分治思想。不难发现，在各种时间复杂度为nlogn排序方法中，大都采用了递归的形式。因为无论是分治合并排序，还是堆排序、快速排序，都存在有分治的思想。只要分开处理，就可以采用递归。其实进行分治，也是一个建树的过程。 4、用于输出动态规划的中间过程。动态规划对空间要求较高，若要保存中间过程用于输出，则可能要增加一倍的空间需求。此时，如果采用递归输出，就完全不需要浪费这宝贵的空间。 【例】 给定n（n>=1）,用递归的方法计算1+2+3+4+.+(n-1)+n。 算法分析：本题可以用递归方法求解，其原因在于它符合递归的三个条件： 1、本题是累加问题：当前和=前一次和+当前项，而前一次和的计算方法与其相同，只是数据不同s(n)=s(n-1)+n; 2、给定n,
