必修三算法的概念

1、,第一章,算法初步,1.1.1,算法的概念,一个人带着三只狼和三只羊过河，,只有一条船，同船可容纳一个人和两,只动物，没有人在的时候，如果狼的,数量不少于羊的数量狼就会吃羊,.,该人,如何将动物转移过河？,问题提出,?,1,?,p,?,?,?,?,2,?,t,5730,1.,用计算机解二元一次方程组,exe,2.,在上述解二元一次方程组的过程中，,计算机是按照一定的指令来工作的，其,中最基础的数学理论就是,算法,，本节课,我们就来学习,:,知识探究（一）：算法的概念,思考,1:,在初中，对于解二元一次方程组,你学过哪些方法？,加减消元法和代入消元法,思考,2,：用加减消元法解二元一次方程组,x

2、-2y=-1,2x+y=1,的具体步骤是什么？,思考,2:,用加减消元法解二元一次方程组,x,?,?,2,y,?,?,1,的具体步骤是什么？,?,?,2,x,?,y,?,1,?,x,?,2,y,?,?,1,?,?,2,x,?,y,?,1,第一步，,+,2,，得,5x=1 .,第二步，,x,?,1,5,第三步，,第四步，,第五步，,解，得,x,?,1,5,.,-,2,，得,5y,3,.,解，得,.,y,?,3,5,?,?,x,1,得到方程组的解为,?,?,?,5,?,?,y,?,3,?,5,.,思考,3:,参照上述思路，一般地，解方程,a,1,x,?,b,1,y,?,c,1,（,a,1,b,2,

3、?,a,2,b,1,?,0,）,组,的基,a,2,x,?,b,2,y,?,c,2,本步骤是什么？,第一步,，,b,2,-,b,1,，得,(,a,1,b,2,?,a,2,b,1,),x,?,b,2,c,1,?,b,1,c,2,.,b,2,c,1,?,b,1,c,2,x,?,第二步,，解,，得,.,a,1,b,2,?,a,2,b,1,a,第三步,，,a,-,2,，得,1,(,a,1,b,2,?,a,2,b,1,),y,?,a,1,c,2,?,a,2,c,1,.,a,1,c,2,?,a,2,c,1,y,?,第四步,，解,，得,.,a,1,b,2,?,a,2,b,1,b,2,c,1,?,b,1,c,2

4、,x,?,a,1,b,2,?,a,2,b,1,a,1,c,2,?,a,2,c,1,y,?,a,1,b,2,?,a,2,b,1,第五步,，得到方程组的解为,思考,4:,根据上述分析，用加减消元法解,二元一次方程组，可以分为五个步骤进,行，这五个步骤就构成了解二元一次方,程组的一个,“算法”,.,我们再根据这一算,法编制计算机程序，就可以让计算机来,解二元一次方程组,.,那么解二元一次方程,组的,算法,包括哪些内容？,思考,5:,一般地，算法是由,按照一定规则,解决某一类问题的基本步骤组成的,.,你认为：,(1),这些步骤的个数是有限的还是无限,的？,(2),每个步骤是否有明确的计算任务？,思考,

5、6:,有人对哥德巴赫猜想,“任何大于,4,的,偶数都能写成两个质数之和”,设计了如下操,作步骤：,第一步，检验,6=3+3,，,第二步，检验,8=3+5,，,第三步，检验,10=5+5,，,利用计算机无穷地进行下去！,请问：这是一个算法吗？,思考,7:,根据上述分析，你能归纳出,算法,的概念吗？,在数学中，按照一定规则解决某一类问,题的明确和有限的步骤,称为算法,.,一个人带着三只狼和三只羊过河，,只有一条船，同船可容纳一个人和两,只动物，没有人在的时候，如果狼的,数量不少于羊的数量狼就会吃羊,.,该人,如何将动物转移过河？,分析：任何动物同船不用考虑动物的争斗但需考虑,承载的数量，还应考虑到

