4.3 非数值计算（神奇的递归） 课件-2023—2024学年高中信息技术教科版（2019）必修1

高中信息技术 必修1 数据与计算 4.3 非数值计算 第二课时 神奇的递归 1 学习目标 01 02 运用合适的算法形成解决问题的方案； 了解算法中的分治思想； 03 体验递归算法，并结合具体问题开展编程实践。 4.3 非数值计算——神奇的递归 2 项目内容 本节我们将围绕“生活中的算法”项目，尝试用“算法的眼睛”看待生活，用“算法的思维”去解决实际问题。 项目任务 任务一：巧翻字典 任务二：玩转“汉诺塔”游戏 本节任务 3 玩“汉诺塔”游戏 “汉诺塔”游戏由来：有一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。 4.3 非数值计算——神奇的递归 4 4.3 非数值计算——神奇的递归 “汉诺塔”游戏规则来： 1、有三根相邻的柱子，标号为A,B,C。 2、A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘。 3、现在把所有盘子一个一个移动到柱子B上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方。 A B C 玩“汉诺塔”游戏 5 4.3 非数值计算——神奇的递归 请打开学案中的“汉诺塔”游戏，赶快体验一下吧！ 玩“汉诺塔”游戏 6 4.3 非数值计算——神奇的递归 分析玩的过程 以3个木盘为例 A B C A B A C 7 4.3 非数值计算——神奇的递归 分析玩的过程 以3个木盘为例 A B C C B A C 8 4.3 非数值计算——神奇的递归 分析玩的过程 以3个木盘为例 C B A B C B A 9 4.3 非数值计算——神奇的递归 分析玩的过程 以3个木盘为例 A B C A C 10 总结移动规律 三步移动 将A上面两个木盘从A B 将A最下面的一个木盘从A C 将B上面两个木盘从B C 将A上面一个木盘从A C 将B最下面一个木盘从A B 将C上面一个木盘从C B 将B上面一个木盘从B A 将B最下面一个木盘从B C 将A上面一个木盘从A C 3个木盘的移动问题成功解决了， 就可以解决更多木盘的移动问题了。 11 知识探究：递归 直接或间接地调用自身的方法称为递归。可以将递归简单类比为具有自相似性重复的事物。 递归是计算科学领域中一种重要的计算思维模式。它既是一种抽象表达的手段，也是一种问题求解的重要方法。 12 知识探究：递归函数 递归函数是只用函数自身来定义该函数的方法。如斐波那契数列“1,1,2,3,5,8,13……”,可以递归定义为： F(n)= 1(n=1或n=2) F(n-1)+F(n-2)(n>2) 13 知识探究：递归的重要组成 递推关系是递归的重要组成； 边界条件是递归的另一要素（保证递归能在有限次计算后得出结果，而不会产生无限循环地情况） F(n)= 1(n=1或n=2) F(n-1)+F(n-2)(n>2) 边界条件 递推关系 14 知识探究：递归的基本思想 递归的基本思想是把规模较大的问题层层转化为规模较小的同类问题求解。对递归而言，递推与回归，二者缺一不可。 1）分：将原有问题分解成K个子问题。 2）治：对这K个子问题分别求解。如果子问题的规模仍然不够小，则将其再分解为K个子问题，如此进 行下去，直到问题足够小时，就很容易求出子问题的解。 3）合：将求出的小规模问题的解合并为一个更大规模问题的解，自下而上逐步求出原问题的解。 递归可用“分”，“治”，“合”三个字概括 15 “汉诺塔”游戏程序实现 hanoi(盘子数，起始杆，过渡杆，目标杆) hanoi(n,A,B,C) 从A移到C hanoi(n-1,B,A,C) hanoi(n-1,A,C,B) 前n-1个木盘从A移动到了B 前n-1个木盘从B移动到了C 汉诺塔递归过程图示 16 “汉诺塔”游戏程序实现 上机实践 17 “汉诺塔”游戏程序执行的过程 def move(n,s,m,t): if n==1: print(s,'-->',t) move(n-1,s,t,m) print(s,'-->',t) move(n-1,m,s,t) move(3,'a','b','c') move(3,'a','b','c')调用 move(2,'a','c','b') print('a','-->','c') move(2,'b