项目5任务5.3 汉诺塔游戏的实现

任务5.3汉诺塔游戏的实现主讲：陈静目录教学目标与重难点函数递归调用函数嵌套调用递归与嵌套对比分析任务实施：汉诺塔程序实现教学总结010203040506教学目标与重难点01教学目标知识目标能力目标理解函数递归调用的概念、核心要素及应用场景掌握函数嵌套调用的原理与执行流程能够运用递归思想解决汉诺塔等经典问题培养将复杂问题分解为简单子问题的逻辑思维能力提升代码调试与程序分析能力素养目标培养"化繁为简、分而治之"的科学思维，能将复杂问题逐层拆解为相似子问题。树立"脚踏实地、层层递进"的耐心与严谨，能清晰追踪递归的调用与返回逻辑。学习刘徽"割圆术"与祖冲之精益求精的工匠精神，敢于挑战复杂问题并持之以恒。教学重难点递归调用的核心要素递归基、递归步骤、收敛性汉诺塔问题的递归实现思路将问题分解为子问题，通过递归完成盘子移动函数嵌套调用的执行过程理解调用栈的压栈与出栈机制理解递推与回归过程递归调用的"递推"与"回归"两个阶段正确设置递归终止条件避免无限递归，确保递归能够收敛掌握移动步骤推导逻辑汉诺塔移动步骤的数学推导与实现函数递归调用02递归调用概念定义函数直接或间接调用自身的过程递归的本质特征适用场景数学问题阶乘、斐波那契数列数据结构树遍历、图遍历算法设计分治算法、动态规划核心要素递归基确定递归何时终止，避免无限递归递归步骤将原问题分解为更小的同构子问题收敛性每次调用使问题规模减小，最终达到递归基递归调用的优缺点优点代码简洁优雅，表达力强直接反映问题的数学定义和递归性质适用于处理递归定义的数据结构（如树、图）可以简化复杂问题的解决方案缺点函数调用开销较大（栈帧创建、参数传递、返回地址保存）可能引起栈溢出问题存在重复计算问题（如斐波那契数列）某些情况下效率不如迭代实现递归使用注意事项1必须设置递归终止条件缺少递归基会导致无限递归和栈溢出2确保递归深度可控系统栈空间有限，避免过深递归3避免重复计算对于存在重叠子问题的情况，考虑使用记忆化技术4考虑尾递归优化某些编译器支持尾递归优化，可减少栈空间使用课堂互动：递归思想讨论思考问题讨论要点为什么递归必须有终止条件？如果递归深度过大，会发生什么问题？生活中有哪些现象体现了递归思想？递归的本质将大问题分解为小问题栈空间限制栈空间限制与递归深度关系现实案例俄罗斯套娃、镜子反射、分形图案训练项目：递归函数编写项目1：计算阶乘编写递归函数

factorial(intn)递归基：0!=1，1!=1递归步骤：n!=n×(n-1)!项目2：斐波那契数列编写递归函数

fibonacci(intn)递归基：F(0)=0，F(1)=1递归步骤：F(n)=F(n-1)+F(n-2)要求输出前10项斐波那契数列函数嵌套调用03嵌套调用概念在一个函数体内调用另一个函数的过程定义多层次嵌套C语言支持多层次的函数嵌套调用平行独立函数定义互相平行、独立，不能嵌套定义模块化编程可以嵌套调用函数，实现模块化编程执行流程1遇函数调用语句，流程转去被调函数2执行完被调函数后，返回调用位置继续执行3逐层调用，逐层返回嵌套调用的优势模块化设计将复杂任务分解为多个小函数提高代码可读性和可维护性代码复用避免重复代码，减少程序体积占位保持结构对称层次清晰函数调用层次清晰便于调试和维护团队协作不同开发者可以独立开发不同模块的函数嵌套调用最佳实践控制嵌套深度避免过深嵌套（通常不超过5层）函数职责单一每个函数只完成一个明确的任务合理使用局部变量避免函数间不必要的耦合注意参数传递大型数据结构考虑使用指针传递课堂互动：嵌套调用分析案例分析：几何计算程序main()printGeometryInfo()calculateCircleArea()/calculateSphereVolume()讨论问题嵌套调用的执行顺序是什么？为什么需要函数声明？如何避免嵌套调用中的参数传递错误？注意：先调用后返回关键：声明在前，调用在后函数调用栈示意1.main()

发起调用2.printGeometryInfo()

入栈执行3.calculateCircleArea()/calculateSphereVolume()

