4.3 《非数值计算》第二课时

4.3 非数值计算 —— 兔子数列 课 前 复 习 1.以下程序的执行结果为： 知识点检测 函 数 主程序 先执行主程序 只有调用函数的时候才能执行函数部分 2 教 学 目 标 通过求解斐波那契数列，体验递归算法，并结合具体问题开展编程实践。 理解迭代与递归的异同。 3 兔 子 数 列 def fib(n): f2 = f1 = 1 for i in range(3, n+1): f1, f2 = f2, f1+f2 return f2 n = int(input('输入需要计算的月份数：')) print('兔子总对数为：', fib(n)) input("运行完毕，请按回车键退出...") Fibonacci数列 ：1，1，2，3，5，8，13，21，34…… 迭 代 法 递归法 4 一 递归算法 直接或间接地调用自身的方法称为递归。可以将递归简单类比为具有自相似性重复的事物。 递归的基本思想是把规模较大的问题层层转化为规模较小的同类问题求解。可用“分”，“治”，“合”三个字概括 递归的基本思想 5 一 递归算法 递推关系 递归的条件 边界条件 + 从第三项起，每一项都是紧挨着的前两项的和,即 fib[i] = fib[i-1] + fib[i-2]， Fibonacci数列 ：1，1，2，3，5，8，13，21，34…… 递归关系： 边界条件： fib(n) = fib(n-1)+ fib(n-2) (n>2) fib(n) = 1 (n=1 或者 n=2） 6 课 堂 活 动 def f(n): if n == 1 ① n == 2: return 1 else: return ② n=int(input("输入要求的n的值")) print("第", n, "个月的兔子数为", ③) 使用递归法求第n个月的兔子数 7 一 递归算法 def f(n): if n == 1 or n == 2: return 1 else: return f(n-1)+f(n-2) n=int(input("输入要求的n的值")) print("第", n, "个月的兔子数为", f(n)) n=4 f(4) f(3) f(2) f(2) f(1) 1 1 1 2 3 8 二 迭代与递归 迭代：重复反馈过程直到达到结果 递归：调用函数自己 9 课 堂 小 练 求阶层 分别用迭代和递归两种方法求n! (n!=1*2*3……n) def f(n): if n==0 ① n==1: return 1 else: return ② n=int(input("请输入n：")) print("n的阶层为：",③) def fac(n): s=1 for i in range(2, ①): s=s*i ② abs=int(input('请输入阶乘数n：')) print("n的阶层为：",③) 10 课 堂 小 结 11 THE END $$