[学科竞赛]信息学奥赛基本算法

《[学科竞赛]信息学奥赛基本算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第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）立方阶……………………调试方法与技巧BreakPointWatchTableDataCheckCode问题分析分析题目的模型考虑要用的算法分析算法的时空复杂度如果符合要求即可Coding第一讲：递归什么是递归？递归就是指一个函数直接或者间接地调用自身。问

2、题的求解过程划分成相同性质的子问题的求解，而小问题的求解过程可以很容易的求出，这些子问题的解就构成里原问题的解。总体思想待求解问题的解输入变量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！#in

3、cludeintF(intn){if(n==0)return1;elsereturnn*F(n-1);}栈递归的实现是需要栈的，这里所使用的栈是系统自带的栈栈是一种数据结构，它符合先入后出的原则解决递归问题的关键找出递推公式：即如何将问题划分为小规模的问题找到边界条件NOTICE：由于函数中的局部变量是存在系统的栈上的，如果你的局部变量过大，如较大的数组，将有可能栈溢出，这个时候要考虑全局变量和人工栈的使用。汉诺塔问题现在有三根相邻的柱子，标号为A,B,C，A柱子上从下到上按金

4、字塔状叠放着n个不同大小的圆盘，现在把所有盘子一个一个移动到柱子B上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方，请问至少需要多少次移动，并输出步骤。汉诺塔问题voidhanoi(intn,charA,charB,charC){if(n==1）{printf("Movedisk%dfrom%cto%c",n,A,C);}else{hanoi(n-1,A,C,B);printf("Movedisk%dfrom%cto%c",n,A,C);hanoi(n-1,B,A,C);}}前序中序求

5、后序树中已知先序和中序求后序。如先序为：abdc,中序为：bdac.则程序可以求出后序为：dbca。前序中序求后序算法思想：先序遍历树的规则为中左右，则说明第一个元素必为树的根节点，比如上例中的a就为根节点,由于中序遍历为：左中右，再根据根节点a，我们就可以知道，左子树包含元素为：db，右子树包含元素：c，再把后序进行分解为db和c（根被消去了），然后递归的进行左子树的求解（左子树的中序为：db，后序为：db），递归的进行右子树的求解（即右子树的中序为：c，后序为：c）。如此递归到没有左右子树为止。前

6、序中序求后序voidpronum(charpre[],intpre_s,intpre_e,charin[],intin_s,intin_e){charc;intk;if(in_s>in_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(p

7、re,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

8、可以构造出一棵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=