6、两岸的动物都得保证狼的,数量要小于羚羊的数量，故在算法的构造过程中尽,可能保证船里面有狼，这样才能使得两岸的羚羊数,量占到优势,.,解：具体算法如下：,算法步骤：,第一步：人带两只狼过河，并自己返回,.,第二步：人带一只狼过河，自己返回,.,第三步：人带两只羚羊过河，并带两只狼,返回,.,第四步：人带一只羊过河，自己返回,.,第五步：人带两只狼过河,.,知识探究（二）,:,算法的步骤设计,思考,1:,如果让计算机判断,7,是否为质数，如,何设计算法步骤？,第一步,，用,2,除,7,，得到余数,1,所以,2,不能整除,7.,第二步,，用,3,除,7,，得到余数,1,所以,3,不能整除,7.,第三

7、步,，用,4,除,7,，得到余数,3,所以,4,不能整除,7.,第四步,，用,5,除,7,，得到余数,2,所以,5,不能整除,7.,第五步,，用,6,除,7,，得到余数,1,所以,6,不能整除,7.,因此，,7,是质数,.,思考,2:,如果让计算机判断,35,是否为质数，如,何设计算法步骤？,第一步,，用,2,除,35,，得到余数,1,所以,2,不能整除,35.,，用,，用,，用,3,除,35,，得到余数,4,除,35,，得到余数,5,除,35,，得到余数,因此，,2,所以,3,不能整除,35.,3,所以,4,不能整除,35.,0,所以,5,能整除,35.,不是质数,.,第二步,第三步,第四步

8、,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,个,步骤，这些步骤基本是重复操作，我们可以,按下面的思路改进这个算法，减少算法的步,骤,.,

9、（,1,）用,i,表示,2,88,中的任意一个整数，并从,2,开始取数；,（,2,）用,i,除,89,，得到余数,r.,若,r=0,，则,89,不,是质数；若r0，将,i,用,i+1,替代，再执行同,样的操作；,（,3,）这个操作一直进行到,i,取,88,为止,.,你能按照这个思路，设计一个“判断,89,是否,为质数”的算法步骤吗？,算法设计,:,第一步，,令,i=2,；,用,i,除,89,，得到余数,r,；,若,r=0,，则,89,不是质数，结束算,法；若r0，将,i,用,i+1,替代；,判断“,i,88”是否成立？若是，,则,89,是质数，结束算法；否则，,返回第二步,.,第二步，,第三步

10、，,第四步，,思考,5:,一般地，判断一个大于,2,的整数是否,为质数的算法步骤如何设计？,第一步,，给定一个大于,2,的整数,n,；,，用,，判断“r=0”是否成立,令,i=2,；,i,除,n,，得到余数,r,；,.,若是，则,n,不是质数，结束算法；否则，将,i,的值增加,1,，仍用,i,表示；,i(n-,1)”是否成立，若是，,则,n,是质数，结束算法；否则，返回,第三步,.,第二步，,第三步,第四步,第五步，判断“,理论迁移,例,设函数,f(x),的图象是一条连续,不断的曲线，写出用“二分法”求方程,的一个近似解的算法,.,f(x)=0,第一步，,取函数,f(x),，给定精确度,d.,

11、a+b,第三步，,取区间中点,.,m,2,第二步，,确定区间,a,，,b,，满足,f(,a,),f(b),0.,第四步，,若,f(,a,),f(m),0,则含零点的区间,为,a,m,否则，含零点的区间为,m,，,b.,将新得到的含零点的区间仍记为,a,b;,第五步，,判断,a,b,的长度是否小于,d,或,f(m),是否等于,0.,若是，则,m,是方程的近似解；,否则，返回第三步,.,对于方程,x,?,2,?,0(,x,?,0),给定,d=0.005.,|a-b|,1,0.5,0.25,0.125,0.062 5,0.031 25,0.015 625,0.007 812 5,1.414 062 5,1.417 968 75,0.003 906 25,a,1,1,1.25,1.375,1.375,1.406 25,1.406 25,1.414 625,b,2,1.5,1.5,1.5,1.437 5,1.437 5,1.421 875,1.421 875,2,小结作业,算法是建立在解法基础上的操作过程，算法,不一定要有运算结果，问题答案可以由计算机解,决设计一个解决某类问题的算法的核心内容是,设计算法的步骤，它没有一个固定