资源简介

4.3 非数值计算
学习目标
1.运用合适的算法形成解决问题的方案
2.了解算法设计中的分治思想，并运用二分查找解决实际问题
3.体验递归的方法，并结合具体问题开展编程实践
教学重点
理解二分思想、递归思想，运用二分算法解决实际问题
教学难点
理解递归算法
第一课时 查找的策略
教学过程
教学内容
设计意图
猜数字比赛
运行Python编写的“猜数字”游戏，计算机在0～1000中随机产生一个数，试试看你要多少次才能猜中
玩猜数字游戏,激发学生兴趣
如何猜得又快又准
讲解二分查找思想：
二分查找又叫折半查找，将数列有序排列，采用跳跃式查找数据；以递增数列为例，先以中点位置的元素作为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分；每一次比较后都可以将查找区间缩小一半
了解二分思想
如何实现
1. 自然语言如何描述
2. 程序如何实现
从自然语言到程序设计语言过渡，降低难度
拓展
二分法解方程
已知x2-3x-18=0在[0，10]区间上有解，用二分法求出方程的解
令f(x)=x2-3x-18，针对有解区间(a,b)，取x0=(a+b)/2：
若f(a)*f(x0)<0，则f(x)在(a,x0)内有解
若f(x0)*f(b)<0,则f(x)在(x0,b)内有解
若f(x0)<较小数，如10-6，则x0为方程的解
深入理解二分，会运用二分思想解决实际问题
总结
1. 二分查找的优缺点
2. 其他查找方法
总结归纳
习题
尝试用二分法求解x3-x2+x-1=0在区域[-5，5]区间上的解
练习巩固
第二课时 神奇的递归
教学过程
教学内容
设计意图
玩汉诺塔游戏
从网上下载Flash版本汉诺塔游戏或在线汉诺塔游戏，让学生体验
游戏导入，激发兴趣
分析玩的过程
从1个盘子开始，到2个盘子，到3个盘子，画出移动过程
由简到难，逐步分析
程序实现
总结移动规律，绘出示意图，并根据示意图完善程序
通过示意图辅助理解
讲解递归思想
讲解递归思想
递归是重复调用函数自身，递是描述问题，归是解决问题。
理解递归思想
探究深入
如何计算移动次数
在以上程序的基础上进行修改，统计汉诺塔游戏的移动次数
相传在印度的婆罗门神庙内插着三根钻石棒，创世之时，神便在其中一根钻石棒上放了64枚纯金的圆盘。有一个叫婆罗门的门徒，不分日夜地将64枚金盘移到另一根钻石棒上，移动的过程中一次只能移动一个金盘，且大盘不能放在小盘上。神说等到婆罗门完成这项工作，世界将在一声霹雳中毁灭……
次数：18446744073709551615。婆罗门以1秒移动1次的速度，不眠不休要花5849万万年
加深对递归的理解
总结
生活中的递归
从前有座山，山上有座庙……
有5个人坐在一起，问第五个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第三个人，又说比第2人大两岁。问第2个人，说比第一个人大两岁。最后问第一个人，他说是10岁。请问第五个人多大？
了解生活中的递归
习题
尝试用递归求Fibonacci数列第N个数
练习巩固

展开更多......

收起↑