C++函数递推递归ppt课件.ppt

《C++函数递推递归ppt课件.ppt》由会员分享，可在线阅读，更多相关《C++函数递推递归ppt课件.ppt（77页珍藏版）》请在金锄头文库上搜索。

1、 C 语言程序设计 第九讲函数 递推 递归 1 第九讲 函数 递推 递归递推递推是计算机数值计算中的一个重要算法 思路 通过数学推导 将复杂的运算化解为若干重复的简单运算 以充分发挥计算机长于重复运算的特点 递推法特点 从一个已知的事实出发 按一定规律推出下一个事实 再从这个新的已知事实出发 再向下推出一个新的事实 2 第九讲 函数 递推 递归 递推举例 1 例 猴子吃桃问题 猴子第1天摘下若干桃子 当即吃了一半 还不过瘾 又多吃了一个 第2天早上又将剩下的桃子吃掉一半 又多吃了一个 以后每天早上都吃了前一天剩下的一半另加一个 到第10天早上想再吃时 就只剩下一个桃子了 问第1天猴子共摘了多少

2、桃子 3 第九讲 函数 递推 递归 解题思路 假设用S i 表示第i天没吃之前的桃子数目 则S 1 即为第1天所摘的桃子数 S 10 S 9 1 2 1第10天没吃之前的桃子数 4 第九讲 函数 递推 递归 一般形式 S i S i 1 1 2 1 i 2 3 10 这个公式可用于知第1天没吃之前的桃子数推算第2天没吃之前的 再推算第3天没吃之前的 现在要求的是第1天没吃之前的 能否倒过来 先知第10天没吃之前的的再反推第9天没吃之的 直到第1天没吃之前的 为此将上式改写为 S i 1 2 S i 1 i 10 9 8 2 5 第九讲 函数 递推 递归 程序 大连理工大学盘锦校区基础教学部6

3、6 第九讲 函数 递推 递归分析 一般形式 S i 1 2 S i 1 i 10 9 8 2 初始 s2 1 S 10 1 i 9 s1 2 s2 1 s2 s1 s1 2 s2 1 s2 s1 s1 2 s2 1 s2 s1 S 9 2 S 10 1 s2 s1 S 9 S 8 2 S 9 1 s2 s1 S 8 S 7 2 S 8 1 s2 s1 S 7 i 8 i 7 i 6 s1 2 s2 1 s2 s1 S 6 2 S 7 1 s2 s1 S 6 7 第九讲 函数 递推 递归 i 5 s1 2 s2 1 s2 s1 S 5 2 S 6 1 s2 s1 S 5 S 4 2 S 5 1

4、s2 s1 S 4 S 3 2 S 4 1 s2 s1 S 3 S 2 2 S 3 1 s2 s1 S 2 S 1 2 S 2 1 s2 s1 S 1 i 4 s1 2 s2 1 s2 s1 s1 2 s2 1 s2 s1 s1 2 s2 1 s2 s1 s1 2 s2 1 s2 s1 i 3 i 2 i 1 8 第九讲 函数 递推 递归 递推举例 2 递推数列一个数列从某一项起 它的任何一项都可以用它前面的若干项来确定 这样的数列称为递推数列 表示某项与其前面的若干项的关系就称为递推公式 例如自然数1 2 n的阶乘就可以形成如下数列 1 2 3 n 1 n 另fact n 为n阶乘 依据后项

5、与前项的关系可以写出递推公式 fact n n fact n 1 通项公式 fact 1 1 边界条件 9 第九讲 函数 递推 递归 递推算例 3 递推算法程序实现 有了通项公式和边界条件后 采用循环结构 从边界条件出发 利用通项公式通过若干步递推过程就可以求出结果 例 王小二自称刀工不错 有人放一张大的煎饼在砧板上 问他 饼不许离开砧板 切100刀最多能分成多少块 10 第九讲 函数 递推 递归 分析 切一刀 切二刀 切三刀切四刀 令q n 表示切n刀能分成的块数 由上图可知q 1 1 1 2q 2 1 1 2 4q 3 1 1 2 3 7q 4 1 1 2 3 4 11 11 第九讲 函数

