资源简介

(共21张PPT)
4.3非数值计算
学习目标
了解算法设计的分治思想，并运用二分查找解决实际问题
体验递归算法，并结合具体问题开展编程实践
运用合适的算法形成解决问题的方案
1
2
3
运行利用python编写的“猜数字”游戏，计算机在1-100
中随机产生一个数，试试看你要猜多少次才能猜中。
课堂导入
程序源代码及执行结果截图：
如何猜得又快又准？
二分查找又叫折半查找，将数列有序排列，采用跳跃式查找数据；以递增数列为例，先以中点位置的元素作为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分；每一次比较后都可以将查找区间缩小一半。
二分查找法是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。在一个有n个元素的有序序列中，利用二分查找大约需要log2n次。
课堂活动1
如何实现？
请学生思考：利用自然语言如何描述？利用程序如何实现？
统计二分查找次数的源代码和程序运行截图：
尝试用二分法求 x3 - x2 + x - 1 = 0 在[-5,5]区间的解。
def f(x): #定义方程
return x**3-x**2+x-1
a=float(input("请输入解区间的左边界："))
b=float(input("请输入解区间的右边界："))
while abs(b-a)>1e-6:
x0=(a+b)/2
if f(a)*f(x0)<0:
b=x0
if f(b)*f(x0)<0:
a=x0
if f(x0)==0:
break
print("解为:",x0)
input("运行完毕，请按回车键退出...")
练习1
二分法：对于在区间[a,b]上连续不断，且满足f(a)f(b)<0的函数y=f(x)，通过不断地把函数f(x)的零点所在的区间二等分，使区间的两个端点逐步逼近零点，进而得到零点近似值的方法叫做二分法。
程序源代码和运行界面截图：
1. 凡治众如治寡，分数是也。（摘自孙子兵法）
2. 查找的基本算法有：顺序查找、二分查找，分块查找、哈希查找等。
拓展知识
3. 当while循环中执行break语句时，循环会马上终止。
4. python中的sort( )可以用于数据排序。
例如，以下语句：
x=[4,6,2,1,5,9]
x.sort( )
可以将列表x按从小到大的顺序排列。
“汉诺塔”游戏源于一个古老的印度传说。如下图所示，在木板上有A、B、C三根杆，A杆上有若干木盘，规定每次移动一个木盘。且小的木盘只能叠在大的木盘上面。请设计算法，用尽可能少的次数把所有的木盘从A杆全部移到C杆上。
课堂活动2
直接或间接地调用自身的方法称为递归。可以将递归简单类比为具有自相似性重复的事物。
递归是计算科学领域中一种重要的计算思维模式。它既是一种抽象表达的手段，也是一种问题求解的重要方法。
递归
递归函数是只用函数自身来定义该函数的方法。如斐波那契数列“1,1,2,3,5,8,13……”,可以递归定义为：
F(n)=
1(n=1或n=2)
F(n-1)+F(n-2)(n>2)
递归函数
递归的基本思想
递归的基本思想是把规模较大的问题层层转化为规模较小的同类问题求解。对递归而言，递推与回归，二者缺一不可。
递归可用“分”，“治”，“合”三个字概括
1）分：将原有问题分解成K个子问题。
2）治：对这K个子问题分别求解。如果子问题的规模仍然不够小，则将其再分解为K个子问题，如此进 行下去，直到问题足够小时，就很容易求出子问题的解。
3）合：将求出的小规模问题的解合并为一个更大规模问题的解，自下而上逐步求出原问题的解。
汉诺塔游戏源代码和运行界面截图：
汉诺塔
hanno(n-1,s,t,m) #将前n-1个盘子从s移动到m上
print(s,'-->',t) #将最底下的最后一个盘子从s移动到t上
hanno(n-1,m,s,t) #将m上的n-1个盘子移动到t上
要完成最后一步，那么最后一步的前一步要做什么。
汉诺塔-程序
1. 理解递归思想。
2. 理解递归算法。
3. 理解二分查找思想，运用二分算法解决实际问题。
课堂小结
结合4.2的知识，计算“汉诺塔”游戏移动的次数。
def f(n):
if n==0:
return 0
else:
return 2*f(n-1)+1
x=int(input("请输入塔的个数："))
print("需要移动",f(x),"次")
input("运行完毕，请按回车键退出...")
练习2
汉诺塔移动次数源代码和运行界面截图：
迭代程序可以转换成等价的递归程序。以上一节中计算斐波那契数列第N项的值为例，程序间的转换如表所示。
迭代与递归算法都需要重复执行某些代码，两者既有区另又有密切的联系。迭代是重复反馈过程的活动，其目的通常是逼迫所需目标或结果。递归是重复调用函数自身。递归满足终止条件的情况时逐层返回。迭代则通常使用计数器结束循环。
拓展知识

展开更多......

收起↑