高中信息技术 全国青少年奥林匹克联赛教案 递归算法

1、资讯科学奥塞梯的基本算法(递归算法)定义递归算法：如果对象的说明包含本身，则牙齿对象称为递归。递归描述的牙齿算法称为递归算法。首先，我们来看看众所周知的故事之一。从前有座山，山上有座庙，庙里有个老和尚在给小和尚讲故事故事。他从前有座山，山上有座庙，庙里有个老和尚在故事给小和尚讲故事。他说。上述故事本身是递归的，用递归算法描述。procedure bonze-tell-story；贝金If演讲中断了，then故事结束。Else begin从前有山，山里有一座庙，庙里有一个小和尚在故事讲故事。(威廉莎士比亚，哈姆雷特)bonze-tell-story；终端End在上述递归案例中，很容易知道递归算法

2、存在的两个茄子必要条件。(1)必须有递归结束条件。(2)进程的说明包括其本身。在迭代算法设计中，如何将问题转换为迭代问题是初学者问题。让我们分析汉诺塔问题，看看如何解决重复算法问题。递归算法应用节目示例1:汉诺塔问题有三根a、b和c的支柱，如下图所示。A柱上从小到大堆积了N堆盘子，现在所有的盘子都要从A柱移动到C柱。移动中可以使用B柱。移动具有以下要求：(1)一次只能移动一个盘子。(2)大碟子不能放在小盘子上。(3)只能放在3根盘子柱上。算法分析：盘子人数多的时候，问题很复杂，所以我们先分析一下简单的情况。如果只有一个盘子，只需一步，直接从A柱移动到C柱。如果是2个盘子，则必须共移动3个步骤：

3、(1)将a柱上的小盘子柱移动到b柱。(2)将a柱上的大碟子移到c柱上。(3)将b列的大盘子移到c柱上。N牙齿比较大的时候，需要很多步骤来完成，我们首先要把复杂的移动过程变成简单的移动过程，如果A柱中最大的盘子可以移动到C柱中，首先要把上面的N-1盘子从A柱移动到B柱中做好准备。根据这种思维方式，N个盘子移动过程可以分为3个阶段。(1)将a柱上方的一个N-1盘子移动到b柱。(2)将a柱的其他盘子之一移到c柱。(3)将B柱上方的一个N-1盘子移动到C柱。在这里，N-1盘子移动过程可以用同样的方式分为三个阶段，将移动过程转换为迭代过程，直到只剩下一个盘子，然后根据盘子移动方法递归结束。(注：N-1-

4、1-1-1-1-1-1-1-1-1-1)。迭代流程：步骤Hanoi (n、a、b、c: integer)；使用b柱作为中间柱，将n个盘子柱从a柱移动到c柱贝金If N=1 then write(A，-，C)直接从A到C移动盘子Else begin河内(n-1，a，c，b)；使用c柱作为中间柱，从N-1盘子a柱移动到b柱Write (a，-，c)；将其他盘子之一从a移动到c 河内(n-1，b，a，c)；使用柱作为中间柱，从N-1盘子b柱移动到c柱EndEnd如上例所示，在使用递归算法时，首先掌握简单情况的解法，然后将复杂情况总结为更简单的情况。资讯科学奥塞梯中问题的结构或处理的数据本身是递归定义

5、的。这种问题很适合用递归算法(递归)解决。对于这种问题，分解为具有相同性质的多个子问题。如果子问题解决，原来的问题也解决了。示例2查找优先级(NOIP2001pj)说明问题提出一棵二叉树的中旬和后期。求其优先权。(商定的树节点用另一个长度为8的大写字母表示。）输入样本:BADC BDCA输出：ABCD算法分析：首先，我们来看看三个茄子巡回的定义。首先访问根节点，然后通过左侧子树，最后通过右侧子树。中间顺序遍历依次遍历左侧子树、根节点和右侧子树。后续遍历是依次遍历左侧子树、右侧子树和根节点。如遍历的定义所示，最后一个字符是牙齿树的根节点。在中间顺序排序中，根节点前面是左侧的子树，根节点后面是右侧

6、的子树。我们可以通过后面的顺序排列得到根节点，然后通过中间顺序位置确定左右子树，可以将左右子树看作单独的树。这样，把一棵树分解成具有相同性质的两个子树，继续递归下去，分解的子树空的时候递归结束，递归进行的过程中，先按照遍历的规则输出得到的每个根节点，输出的结果就是原来问题的解决方法。源代码program noip 2001 _ 3；Var z，h :字符串；Proceduremake (z，h3360字符串):z为中间顺序，h为后续顺序Var s、m : integer:贝金M:=长度(h)；m是树的长度写入(hm)；输出根节点S:=pos(hm，z)；在中间顺序中查找根节点的位置If S1

7、then make(复制(z，1，s-1)，复制(h，1，s-1)；左子树处理If ms then make (copy (z，S1，m-s)，copy (h，s，m-s)；处理右侧子树End贝金readln(z)；readln(h)；梅凯(z，h)；终端。递归算法不仅是解决递归描述的问题，而且在很多其他问题上，递归思想(如回溯法、分治法、动态规划法等算法都可以使用递归思想)，所写的节目更为简洁。例如，在以前的回溯法2 数的划分问题中递归求解，程序非常短、高效，源程序如下：Varn，k:交错；Tol:longintProceduremake (sum，t，d : integer)；Var i:

8、integer:贝金If d=k then inc(tol)else for I :=t to sum div 2 do make(sum-I，I，D1)；End贝金Readln(n，k)；tol :=0；Make(n，1，1)；writeln(tol)；终端。某些问题本身是递归定义的，但不适用于递归算法(Fibonacci)序列，例如Fibonacci序列。递归定义如下：F(n)=1 (n=1，2)F(n)=F(n-2) F(n-1) (n2)使用递归过程说明如下：funtion FB(n : integer): integer:贝金If n3 then fb:=1else FB :=FB(n-1)FB(n-2)；End上述递归过程一次生成两个新调用，迭代次数呈指数增长，变为时间复杂度O(2n)，变为非递归。x :=1；y :=1；For i:=3 to n do贝金z :=y；Y:=x yx :=z；