6、 递推 递归 分析 切一刀 切二刀 切三刀切四刀 在切法上是让每两条线都有交点 用归纳法可得出q n q n 1 nq 0 1 边界条件 12 第九讲 函数 递推 递归 递推算例 3 参考程序 13 第九讲 函数 递推 递归递归递归算法在可计算理论中占有重要地位 它是算法设计的有力工具 对于拓展编程思路非常有用 就递归算法而言不涉及高深数学知识 只不过初学者建立起递归概念不太容易 看一个简单的例子 14 第九讲 函数 递推 递归递归有5个人坐在一起 问第5个人多少岁 他说比第4个人大两岁 问第4个人岁数 他说比第3个人大两岁 问第3个人 又说比第2个人大两岁 问第2个人 说比第1个人大两岁 最

7、后问第1个人 他说是10岁 请问第5个人多大 解题思路 假设用age i 表示第i个人的岁数 则 借助循环结构采用递推方法求解 15 第九讲 函数 递推 递归 一般形式 age n 10age n age n 1 2 n 1 n 2 16 第九讲 函数 递推 递归 分析 上述求解是从求解目标出发 即将第n个人的年龄表示第 n 1 个人的年龄 再回溯到第 n 2 个人的年龄 直到第1个人的年龄 回溯阶段 然后 采用递推方法 从第1个人的已知年龄推算第2个人的年龄 在推算第3个人的年龄 直到推算出第5个人的年龄 递推阶段 这是一个递归问题 对它的求解可以分成回溯和递推两个阶段 显而易见 如果不希望

8、递归过程无限制的进行下去 必须有一个结束递归过程的条件 如 age 1 10 17 第九讲 函数 递推 递归 计算年龄函数 intage intn intc if n 1 c 10 else c age n 1 2 returnc 18 第九讲 函数 递推 递归 递归调用 在调用一个函数的过程中又出现直接或间接地调用该函数本身 称为函数的递归 recursive 调用 C 允许函数的递归调用 例 intf intx inty z z f y return2 z 19 第九讲 函数 递推 递归 递归调用 直接调用 间接调用 注意 上述两种情况都是无终止的自身调用 显然 程序中不应该出现这种无终止

9、的调用 而只应出现有限次的 有终止的递归调用 可以用if语句控制 实现递归调用结束 20 第九讲 函数 递推 递归 递归函数 包含递归调用的函数 称为递归函数 计算年龄函数 intage intn intc if n 1 c 10 else c age n 1 2 returnc 21 第九讲 函数 递推 递归 递归函数 计算年龄递归函数执行过程 22 第九讲 函数 递推 递归 计算年龄程序 23 第九讲 函数 递推 递归 递归算例 2 用递归方法计算n 算法思路 若n 10 则n 10 9 定义函数fact n 表示计算n 的函数 则有 24 第九讲 函数 递推 递归 递归算例 2 阶乘计算

10、递归函数 iinnttffaacctt iinnttnn intc if cn n 0f anct n 11 c 1 reelstuernc c n fact n 1 returnc 结束递归条件 25 第九讲 函数 递推 递归 递归算例 3 用递归函数计算组合数 C m n 即从m个数中取n个数的组合数 C m n C m 1 n C m 1 n 1 C m n 0 m 0 n 0 C m n 1 m n C m n m n 1 26 第九讲 函数 递推 递归 递归算例 3 27 第九讲 函数 递推 递归 递归算例 4 例 猴子吃桃问题 猴子第1天摘下若干桃子 当即吃了一半 还不过瘾 又多吃

11、了一个 第2天早上又将剩下的桃子吃掉一半 又多吃了一个 以后每天早上都吃了前一天剩下的一半另加一个 到第10天早上想再吃时 就只剩下一个桃子了 问第1天猴子共摘了多少桃子 28 第九讲 函数 递推 递归 解题思路 假设用S i 表示第i天没吃之前的桃子数目 则S 1 即为第1天所摘的桃子数 S 10 S 9 1 2 1第10天没吃之前的桃子数 29 第九讲 函数 递推 递归 一般形式 S i S i 1 1 2 1 i 2 3 10 这个公式可用于知第1天没吃之前的桃子数推算第2天没吃之前的 再推算第3天没吃之前的 现在要求的是第1天没吃之前的 能否倒过来 先知第10天没吃之前的的再反推第9天