入栈4.逐层返回，栈顶弹出训练项目：嵌套调用实践注意精度三层嵌套验证结果项目要求编写几何计算程序实现多层函数嵌套调用计算圆面积和球体积函数设计calculateCircleArea(doubleradius)calculateSphereVolume(doubleradius)printGeometryInfo(doubleradius)输出示例半径

5.00：圆面积

78.54球体积

523.60实施步骤定义基础函数：先实现

calculateCircleArea

和

calculateSphereVolume，分别使用公式πr²和4/3πr³创建整合函数：编写

printGeometryInfo，内部调用上述两个函数获取计算结果参数传递：确保半径参数正确传递给各层函数，注意double类型的精度处理格式化输出：使用printf或cout按示例格式输出，保留两位小数递归与嵌套对比分析04递归与嵌套对比对比项函数递归函数嵌套调用关系函数直接或间接调用自身一个函数调用另一个不同的函数核心要素

必须包含终止条件

无自我调用要求栈空间

每次调用创建新栈帧，深度大

调用深度受栈大小限制应用场景分治算法、树/图遍历、递归定义问题

模块化程序设计、代码复用

性能

函数调用开销大，可能栈溢出

函数调用开销可控

代码特点简洁优雅，数学表达力强

结构清晰，易于维护

任务实施：汉诺塔程序实现05汉诺塔问题导入传说背景印度神庙中有三根柱子，其中一根穿有64个黄金圆盘大盘在下、小的在上，需按规则移动到另一根柱子每次只能移动一个圆盘，小盘必须始终在大盘之上学习目标理解递归思想在经典问题中的应用掌握汉诺塔移动步骤的推导逻辑问题本质将复杂移动问题分解为相似子问题通过递归调用优雅解决实施思路递归实现移动输出每一步移动过程，展示递归算法执行流程嵌套调用演示主函数调用hanoi函数，展示函数嵌套机制计算最少步数公式：2n-1，递归计算理论最优解交互与可视化用户输入圆盘数量(1~10)，清晰格式显示每步移动核心函数签名hanoi(intn,charfrom,charvia,charto)countSteps(intn)printSeparator()hanoi()递归移动函数：参数n为圆盘数，from为起始柱，via为辅助柱，to为目标柱。将n-1个圆盘从from移到via，再将第n个圆盘从from移到to，最后将n-1个圆盘从via移到tocountSteps()递归计算步数：利用公式2n-1的递归形式，当n=1时返回1，否则返回2×countSteps(n-1)+1，验证移动过程的理论最优性printSeparator()打印分隔线：作为嵌套调用示例，在输出中插入可视化分隔符，增强程序输出的可读性和结构化展示效果任务分析if(n==1)直接移动;else{分解为三步递归}递归出口当n==1时，直接移动圆盘第一步：移动n-1个圆盘将上面n-1个圆盘从起始柱经由目标柱移动到辅助柱第二步：移动第n个圆盘将第n个圆盘移动到目标柱第三步：再移动n-1个圆盘将n-1个圆盘从辅助柱经由起始柱移动到目标柱输出总移动步数程序运行后需输出完成汉诺塔移动的总步数验证计算结果与countSteps函数的计算结果进行验证，确保正确性程序实现要点全局变量stepCount：记录移动步数递归逻辑hanoi(n-1,from,to,via)：移动上面n-1个圆盘移动第n个圆盘到目标柱hanoi(n-1,via,from,to)：移动n-1个圆盘到目标柱输入验证圆盘数量范围：1~10非法输入提示并退出课堂互动：汉诺塔演示动手实践1输入圆盘数量在程序中设置n=3，初始化汉诺塔状态2观察移动步骤运行程序，记录每一步的圆盘移动轨迹3统计总移动步数程序执行完毕后，统计实际输出的步数4验证公式对比实际步数与理论值

2³-1=7思考问题为什么汉诺塔问题适合用递归解决？移动n个圆盘最少需要多少步？如何优化程序避免重复计算？拓展讨论64个圆盘需要移动多少步？递归深度与圆盘数量的关系训练项目：汉诺塔程序完善项目要求功能扩展提交内容实现完整程序完整的汉诺塔游戏程序添加动画效果移动动画效果（可选）步数统计验证步数统计与验证功能自定义柱子名称支持自定义柱子名称移动历史记录添加移动历史记录反向移动功能实现反向移动功能源代码文件完整的源代码文件运行截图程序运行截图设计说明设计思路说明文档教学总结06知识要点回顾递归调用核心要素：递归基、递归步骤、收敛性必须设置终止条件，避免无限递归适用于可分解为相似子问题的问题嵌套调用函数间协作的编程机制实现模块化设计和代码复用控制嵌套深度，保持层次清晰汉诺塔实现递归思想