算法初步课件 1.1 算法的概念

1、x 为什么要学习算法为什么要学习算法? ? 计算机与算法: 在现代社会里，计算机已经成为人们日常 生活和工作不可缺少的工具听音乐、看 电影、玩游戏、画卡通画、处理数据计 算机几乎可以是一个全能的助手，你可以 用它来做你想做的任何事情那么，计算 机是怎样工作呢？要想弄清楚这个问题， 就需要学习算法 二元一次方程组二元一次方程组 12 12 yx yx 的求解过程的求解过程. 归纳它的步骤归纳它的步骤: 第一步第一步: -2，得，得 5y=3 第三步第三步: 5 1 5 3 xy，得代入将 第二步第二步: 解解得得 y= 5 3 第二步第二步: 解解得得 y= 5 3 思考？ 0 1221 222

2、 111 baba cybxa cybxa 其中 一般的二元一次方程组 第二步：解第二步：解，得，得 1221 1221 baba caca y 第一步：第一步： - - ，得，得 1 a 2 a 12211221 )(cacaybaba 第三步：将第三步：将 代入代入，得，得 1221 1221 baba caca y 1221 2112 baba cbcb x 1、算法的概念：、算法的概念： 在数学中在数学中“算法算法”通常是指按照一定的规则来通常是指按照一定的规则来 解决的某一类问题的解决的某一类问题的明确和有限的步骤明确和有限的步骤，这些，这些 步骤必须是步骤必须是明确明确和和有效有效

3、的，而且能够在的，而且能够在有限步有限步 之内完成。之内完成。 3.算法的基本思想与特征算法的基本思想与特征: 2.算法的表示方法：算法的表示方法：自然语言、程序框图、程序自然语言、程序框图、程序 (1)解决某一类问题解决某一类问题 (2)在在有限步有限步之内完成之内完成 (3)每一步的明确性和有效性每一步的明确性和有效性 (4)每一步具有顺序性每一步具有顺序性 (一般性一般性) (有限性有限性) (确定与可行性确定与可行性) (顺序性顺序性) 一般书上归纳算法的基本性质有四条： a.有穷性； b. 唯一的初始动作； c.每个动作都有唯一的后继动作； d.动作序列终止时，表示问题得到解答 或没

4、有解答 练习练习 判断下列关于算法的说法是否确：判断下列关于算法的说法是否确： 1、求解某一类问题的算法是唯一的；、求解某一类问题的算法是唯一的； 2、算法必须在有限步操作之后停止：、算法必须在有限步操作之后停止： 3、算法的每一步必须是明确的，不能有歧、算法的每一步必须是明确的，不能有歧 义或模糊：义或模糊： 4、算法执行后一定产生确定的结果：、算法执行后一定产生确定的结果： 例题例题1 思考：任意给定一个大于思考：任意给定一个大于2的整数的整数n，试设计，试设计 一个算法对一个算法对n是否为质数做出判定是否为质数做出判定. . (2).设计一个算法，判断设计一个算法，判断35是否为质数？是

5、否为质数？ (1).设计一个算法，判断设计一个算法，判断7是否为质数？是否为质数？ 分析：1二分法求方程近似解是通过求 对应函数的近似零点得到的，所以首先 要建立函数，而且要有具体精确度要求， 因此第一步应该怎么做？ 2二分法分的是什么？ 3如何确定新区间的端点？ 4如何表达出反复二分区间的过程？ 例例2、用二分法设计一个求方程、用二分法设计一个求方程x2-2=0的近的近 似根的算法（精确度为似根的算法（精确度为0.005）. . 例例2、用二分法设计一个求方程、用二分法设计一个求方程x2-2=0的近的近 似根的算法（精确度为似根的算法（精确度为0.005）. . 第一步：令f(x)=x2-2

6、，给定精确度d. ,0f af b第二步：确定区间 a,b 满足； ; a+b 第三步：取区间中点m= 2 0, ,. f af m第四步：若，则含零点的区间为 a,m 否则为 m，b 将新得到的区间仍记为 a,b df m第五步：判断区间 a,b 的长度是否小于 或是否等于0； 若是，则m即为所求方程的近似解，不是，则返回第三步。 课堂练习课堂练习 1、任意给定一个正实数，设计一个算法求以这个数为半、任意给定一个正实数，设计一个算法求以这个数为半 径的圆的面积。径的圆的面积。 算法步骤： 第一步：输入任意一个正实数r。 第二步：计算以r为半径的圆的面积 。 2 sr 第三步：输出圆的面积s。 2、任意给定一个大于、任意给定一个大于1的正整数的正整数n，设计一个算法，设计一个算法 求出求出n的所有因数。的所有因数。 算法步骤： 第一步：依次以2（n-1）为除数去除n，判定余数是否 为0，若是，则n是因数；若不