信息学奥赛课课通(c++)第6单元第5课函数的递归调用.ppt

函数的递归调用 长沙市一中岳麓中学信息学奥赛培训 阅读程序 分析结果 includeusingnamespacestd voidp intn if n 0 p n 1 for inti 0 i n i cout n cout endl intmain p 5 return0 答案 122333444455555 递归函数的局部变量 递归函数通常带有一些局部变量 如上例中的n 只有当整个函数体执行完毕 这些局部变量才失去意义 每递归调用一次 就必须生成一组 新 的局部变量 虽然这些新的局部变量与原来的局部变量具有相同的名字 但其分配的存储空间不同 其值也完全无关 使用递归必须符合的条件 1 可以把这个问题转化成一个新问题 而新问题的解法和原问题的解法完全相同 只是问题规模变小了 参数不同 2 必须要有一个明确的递归结束条件 递归边界 例1 求阶乘 jc 1s 64MB 问题分析 jc n 1 n 0或n 1 jc n n jc n 1 n 1 longlongjc intn if n 0 n 1 return1 returnjc n 1 n 思考 最后一行可否写成 elsereturnjc n 1 n 例2 求最大公约数 gcd 1s 64MB 问题分析 先使m n 根据欧几定理 发现 m n 的最大公约数与 n m n 的最大公约数是一样的 但是数据规模变小了 所以 最大公约数问题的递归公式为 gcd m n m n 0 gcd n m n n 0 intgcd intm intn if n 0 returnm elsereturngcd n m n 例3 分解质因子 zyz 1s 64MB 问题描述 输入一个正整数n 用递归方法从小到大输出它的所有质因子 输入格式 一行一个正整数n 2 n 10000 输出格式 一行若干个正整数 两数之间用一个空格隔开 从小到大输出 输入样例 18输出样例 233 递归公式 n 1返回输出pzyz n p n p 0n 1zyz n p p n p 0zyz n p 1 例4 抽奖 lottery2 1s 64MB 公司举办年会 为了活跃气氛 设置了摇奖环节 参加聚会的每位员工都有一张带有号码的抽奖券 现在 主持人从小到大依次公布n个不同的获奖号码 小谢看着自己抽奖券上的号码win 无比紧张 请编写一个程序 如果小谢获奖了 请输出他中奖的是第几个号码 如果没有中奖 请输出0 输入格式 第一行1个正整数n 表示有n个获奖号码 2 n 100 第二行包含n个正整数 之间用一个空格隔开 表示依次公布的n个获奖号码 第三行1个正整数win 表示小谢抽奖券上的号码 1 获奖号码 win 10000 输出格式 一行一个整数 如果小谢中奖了 请输出中的是第几个号码 如果没有中奖 请输出0 思考1 走楼梯 stairs 1s 64MB 问题描述 已知一个楼梯有n级 小谢同学从下往上走 一步可以走一级 也可以走两级 问 他走到第n级楼梯有多少种走法 要求用递归函数实现 输入格式 一行 一个正整数n 1 n 40 输出格式 一行 一个整数 表示走到第n级有多少种走法 输入样例 9输出样例 10 思考2 角谷猜想 问题描述 角谷猜想是指对于每一个正整数 如果它是奇数 则对它乘3再加1 如果它是偶数 则对它除以2 如此循环 最终都能够得到1 也就是说 给定正整数n 要进行如下操作 1 若n为1 操作结束 2 若n为偶数 则n变成n 2 3 若n为大于1的奇数 则n变成n 3 1 请编程验证此猜想 输入格式 1行 一个正整数n 1 n 20000 输出格式 若干行 每行表示一个操作 具体格式参见输出样例 样例输入 22样例输出 22 2 1111 3 1 3434 2 1717 3 1 5252 2 2626 2 1313 3 1 4040 2 2020 2 1010 2 55 3 1 1616 2 88 2 44 2 22 2 1 思考3 数的计算 count 1s 256MB 问题描述 输入一个自然数n 然后对此自然数按照如下方法处理 1 不做任何处理 2 在它的左边加上一个自然数 但该自然数不能超过原数的一半 3 加上数后继续按此规则进行处理 直到不能再加自然数为止 请找出以上操作能得到的数的个数 例如 n 6时 满足条件的数有6个 分别是6 16 26