算法的概念[下学期]

课件47张PPT。算法的概念(一)翠园中学:王光宁2005 .7.3问3、指出在家中烧开水的过程分几步？问1、要把水果装入冰箱分几步？第三步 输出方程的根或无解的信息问2、如何求一元二次方程解：第一步 计算第二步 如果则方程无解顺序结构循环结构选择结构一、复习引入二、课本:引入 例题 与练习引入. 猜数:一商品价350元,猜者在0～800元猜,问竞猜者最多报几次、才能猜中商品价？第一步 报400;第二步 对了,就结束.否则执第三步;第四步 重复第二步,第三步的报数方法,
直到得出正确结果;第三步 高了,就报600,否则就报200;注重通法 解决一类问题 顺序? 选择? 循环? 结构例1、写出求1+2+3+4+5的一个算法。算法1：S1：计算1+2得到3；S2：将第一步中的运算结果3与3相加得到6；S3：将第二步中的运算结果6与4相加得到10；S4：将第三步中的运算结果10与5相加得到15；算法2:S1：取n=5；S2：计算S3：输出运算结果。同一问题的解决算法一般是不唯一的解：第一步，②-①×2得3y=-3；③第二步，解③得y=-1；第三步，将y=-1代入①，解得x=4机械的·统一的方法算法1算法2问:a x + b = 0 ? 顺序? 选择? 循环? 结构练2、求1×3×5×7的值，写出其算法。第一步，先求1×3，得到结果3；算法：第二步，将第一步所得结果3再乘以5，得到结果15；第三步，再将15乘以7，得到结果105；问:求1×3×5×7×┅×101? 顺序? 选择? 循环? 结构练3、已知直角坐标系的两点A(－1，0)，B(3，2)，写出
直线AB的方程的一个算法。解：算法：第一步：取x1=-2，y1=-1，x2=2，y2=3；第二步：计算第三步：写出问: x1= x2 ?第 ? 步 若 x1= x2 则写出 x=x1
否则执行下一步练4 、写出求1+2+3+ ┅ +100的一个算法。S1：取n=100；S2：计算S3：输出运算结果;S1 使P=1；S2 使i=2；S3 使P=P + i;S4 使i=i+1；S5 若i≤100，则返回到S3继续执行；
否则算法结束。算法1算法21 算法的概念 算法：为解决一个问题而采取的方法和步骤 做任何事情都有一定的步骤。算法过程: 要能一步一步执行，每一步执行的操作，
必须确切，不能含混不清楚，而且经过有限步后能得
出结果。具有下面几个特点：三、归纳与总结2 算法的特征 有穷性： 一个算法应包含有限的操作步骤而不能是
无限的。 确定性： 算法中每一个步骤应当是确定的，而不能应当
是含糊的、模棱两可的。有效性： 算法中每一个步骤应当能有效地执行，并得到
确定的结果。输 入: 有零个或多个输入。输 出: 有一个或多个输出。顺序结构选择结构循环结构当型直到型3 算法的结构学习与评价2、写出解不等式2x+2<4x-1的一个算法。1、写出求球的体积一个算法4、写出解不等式x2- x-1=0的一个算法。四、习题与提示5、写出过A(2,1)、B(1,0) 、C(2,-1)的三点的外接圆
的一个算法。6、二次函数顶点为过A(1,-41)、且过B(0,-3) 写出二次函数f(x)解析式的一个算法。10.猜数、一商品价1500元,猜者第一次报4000元,问竞猜者最多报几次、才能猜中商品价？算法的概念(二)翠园中学:王光宁2005 .7.3 例1． 两个大人和两个小孩一起渡河，渡口只有一条小
每次只能渡1 个大人或两个小孩，他们四人都会划 船，
但都不会游泳。试问他们怎样渡过河去？请写出一个渡
河方案。S1 两个小孩同船过河去；S2 一个小孩划船回来；S3 一个大人划船过河去；S4 对岸的小孩划船回来；S5 两个小孩同船渡过河去；S6 一个小孩划船回来；S7 余下的一个大人独自划船渡过河去；
对岸的小孩划船回来；S8 两个小孩再同时划船渡过河去。一、典型例题S2 若D=0 输出方程组无解或有无数组解， S3输出结果x1，x2、方程组无解或有无数组解。 例1、写出解不等式x2-2x-3<0的一个算法。解：第一步：x2-2x-3=0的两根是x1=3，x2=-1；第二步：由x2-2x-3<0可知不等式的解集为{x|-1< x <3}；1、方程 不等式与函数问:ax2+bx+c >0 （a > 0）?
一般的 ax2+bx+c >0 （a > 0）的算法如下：第一步：计算第二步：若△>0，求出方程两根（设x1>x2），则不等式解集为{x|x>x1或x 共48，要数脑袋整17，多少只小兔多少只鸡？S1 首先设x只小鸡，y只小兔。 S3 解方程组得：S4 指出小鸡10只，小兔7只。S2 再列方程组为：
2 设函数 输入为x，求y的值算法如下：S1：输入x；S2：判断x≥0？若x≥0，则执行S3，否则执行S4；S3: y=1；S4：y=-1；S5：输出S6：结束。练习例5 写出求1+2+3+4+5+6的一个算法。用P表示被加数，i表示加数。S1 使P=1；S2 使i=2；S3 使P=P + iS4 使i=i+1；S5 若i≤6，则返回到S3继续执行；
否则算法结束。2、求和与循环如果i>7，则输出x，否则，返回第3步，
重新执行3，4，5步。1、求1×3×5×7×9×11的值，写出其算法。S1 使P=1；S2 使i=3；S3 使P=P × i；S4 使i=i+2；S5 若i≤11，则返回到S3继续执行；否则算法结束。练习2、算法
S1 P=0
S2 i=1
S3 P=P + i
S4 i=i+1
S5 如果i不大于100，则返回执行S3，S4，S5；
如果大于100，则算法结束。1+2+3+4+5+……+100 算法表示：__________________练习 满足不等式1+2+3+……+n >100的最小的正整数n值。 3、算法：
S1 p=0
S2 i=0
S3 i=i+1
S4 p= p + i
S5 判断p是否大于100。若不是，
则返回从S3执行，若是，则执行S6
S6 输出i算法表示：练习S1 使P=1；S2 使i=3；S3 使P=P + iS4 使i=3×i；S5 若i≤3100，则返回到S3继续执行；
否则算法结束。练习例8、 任意给定一个大于1的正整数n，设计一个算法
　　　求出n的所有因数。解：S1 依次用2～n-1做除数去除n，看余数是否为0。若是，则是n的因数；
若不为0，则不是n的因数。S2 把1，n算在内；S3 将求出的所有的因数写出。3、整除与余数问:3的所有因数是____?问:4____? 6____?例9 求2000 — 2500年中的每一年是否闰年的一个算法.润年的条件：1、 能被4整除，但不能被100整除的年份；
2 、 能被100整除，又能被400整除的年份；设y为被检测的年份，则算法可表示如下：S1: 2000→yS2:若y不能被4整除，则输出y“不是闰年”，然后转到S6S3:若y能被4整除，不能被100整除，则输出y“是闰年”，
然后转到S6S4:若y能被100整除，又能被400整除，输出y“是闰年”
否则输出y“不是闰年”，然后转到S6S5:输出y“不是闰年”。S6:y+1→yS7:当y≤2500时, 返回S2继续执行，否则，结束。１、任意给定一个大于1的整数n，试设计一个程序或
步骤对n是否为质数做出判定。第一步：判断n是否等于2，若n=2，则n是质数；
　　　　　　　　　　　　若n>2，则执行第二步。第二步：依次从2至（n-1）检验是不是n的因数，
　　　　即整除n的数，若有这样的数，则n不是质数；　　　　　　
　　　　　　　　　　若没有这样的数，则n是质数。这是判断一个大于1的整数n是否为质数的最基本算法。练习2、写出求1至1000的正数中的3倍数的一个算法解：算法如下：S1 使i=1S2 i被3除，得余数rS3 如果r=0，则打印i，否则不打印S4 使i=i+1S5 若i≤1000,则返回到S2继续执行，
否则算法结束。练习例10、 设计一个求半径为一给定正实数的圆的面积的算法分析：根据圆面积公式s=πr2设计算法，取π=3.1416解：S1:将给定正实数r代入圆面积公式s=3.1416×r2；S2: 所得s的值就是所求圆的面积。说明：有了公式，算法设计很简单，就是代入公式。4、立几与解几—计算1、求两底半径为2和4，高为4的圆台的体积的算法练习第一步：取r1= 2，r2= 4，h= 4，π=3.141第二步：计算第三步：计算第四步：计算第五步：输出运算结果
第六步：输出结果。第一步：取x1= a1，y1= b1，x2= a2，y1= b2 ；第二步：若x1= x2；第三步：输出斜率不存在；第四步：若x1≠x2；第五步：计算例11、求过P(a1,b1)、Q(a2,b2)两点的直线斜率的算法：第二步：计算1、写出求过两点M(-2,-1)、N(2,3)的直线与坐标轴围
成面积的一个算法。解：算法：第一步：取x1=-2，y1=-1，x2=2，y2=3；第三步：在第二步结果中令x=0得到y的值m，
得直线与y轴交点(0,m)；第四步：在第二步结果中令y=0得到x的值n，
得直线与x轴交点(n,0)；第五步：计算 S =第六步：输出运算结果练习2、给出求点P(x0,y0)关于直线l:Ax+By+C=0的对称点
的一个算法。S1:过点P(x0,y0)关于直线l垂直的直线方程
l1:Bx-Ay=Bx0-Ay0；S2:直线l与直线l1的交点P(x1,y1)S3:写出P(2x1-x0,2y1-y0)练习例12、写出一个求整数a、b、c最大值的算法S1 max=a；S2 如果b>max，则max=b；S3 如果c>max，则max=c；S4 max就是a、b、c的最大值；5、比较大小1．算法
S1 m=a
S2 若bS3 若cS4 若dS5 输出m，则输出m表示 ( )
A．a，b，c，d中最大值
B．a，b，c，d中最小值
C．将a，b，c，d由小到大排序
D．将a，b，c，d由大到小排序 B练习2 有50个学生，要求将他们之中成绩在80分以上者打印出来。设Ni表示第i个学生学号； Gi表示第i个学生成绩；则算法可表示如下：S1: i=1;S2: 如果Gi≥80，则打印Ni和Gi，否则不打印;S3: i=i+1;S4:若i≤50, 返回S2，否则，结束。练习3、给定任意两个整数，按从小到大顺序排列。⑴输入两个整数A和B；否则(A≥B)，分别输出B和A，
且计算到此结束。⑵比较A和B的大小，若A 且计算到此结束，练习4、 写出一个求有限整数列中的最大值的算法。 S1 先假定序列中的第一个整数为“最大值”。S2 将序列中的下一个整数值与“最大值”比较，如果
它 大于此“最大值”，这时你就假定“最大值”是这个
整数。S3 如果序列中还有其他整数，重复S2。S4 在序列中一直到没有可比的数为止，这时假定的
“最大值”就是这个序列中的最大值。练习
例13用二分法设计一个求方程x2–2=0的近似根的算法。
使近似根与准确解的差的绝对值不超过0.005 第一步：令f(x)=x2–2。因为f(1)<0，f(2)>0，
所以设a=1，b=2;第二步：令m=(a+b)/2，判断若f(m)=0， m为所求；
若否，则继续判断f(a)·f(m)大于0还是小于0;第三步：若f(a)·f(m)>0，则令a=m；否则，令b=m;第四步：判断b-a<0.005是否成立;若是，则a、b之间的任意取值均为满足条件
的近似根；
若否，则返回第二步;6、二分法能否求解下列方程能否解出上述方程的近似解？（精确到0.1）（3）x3+3x-1=0（1）lgx=3-x（2）x2-2x-1=0思考题1.1 算法的含义 同步练习.doc同步练习 二、习题与提示