12、没吃之的 直到第1天没吃之前的 为此将上式改写为 30 第九讲 函数 递推 递归 一般形式 S i 1 2 S i 1 i 2 3 4 10 则S 1 即为第1天所摘的桃子数 S 1 2 S 2 1 S 2 2 S 3 1 S 8 2 S 9 1 S 10 1 31 第九讲 函数 递推 递归 递归函数 intcount intn intc if n 10 c 1 elsec 2 count n 1 1 returnc 这样可以吗 有没有问题 如果出现调用语句 count 11 32 第九讲 函数 递推 递归 递归函数 intcount intn intc if n 10 return 1 if

13、 n 10 c 1 elsec 2 count n 1 1 returnc 33 第九讲 函数 递推 递归 递归方法 递归实现 在时间和空间上的开销比较大 但符合人们的思路 程序容易理解 递归函数 只须写出递归公式和递归结束条件 即边界条件 即可很容易写出递归函数 34 第九讲 函数 递推 递归 局部变量和全局变量 一个程序可以包括若干个源程序文件 文件模块 每个源程序文件又包括若干个函数 在每个函数中和函数外都可以定义变量 这些在不同地方定义的变量是否都在程序的全部范围内有效 如果不是 他们的有效范围是什么呢 35 第九讲 函数 递推 递归 局部变量和全局变量 局部变量在一个函数内部定义的变

14、量是内部变量 它只在本函数范围内有效 换句话说只有在本函数内才能使用它们 在此函数之外是不能使用这些变量的 同样的 在复合语句中定义的变量只在复合语句内范围内有效 36 第九讲 函数 递推 递归 floatf1 inta 函数f1 intb c charf2 int inti j intmain intm n intp q b c有效 a有效 x inty i j有效 函数f2 x y有效 主函数 p q在复合语句中有效 m n有效 37 第九讲 函数 递推 递归 a也只在f1函数中有效 其他函数不能调用 大连理工大学盘锦校区基础教学部 说明 1 主函数main中定义的变量 m n 也只在主函

15、数中有效 不会因为在主函数中定义而在整个文件或程序中有效 主函数也不能使用其他函数中定义的变量 2 不同函数中可以使用同名的变量 它们代表不同的对象 互不干扰 例如 在f1函数中定义了变量b和c 倘若在f2函数中也定义变量b和c 它们在内存中占不同的单元 不会混淆 3 可以在一个函数内的复合语句中定义变量 这些变量只在本复合语句中有效 这种复合语句也称为分程序或程序块 4 形式参数也是局部变量 例如f1函数中的形参 38 第九讲 函数 递推 递归 5 在函数声明中出现的参数名 其作用范围只在本行的括号内 实际上 编译系统对函数声明中的变量名是忽略的 即使在调用函数时也没有为它们分配存 储单元

16、例如 intmax inta intb intmax intx inty cout x y endl cout a b endl 函数声明中出现a b 函数定义 形参是x y 合法 x y在函数体中有效 非法 a b在函数体中无效 编译时认为max函数体中的a和b未经定义 39 第九讲 函数 递推 递归 全局变量 程序的编译单位是源程序文件 cpp 一个源文件可以包含一个或若干个函数 在函数内定义的变量是局部变量 而在函数之外定义的变量是外部变量 称为全局变量 globalvariable 也称全程变量 全局变量的有效范围为从定义变量的位置开始到本源文件结束 如 40 第九讲 函数 递推 递归 intp 1 q 5 全局变量 floatf 定义函数f1 1 a inta 围 全局变量c1 c2的作用范围 inta 41 第九讲 函数 递推 递归 p q c1 c2都是全局变量 但它们的作用范围不同 在main函数和f2函数中可以使用全局变量p q c1 c2 但在函数f1中只能使用全局变量p q 而不能使用c1和c2 在一个函数中既可以使用本函数中的局部变量 又可以使用有效的全局变量