1、第4单元 计算与问题解决4.l算法及其特征1、算法的重要特征有穷性。算法必须能在执行有限个步骤之后终止。确切性。算法中的每一次运算都有明确的定义，具有无二义性，并且可以通过计算得到唯一的结果。输人项。一个算法有0个或多个输人，以刻画运算对象的初始情况，所谓0个输人是指算法本身给出了初始条件。输出项。算法一定要有输出。任何算法都不能“无功而返”可行性。算法中执行的任何计算都可以在有限时间内完成(也称为有效性)。算法中的运算都必须是可以实现的。从某种意义上说，算法也是一种数学模型。一般而言，问题求解的第一步是数学建模。用数学语言描述实际现象，将现实世界的问题抽象成数学模型，就可能发现问题的本质并判
2、定其能否求解，继而找到求解该问题的方法和算法。2、枚举我们常利用计算机运算速度快、精确度高的特点解决实际问题。在设计算法时，最简单的方法就是“直译”我们的思维过程。有一种算法是把所有可能的答案一一列举，合适就保留，不合适就丢弃。这种方法称作“枚举”或“穷举”4.2 数值计算1、numpy模块简介numpy是一个科学计算包，其中包含很多数学函数，如三角函数、矩阵计算方法等。通过该模块中的arange函数可以创建一个等差数列。如在02之间每隔0.01取个值，则可以用arange(0,2* numpy.pi,0.01)来表示，其中numpy.pi表示。下列代码可以产生sin(x)的若干个关键点2、m
3、atplotlib模块简介matplotlib模块是Python中最出色的绘图库，功能很完善。调用 matplotlib.pyplot时，坐标系可以根据数值范围自动生成。matplotlib的绘图原理很简单，利用plot画线函数就可以在直角平面 内轻松地将(x, y)坐标点对连接成平滑曲线。例如:在上述代码的适当位置增加下列语句，就可以将刚才生成的关键点连接起来。参考上述代码，让我们一起来完善以下Python程序，尝试绘出“sin(x)”“sin(-x)”和“sin(2x)/2”的图像。斐波那契在计算之书中提出了一个有趣的兔子问题:假设一对兔子每个月可以生一对小兔子，一对兔子出生后第2个月就开
4、始生 小兔子。则一对兔子一年内能繁殖成多少对? 10年呢?第1个月和第2个月的兔子对数之和为第3个月的兔子对数，第2个月和第3个月的兔子对数之和为第4个月的兔子对数.，每个月的兔子对数是前两个月的兔子对数之和，又同时作为下一个月兔子对数的加数。这种重复反馈的过程称为迭代。迭代法也称辗转法，是用计算机解决问题的一种基本方法。迭代通常是为了接近并到达所需的目标或结果。每一次对过程的重复被称为一次“迭代”，而每一次迭代得到的结果会被用来作为下一次迭代的初始值。由于在迭代系列中的每个月份兔子对数只跟前两个月有关，因此在编写程序时，只需两个变量f1和f2分别记录上上月和上月的数据。“f1,f2=f2,f
5、1+f2”中右边的值全是这个式子计算以前的初始值，可折为下面代码利用迭代算法解决问题，有三个关键步骤: (1)确定迭代变量, 如上例中的的f1、f2; (2) 建立迭代关系式；(3)对迭代过程进行控制，这是编写迭代程序必须考虑的问题，不能让迭代过程无休止地重复执行下去。现代自然科学和工程电子技术的研究过程中，都离不开大规模的数学计算问题。例如:数学类课程中的线性方程求解、微分方程求解、概率统计等，实用性和实验性技术应用中的模拟核试验、油田开发、飞机设计等。4.3 非数值计算1、分治策略分治的设计思想，是将一个难以直接解决的大问题，分割成一些较小的同类问题，各个击破，最终达到解决问题的目的。二分
6、查找实际上就是分治策略的一种典型运用。2、二分查找.二分查找又叫折半查找，该方法主要将数列有序排列，采用跳跃式的方式查找数据。以递增数列为例，先以中点位置的元素作为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。每一次比较后都可以将查找区间缩小一半。二分查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。在一个有n个元素的有序序列中，利用二分查找大约需要次。但是，二分法查找的前提条件是被查找的数据必须是有序的。例程：假设一本字典大约1000页，目标信息在第328页。翻页过程，看谁翻的次数最少。在翻页过程中借助两个书签，划定目标所属范围，然后翻到
7、两个书签的中间位置。每次目标区域都更新为原来的“二分之一”，当数据范围缩小到只有1个数的时候肯定能得到问题的解。1000以内的页码，最多翻10次肯定能找到解。2、递归递归是计算科学领域中一种重要的计算思维模式。它既是一种抽象表达的手段，也是一种问题求解的重要方法。直接或间接地调用自身的方法称为递归。可以将递归简单类比为具有自相似性重复的事物。图4.3.3所示就是递归的一种形象表示。在数学与计算机领域中，递归函数是指用函数自身来定义该函数的方法。如著名的斐波那契数列“1，1, 2，3, 5，8，13, .”，可以递归定义为递推关系是递归的重要组成，而边界条件是递归的另一要素，它保证递归能在有限次
8、的计算后得出结果，而不会产生无限循环的情况。面对一个大规模复杂问题的求解，递归的基本思想是把规模较大的 问题层层转化为规模较小的同类问题求解。对递归而言，递推与回归, 二者缺一不可。结合分治策略，递归也可用“分”“治”“合”三个字 概括。(1)分:将原问题分解成k个子问题。(2)治:对这k个子问题分别求解。如果子问题的规模仍然不够小，则将其再分解为k个子问题，如此进行下去，直到问题足够小时，就很容易求出子问题的解。(3)合:将求出的小规模问题的解合并为一个更大规模问题的解自下而上涿步求出原问题的解，移动3个木盘的方法是:根据木盘叠放规则，要使A杆上最大的木盘(记为x)移动到C杆上(子问题1，如
9、图4.3.2中的第4步)，必须先把 x上方的所有木盘移动到B杆上(子问题2,如图4.3.2中的前3步)，然后再将B杆上所有的木盘移动到C杆上(子问题3,如图4.3.2中的后3步)。3个木盘的移动问题成功解决了，就可以解决更多木盘的移动问题了。将n个木盘从A杆移动到C杆，需要借助中间的B杆。只要超过一个木盘，在移动过程中，总会存在起始杆、过渡杆及目标杆的问题。因此，定义函数时，用到了4个参数: hanoi(n,s,m,t), n表示需要移动的盘子数量，s表示盘子的起始杆，m表示中间过渡杆，t表示目标杆，如图4.3.4所示。用递归求斐波那契数列将一个难以直接解决的大问题，分割成一些规模较小的同类问
10、题，以便各个击破，分而治之，此为分治。分治与递归就像一对孪生兄弟，经常同时应用在算法设计中，并由此产生了许多高效的算法。4.4综合问题的解决在解决一个综合问题时，我们通常先考虑总体，后考虑细节；先面向整体，再细化局部。面对软件开发这类综合问题时，需要立足对象间的相互联系，强调便捷的人机交互模式，尽量向需求靠拢。1、pygame模块pygame是一个专门用来开发游戏的模块，可以包含图像、声音等。pygame相关内容如表4.4.1所示。pygame是专为游戏设计的，自带了一个监听类循环，不断检查用户的操作，比如用户按键、移动鼠标或者关闭窗口等。这个循环会在程序运行运行期间持续工作。其代码框架如下需求分析之后、程序设计之前，需要对系统进行总体设计和详细设计。总体设计就是在需求分析的基础上对模型细化、分解任务，明确程序由哪些模块组成。概括地说，就是系统应该如何实现。详细设计主要指界面设计、过程设计等。
