必修三算法的概念

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第一章 算法初步,1.1.1,算法的概念,一个人带着三只狼和三只羊过河，只有一条船，同船可容纳一个人和两只动物，没有人在的时候，如果狼的数量不少于羊的数量狼就会吃羊,.,该人如何将动物转移过河？,问题提出,1.,用计算机解二元一次方程组,exe,2.,在上述解二元一次方程组的过程中，计算机是按照一定的指令来工作的，其中最基础的数学理论就是,算法,，本节课我们就来学习,:,算法的概念,知识探究（一）：算法的概念,思考,1:,在初中，对于解二元一次方程组你学过哪些方法？,思考,2,：用加减消元法解二元一次方程组,x-2y=-1 ,2x+y=1 ,的具体步骤是什么？,加减消元法和代入消元法,思考,2:,用加减消元法解二元一次方程组,的具体步骤是什么？,+,2,，得,5x=1 . ,解，得,.,-,2,，得,5y,3,.,解，得,.,第一步，,第二步，,第三步，,第四步，,第五步，,得到方程组的解为,.,思考,3:,参照上述思路，一般地，解方程,组 的基,本步骤是什么？,第一步,，,-,，得,.,第二步,，解,，得,.,第三步,，,-,，得,.,第四步,，解,，得,.,第五步,，得到方程组的解为,思考,4:,根据上述分析，用加减消元法解二元一次方程组，可以分为五个步骤进行，这五个步骤就构成了解二元一次方程组的一个,“,算法,”,.,我们再根据这一算法编制计算机程序，就可以让计算机来解二元一次方程组,.,那么解二元一次方程组的,算法,包括哪些内容？,思考,5:,一般地，算法是由,按照一定规则解决某一类问题的基本步骤组成的,.,你认为：,(1),这些步骤的个数是有限的还是无限 的？,(2),每个步骤是否有明确的计算任务？,思考,6:,有人对哥德巴赫猜想,“,任何大于,4,的偶数都能写成两个质数之和,”,设计了如下操作步骤：,第一步，检验,6=3+3,，,第二步，检验,8=3+5,，,第三步，检验,10=5+5,，,利用计算机无穷地进行下去！,请问：这是一个算法吗？,思考,7:,根据上述分析，你能归纳出,算法,的概念吗？,在数学中，按照一定规则解决某一类问题的明确和有限的步骤,称为算法,.,一个人带着三只狼和三只羊过河，只有一条船，同船可容纳一个人和两只动物，没有人在的时候，如果狼的数量不少于羊的数量狼就会吃羊,.,该人如何将动物转移过河？,分析：任何动物同船不用考虑动物的争斗但需考虑承载的数量，还应考虑到两岸的动物都得保证狼的数量要小于羚羊的数量，故在算法的构造过程中尽可能保证船里面有狼，这样才能使得两岸的羚羊数量占到优势,.,解：具体算法如下：,算法步骤：,第一步：人带两只狼过河，并自己返回,.,第二步：人带一只狼过河，自己返回,.,第三步：人带两只羚羊过河，并带两只狼返回,.,第四步：人带一只羊过河，自己返回,.,第五步：人带两只狼过河,.,知识探究（二）,:,算法的步骤设计,思考,1:,如果让计算机判断,7,是否为质数，如何设计算法步骤？,第一步,，用,2,除,7,，得到余数,1,所以,2,不能整除,7.,第四步,，用,5,除,7,，得到余数,2,所以,5,不能整除,7.,第五步,，用,6,除,7,，得到余数,1,所以,6,不能整除,7.,第二步,，用,3,除,7,，得到余数,1,所以,3,不能整除,7.,第三步,，用,4,除,7,，得到余数,3,所以,4,不能整除,7.,因此，,7,是质数,.,思考,2:,如果让计算机判断,35,是否为质数，如何设计算法步骤？,第一步,，用,2,除,35,，得到余数,1,所以,2,不能整除,35.,第二步,，用,3,除,35,，得到余数,2,所以,3,不能整除,35.,第三步,，用,4,除,35,，得到余数,3,所以,4,不能整除,35.,第四步,，用,5,除,35,，得到余数,0,所以,5,能整除,35.,因此，,35,不是质数,.,思考,3:,整数,89,是否为质数？如果让计算机判断,89,是否为质数，按照上述算法需要设计多少个步骤？,第一步,，用,2,除,89,，得到余数,1,所以,2,不能整除,89.,第二步,，用,3,除,89,，得到余数,2,所以,3,不能整除,89.,第三步,，用,4,除,89,，得到余数,1,所以,4,不能整除,89., ,第八十七步,，用,88,除,89,，得到余数,1,所以,88,不能 整除,89.,因此，,89,是质数,.,思考,4:,用,2,88,逐一去除,89,求余数，需要,87,个步骤，这些步骤基本是重复操作，我们可以按下面的思路改进这个算法，减少算法的步骤,.,（,1,）用,i,表示,2,88,中的任意一个整数，并从,2,开始取数；,（,2,）用,i,除,89,，得到余数,r.,若,r=0,，则,89,不是质数；若,r0,，将,i,用,i+1,替代，再执行同样的操作；,（,3,）这个操作一直进行到,i,取,88,为止,.,你能按照这个思路，设计一个,“,判断,89,是否为质数,”,的算法步骤吗？,用,i,除,89,，得到余数,r,；,令,i=2,；,若,r=0,，则,89,不是质数，结束算法；若,r0,，将,i,用,i+1,替代；,判断,“,i,88,”,是否成立？若是，则,89,是质数，结束算法；否则，返回第二步,.,第一步，,第四步，,第三步，,第二步，,算法设计,:,思考,5:,一般地，判断一个大于,2,的整数是否为质数的算法步骤如何设计？,第一步,，给定一个大于,2,的整数,n,；,第二步，,令,i=2,；,第三步,，用,i,除,n,，得到余数,r,；,第四步,，判断,“,r=0,”,是否成立,.,若是，则,n,不是质数，结束算法；否则，将,i,的值增加,1,，仍用,i,表示；,第五步，判断,“,i(n-1),”,是否成立，若是，,则,n,是质数，结束算法；否则，返回 第三步,.,理论迁移,例 设函数,f(x,),的图象是一条连续不断的曲线，写出用,“,二分法,”,求方程,f(x,)=0,的一个近似解的算法,.,第一步，,取函数,f(x,),，给定精确度,d.,第二步，,确定区间,a,，,b,，满足,f(,a,),f(b,),0.,第五步，,判断,a,b,的长度是否小于,d,或,f(m,),是否等于,0.,若是，则,m,是方程的近似解；否则，返回第三步,.,第三步，,取区间中点,.,第四步，,若,f(,a,),f(m,),0,则含零点的区间 为,a,m,否则，含零点的区间为,m,，,b.,将新得到的含零点的区间仍记为,a,b,;,a,b,|a-b|,1,2,1,1,1.5,0.5,1.25,1.5,0.25,1.375,1.5,0.125,1.375,1.437 5,0.062 5,1.406 25,1.437 5,0.031 25,1.406 25,1.421 875,0.015 625,1.414 625,1.421 875,0.007 812 5,1.414 062 5,1.417 968 75,0.003 906 25,对于方程,给定,d=0.005.,小结作业,算法是建立在解法基础上的操作过程，算法不一定要有运算结果，问题答案可以由计算机解决设计一个解决某类问题的算法的核心内容是设计算法的步骤，它没有一个固定的模式，但有以下几个基本要求：,(1),符合运算规则，计算机能操作；,(2),每个步骤都有一个明确的计算任务,；,(4),步骤个数尽可能少,；,(5),每个步骤的语言描述要准确、简明,.,(3),对重复操作步骤作返回处理,；,1,、写出求,1,2,3,4,5,的一个算法,.,练习：,2,、设计一个算法，对任意,3,个整数,a,、,b,、,c,，求出其中的最大数。,