计算基础教程 6

授课内容递归学时2教学目标知识目标理解递归的核心思想与“递推+回归”工作流程掌握斐波那契数列的递归求解方法理解备忘录技术的原理及应用场景掌握汉诺塔、数的计算的递归解题思路能力目标提升复杂问题递归分解与规律提炼能力强化递归算法逻辑分析与流程设计能力培养递归优化与时空权衡的工程实践能力重点与难点重点递归的核心思想与工作流程斐波那契数列的递归实现与优化方法备忘录技术的应用的核心要点汉诺塔问题的递归解题步骤与逻辑难点理解递归的递推与回归过程，梳理递归逻辑掌握备忘录技术的应用，实现递归优化教学内容第一部分：课程导入1、点名与签到2、课程重要性阐述本章承接枚举法，学习高效的递归算法思想递归是算法竞赛、考级中高频考点，实用性极强递归可简化复杂问题求解，适配多种典型场景掌握递归优化技巧，提升算法运行效率通过实例练习，深化算法设计与问题解决能力第二部分：新课讲解一、递归概述1、递归算法思想递归是一种编程方式，但同时还是一种算法思想。递归作为一种算法思想，其核心是把复杂的问题分解成简单的问题，逐级分解下去，直到问题的规模小到可以直接求解，然后再逐级向上回溯生成较为复杂问题的解，直到解决最初的问题为止2、递归的工作流程递归包含了“递推”和“回归”二个过程。递推：把复杂的问题分解为比原问题简单一些的子问题，以便于求解；回归：当获得简单问题的答案后，逐步返回，依次得到复杂问题的解。二、Fibonacci数列1、概述Fibonacci数列（斐波那契数列）是由古代意大利数学家莱昂纳多•斐波那契在研究兔子繁殖问题时提出来的。Fibonacci数列以如下递归的方式定义：F(0)=0F(1)=1F(n)=F(n-1)+F(n-2)（n≥2）2、编程求解Fibonacci数列的各项可以通过一个简单的循环来求解，也可以通过递归方式来求解。intfib(inti) //返回第i项的值{ if(i==0)return0; if(i==1) return1;returnfib(i-2)+fib(i-1);}3、消除重复求解在使用递归版本求解Fibonacci数列时，会存在针对同一子问题的重复求解问题，以下图为例进行说明。为了求fib(5)的值，需要分别计算fib(4)和fib(3)，而求fib(4)时，又需要计算fib(3)和fib(2)，这样fib(3)就被重复计算了二次。使用“备忘录”解决重复求解问题，就是建立一个数组，将fib函数的参数值i及其对应的求解结果记录下来。以后再要求计算fib(i)时，先查询一下“备忘录”中有没有fib(i)的值，若有则直接使用；若没有才需要进行计算，并将计算结果也记录到“备忘录”中。代码如下：inta[100]={0,1};//备忘录，a[i]存储fib(i)的返回值intfib(inti){ if(a[i]>0||i==0)returna[i];//备忘录内已有记录时 a[i]=fib(i-1)+fib(i-2); //初次求解，先保存结果 returna[i];}三、Hanoi塔问题1、问题介绍Hanoi塔（汉诺塔）问题是从一个古老的印度传说演变而来的，其问题是这样的：Hanoi塔由n个大小不同的圆盘和三根木柱a，b，c组成。开始时，这n个圆盘由大到小依次套在a柱上，如下图所示。要求把a柱上n个圆盘按下述规则移到c柱上： 一次只能移一个圆盘 圆盘只能在三个柱上存放 在移动过程中，不允许大盘压小盘试给出全部盘子的移动过程。2、算法分析我们先考虑最后一个盘子是如何移动的，可以简单分为三个步骤：（1）把n-1个盘子由A移到B；（2）把第n个盘子由A移到C；（3）把n-1个盘子由B移到C；3、程序见课本四、数的计算1、题目要求找出具有下列性质数的个数（包括输入的自然数n）。先输入一个自然数n（n≤1000），然后对此自然数按照如下方法进行处理：不作任何处理；在它的左边加上一个自然数，但该自然数不能超过原数的一半；加上数后，继续按此规则进行处理，直到不能再加自然数为止。【输入格式】一个自然数n（n≤1000）【输出格式】一个整数，表示满足条件的数的个数2、分析如果n=100，需要依次在前面添加1～50之一；然后，针对新添加的部分（1～50之一），再每次取其一半添加在其前面。显然，本过程是递归的。在递归过程中会存在重复求解相同子问题的情况，因此，需要使用“备忘录”技术来提高程序