信息学奥赛基本算法

第0讲：算法设计概论时间复杂度空间复杂度调试方法与技巧时间复杂度O（1）常数阶O（logN）对数阶O（N）线性阶O（N＾2）平方阶O（N＾3）立方阶……………………空间复杂度O（1）常数阶O（logN）对数阶O（N）线性阶O（N＾2）平方阶O（N＾3）立方阶……………………调试方法与技巧BreakPointWatchTableDataCheckCode问题分析分析题目的模型考虑要用的算法分析算法的时空复杂度如果符合要求即可Coding第一讲：递归什么是递归？递归就是指一个函数直接或者间接地调用自身。问题的求解过程划分成相同性质的子问题的求解，而小问题的求解过程可以很容易的求出，这些子问题的解就构成里原问题的解。总体思想待求解问题的解输入变量x的函数f(x)通过寻找函数g()，使得f(x)=g(f(x-1))且已知f(0)的值，就可以通过f(0)和g()求出f(x)值推广扩展到多个输入变量x,y,z等，x-1也可以推广到x-x1，只要递归朝着“出口”的方向即可递归的三个要点递归式：如何划分子问题递归边界：递归的终止条件，也就是最小的子问题界函数：问题规模变化的函数，保证递归向边界靠拢求n！#includeiostream.hintF(intn){if(n==0)return1;elsereturnn*F(n-1);}栈递归的实现是需要栈的，这里所使用的栈是系统自带的栈栈是一种数据结构，它符合先入后出的原则解决递归问题的关键找出递推公式：即如何将问题划分为小规模的问题找到边界条件NOTICE：由于函数中的局部变量是存在系统的栈上的，如果你的局部变量过大，如较大的数组，将有可能栈溢出，这个时候要考虑全局变量和人工栈的使用。汉诺塔问题现在有三根相邻的柱子，标号为A,B,C，A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘，现在把所有盘子一个一个移动到柱子B上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方，请问至少需要多少次移动，并输出步骤。汉诺塔问题voidhanoi(intn,charA,charB,charC){if(n==1）{printf(Movedisk%dfrom%cto%c\n,n,A,C);}else{hanoi(n-1,A,C,B);printf(Movedisk%dfrom%cto%c\n,n,A,C);hanoi(n-1,B,A,C);}}前序中序求后序树中已知先序和中序求后序。如先序为：abdc,中序为：bdac.则程序可以求出后序为：dbca。前序中序求后序算法思想：先序遍历树的规则为中左右，则说明第一个元素必为树的根节点，比如上例中的a就为根节点,由于中序遍历为：左中右，再根据根节点a，我们就可以知道，左子树包含元素为：db，右子树包含元素：c，再把后序进行分解为db和c（根被消去了），然后递归的进行左子树的求解（左子树的中序为：db，后序为：db），递归的进行右子树的求解（即右子树的中序为：c，后序为：c）。如此递归到没有左右子树为止。前序中序求后序voidpronum(charpre[],intpre_s,intpre_e,charin[],intin_s,intin_e){charc;intk;if(in_sin_e)return;/*非法子树，完成。*/if(in_s==in_e){printf(%c,in[in_s]);/*子树子仅为一个节点时直接输出并完成。*/return;}c=pre[pre_s];/*c储存根节点。*/k=find(c,in,in_s,in_e);/*在中序中找出根节点的位置。*/pronum(pre,pre_s+1,pre_s+k-in_s,in,in_s,k-1);/*递归求解分割的左子树。*/pronum(pre,pre_s+k-in_s+1,pre_e,in,k+1,in_e);/*递归求解分割的右子树。*/printf(%c,c);/*根节点输出。*/}FBI树我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。FBI树是一种二叉树，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：1)T的根结点为R，其类型与串S的类型相同；2)若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2。现在给定一个长度为2N的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历序列。FBI树算法思想：本题为后序，类似于前一题，我们有相似的解法FBI树intfbi(inti,intj){if(i=j){intmid=(i+j)/2if(i!=j){fbi(i,mid);fbi(mid+1,j);}intI,B;while(i=j)if(a[i++]=='0')B++;elseI++;if(B0&&I0)cout'F';elseif(B0)cout'B';elsecout'I';}return0;}第二讲：回溯回溯回溯是一种实现枚举的算法其本质就是应用了递归这一工具所进行的枚举其优点在于可以加上一些剪枝，使得枚举的效率更加的高我们也可以将其称之为深度优先搜索DFS回溯框架inttry(……….){if(达到目标)记录结果;elsefor_each()if(满足条件){改变状态；try(………..);回复状态}}8皇后在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。分析显然，八皇后问题每行必须有一个皇后，所以，对棋盘深搜时，第一个皇后的位置不妨设为第一行，这样只对第一行进行搜索，同理，第二个皇后不妨设为第二行，以此类推。代码voidtry(intk){if(k==9){if(ok)ans++;return0}for(inti=1;i=8;i++){a[k][i]=1;try(k+1);a[k][i]=0;}}优化用一个use[]来记录是否本列被占用用一个Xright[],Xleft[]分别记录每条对角线是否被占用FibonacciF(n)=F(n-1)+F(n-2)F(0)==F(1)==1如何解决这个问题解法1递归解法intf(intn){if((n==1)||(n==0))return1;returnf(n-1)+f(n-2)}解法2递归+记忆化intf(intn){if((n==1)||(n==0))return1;calc[n]=1;if(calc[n])returnf[n];f[n]=f(n-1)+f(n-2)returnf[n];}解法3递推f[0]=1;f[1]=1;for(inti=2;i=n;i++){f[n]=f[n-1]+f[n-2];}解法4数学方法数学上可以简单推理：存在A，B使得：F(n)=A*x1^n+B*x2^n代入F(0)=0，F(1)=1，解得A=1/sqrt(5.0)，B=-1/sqrt(5.0)，即F(n)=(x1^n-x2^n)/sqrt(5.0)-----时间复杂度为O(1)，但不能保证精度解法5注意到Fibonacci数列是二阶递推数列，所以存在一个2*2的矩阵A，使得：(F[n]F[n-1])=(F[n-1]F[n-2])*A，求解得到A={{1,1},{1,0}}，然后通过递推式(FnFn-1)=(Fn-1Fn-2)*A=(Fn-2Fn-3)*A2=....=(F1F0)*An-1，然后只要计算An-1，再与矩阵(F1F0)相乘，就可以的得到Fn的值快速指数相乘法求An-1：n=ak*2^k+ak-1*2^k-1+...+a1*2+a0，其中ai=0或1，i=0,1,2...k.所以我们只需要进行logn次的运算第三讲：分治分治概念分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。分治步骤分解，将要解决的问题划分成若干规模较小的同类问题；求解，当子问题划分得足够小时，用较简单的方法解决；合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。分治分治也是运用递归方法进行的算法将大问题化为若干小问题再解决小问题最后由小问题得出大问题的解分治例子例1[找出伪币]给你一个装有16个硬币的袋子。16个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。解法1比较硬币1与硬币2的重量。假如硬币1比硬币2轻，则硬币1是伪造的；假如硬币2比硬币1轻，则硬币2是伪造的。这样就完成了任务。假如两硬币重量相等，则比较硬币3和硬币4。同样，假如有一个硬币轻一些，则寻找伪币的任务完成。假如两硬币重量相等，则继续比较硬币5和硬币6。按照这种方式，可以最多通过8次比较来判断伪币的存在并找出这一伪币。解法2另外一种方法就是利用分而治之方法。假如把16硬币的例子看成一个大的问题。第一步，把这一问题分成两个小问题。随机选择8个硬币作为第一组称为A组，剩下的8个硬币作为第二组称为B组。这样，就把16个硬币的问题分成两个8硬币的问题来解决。第二步，判断A和B组中是否有伪币。可以利用仪器来比较A组硬币和B组硬币的重量。假如两组硬币重量相等，则可以判断伪币不存在。假如两组硬币重量不相等，则存在伪币，并且可以判断它位于较轻的那一组硬币中。最后，在第三步中，用第二步的结果得出原先16个硬币问题的答案。若仅仅判断硬币是否存在，则第三步非常简单。无论A组还是B组中有伪币，都可以推断这16个硬币中存在伪币。因此，仅仅通过一次重量的比较，就可以判断伪币是否存在。分治应用：归并排序排序的方法：冒泡排序选择排序快速排序桶排序基数排序归并排序归并排序归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。归并排序我们可以在O(n)的时间内将两个有序的序列合并每次我们将一个序列平均分成两半，分别进行排序，之后再将其合并复杂度分析时间复杂度为O(nlogn)这是该算法中最好、最坏和平均的时间性能。空间复杂度为O(n)比较操作的次数介于(nlogn)/2和nlogn-n+1。赋值操作的次数是(2nlogn)。归并算法的空间复杂度为：0(n)归并排序比较占用内存，但却效率高且稳定的算法。优点归并排序是稳定的排序。即相等的元素的顺序不会改变。如输入记录1(1)3(2)2(3)2(4)5(5)（括号中是记录的关键字）时输出的1(1)2(3)2(4)3(2)5(5)中的2和2是按输入的顺序。这对要排序数据包含多个信息而要按其中的某一个信息排序，要求其它信息尽量按输入的顺序排列时很重要。这也是它比快速排序优势的地方。例子如设有数列{6，202，100，301，38，8，1}初始状态：[6][202][100][301][38][8][1]比较次数i=1[6202][100301][838][1]3i=2[6100202301][1838]4i=3[16838100202301]4总计：11次代码voidMergeSort(intarray[],intfirst,intlast){intmid=0;if(firstlast){mid=(first+la