1.1.1算法概念(定稿)

1、织金育才学校织金育才学校人教人教A版版 必修必修3第一章第一章计算机与算法计算机与算法:在现代社会里，在现代社会里，计算机计算机已经成为人已经成为人们日常生活和工作不可缺少的工们日常生活和工作不可缺少的工具听音乐、看电影、玩游戏、画具听音乐、看电影、玩游戏、画卡通画、处理数据卡通画、处理数据计算机几乎可计算机几乎可以是一个全能的助手，你可以用它以是一个全能的助手，你可以用它来做你想做的任何事情那么，计来做你想做的任何事情那么，计算机是怎样工作呢？要想弄清楚这算机是怎样工作呢？要想弄清楚这个问题，就需要学习个问题，就需要学习算法算法什么是算法？什么是算法？ 答：分三步：答：分三步：第一步：打开冰

2、箱门第一步：打开冰箱门第二步：把大象装进冰箱第二步：把大象装进冰箱第三步：关上冰箱门第三步：关上冰箱门 要把大象装进冰箱，分几步？要把大象装进冰箱，分几步？问题情境：问题情境：一一知识探究知识探究加减消元法和代入消元法加减消元法和代入消元法 1. 1.在初中，对于解二元一次方程组你在初中，对于解二元一次方程组你学过哪些方法？学过哪些方法？ 2.2.用用加减消元加减消元法解二元一次方程组法解二元一次方程组 的详细求解步骤是什么？的详细求解步骤是什么？2121xyxy 2. 用用加减消元法加减消元法写出解二元一次方程组的写出解二元一次方程组的 详细求解过程详细求解过程. 2121xyxy 第三步第

3、三步:-2得得: 5y=3 第四步第四步: 解解得得:35y 第一步第一步: +2得得: 5x=1 第二步第二步: 解得解得:51x第五步第五步:得到方程组的解为得到方程组的解为5351yx 对于一般的二元一次方程组对于一般的二元一次方程组 （ ） 也可以按照上述步骤求解也可以按照上述步骤求解.111222a xb yca xb yc1 22 10aba b第五步第五步:得到方程组的解为得到方程组的解为1221122112212112babacacaybabacbcbx21121221)(cbcbxbaba第一步第一步: - 得得 2b1b第二步第二步: 解解得得:12212112babacb

4、cbx1 22 11 22 1()aba b ya ca c第三步第三步: - 得得 2a1a第四步第四步: 解解得得:12211221babacacay这五个步骤就构成了这五个步骤就构成了解二元一次方程组的解二元一次方程组的一个一个“算法算法”在这里我们可以利用得到的二元一次方程组在这里我们可以利用得到的二元一次方程组的的求解公式求解公式 12212112babacbcbx12211221babacacay 第一步：取第一步：取a1=1，b1=-2，c1=-1，a2=2，b2=1，c2=1 第二步：计算第二步：计算 与与 第三步：输出运算结果。第三步：输出运算结果。12212112babac

5、bcbx12211221babacacay给出另一个算法：给出另一个算法：（例如：（例如： ）2121xyxy 1.1.算法的概念算法的概念： 算法 （algorithm) 通常是指按照一定规则解决某一类问题的明确和有限的步骤。现在，算法通常可以编成计算机程序，让计算机执行并解决问题。二二建构数学建构数学 2. 2.算法的特征算法的特征普适性普适性有限性有限性不唯一性不唯一性明确性明确性可执行性可执行性例例1.(1)1.(1)设计一个算法判断设计一个算法判断7 7是否为质数是否为质数. .第一步第一步, 用用2除除7,得到余数得到余数1.因为余数不为因为余数不为0， 所以所以2不能整除不能整除

6、7.第二步第二步, 用用3除除7,得到余数得到余数1.因为余数不为因为余数不为0， 所以所以3不能整除不能整除7.第三步第三步, 用用4除除7,得到余数得到余数3.因为余数不为因为余数不为0， 所以所以4不能整除不能整除7.第四步第四步, 用用5除除7,得到余数得到余数2.因为余数不为因为余数不为0， 所以所以5不能整除不能整除7.第五步第五步, 用用6除除7,得到余数得到余数1.因为余数不为因为余数不为0， 所以所以6不能整除不能整除7.三三数学应用数学应用因此，因此，7是质数是质数例例1(1)(1)设计一个算法判断设计一个算法判断 7 7 是否为质是否为质数数. .第一步第一步, 用用2除

7、除 7 ,得到余数得到余数1.因为余数不为因为余数不为0， 所以所以2不能整除不能整除7.第二步第二步, 用用3除除 7 , 得到余数得到余数 1 .因为余数不为因为余数不为0， 所以所以3不能整除不能整除7.第三步第三步, 用用4除除 7 ,得到余数得到余数 3 .因为余数不为因为余数不为0， 所以所以4不能整除不能整除7.第四步第四步, 用用5除除 7 ,得到余数得到余数 2 .因为余数因为余数 不不 为为0， 所以所以 5 不能整除不能整除7.第五步第五步, 用用6除除7,得到余数得到余数1.因为余数不为因为余数不为0， 所以所以6不能整除不能整除7.因此，因此，7是质数是质数.三三数学

8、应用数学应用35352353350535353535 因此，因此，35不是质数不是质数.35(2) 设计一个算法判断设计一个算法判断20112011是否为质数是否为质数. .第一步第一步, 用用2除除7,得到余数得到余数1.因为余数不为因为余数不为0， 所以所以2不能整除不能整除7.第二步第二步, 用用3除除7,得到余数得到余数1.因为余数不为因为余数不为0， 所以所以3不能整除不能整除7.第三步第三步, 用用4除除7,得到余数得到余数3.因为余数不为因为余数不为0， 所以所以4不能整除不能整除7.第四步第四步, 用用5除除7,得到余数得到余数2.因为余数不为因为余数不为0， 所以所以5不能整

9、除不能整除7.第五步第五步, 用用6除除7,得到余数得到余数1.因为余数不为因为余数不为0， 所以所以6不能整除不能整除7.因此，因此，7是质数是质数 ，则，则n n不是质数结束算法；不是质数结束算法；（1 1）用）用 表示表示2 2n-1n-1中的任意一个整数，中的任意一个整数， 若若r0r0，（3 3）这个操作一直进行到）这个操作一直进行到i i取取n-1n-1为止为止. .判断最终的判断最终的in-1in-1是否成立？是否成立？（2 2）用）用i i除除 n n ，得到余数得到余数 . . 若若r=0r=0 将将 用用 代替，代替，再执行同样的操作；再执行同样的操作； iii+1并且从并

10、且从2 2开始取数；开始取数；r 如何写出如何写出“判断整数判断整数n n(n2)(n2)是是否为质数否为质数”的算法？的算法？（1 1）用）用i i表示表示2 2n-1n-1中的任意一个整数，并从中的任意一个整数，并从2 2开始取数；开始取数；（3 3）这个操作一直进行到）这个操作一直进行到i i取取n-1n-1为止为止. .（2 2）用用i i除除n n，得到余数，得到余数r.r.若若r=0r=0则则n n不是质数结束不是质数结束 算法算法; ;若若r r0,0,将将i i用用i+1i+1代替，再执行同样的操作，代替，再执行同样的操作，探究探究：如何写出如何写出“判断整数判断整数n n(n

11、2)(n2)是否是否为质数为质数”的算法？的算法？第一步，令第一步，令i=2i=2； 第二步，用第二步，用i i除除n n，得到余数，得到余数r r； 若若r0r0，将，将i i用用i+1i+1替代；替代； 第三步，若第三步，若r=0r=0，则，则n n不是质数，结束算法；不是质数，结束算法； 第四步，判断第四步，判断“i“in-1”是否成立？若是，则是否成立？若是，则n n 是质数，结束算法；否则，返回第三步是质数，结束算法；否则，返回第三步. . 第一步第一步 给定大于给定大于2的整数的整数n第二步第二步 第三步第三步 第四步第四步 第五步第五步 问题情境：猜商品价格问题情境：猜商品价格第

12、一步 报5000;第二步 若正确，就结束, 若高了,则报4000. 若低了,则报6000;第三步 重复第二步的报数方法，直到得出正确 结果. 一苹果手机价格在一苹果手机价格在30007000元之间，问竞猜者元之间，问竞猜者采取什么策略才能在较短时间内猜出商品价格？采取什么策略才能在较短时间内猜出商品价格？猜中间值做法体现了猜中间值做法体现了二分法二分法思想思想二分法二分法 对于区间对于区间 a a, ,b b 上连续不断、上连续不断、f(a)f(b)f(a)f(b)00的的函数函数y=f(x)y=f(x), ,通过不断地把函数通过不断地把函数f(x)f(x)的的零零点点所在所在区间一分为二区间

13、一分为二，使区间的两个端点，使区间的两个端点逐步逐步，进而得到，进而得到零点或其近似值零点或其近似值的方法叫做的方法叫做二分法二分法. .例例2. .用二分法设计一个求方程用二分法设计一个求方程220 x 的的近似解近似解的算法的算法. .(0)x 第四步第四步, 若若f(a) f(m) 0,则含零点的区间为则含零点的区间为a,m；第二步第二步, 给定区间给定区间a,b,满足满足f(a) f(b)0第三步第三步, 取中间点取中间点2abm将新得到的含零点的区间仍然记为将新得到的含零点的区间仍然记为a,b.否则，含零点的区间为否则，含零点的区间为m, b.算法步骤：算法步骤：第一步第一步, 令令

14、 ,2( )2f xx第五步第五步, 返回第三步返回第三步 精确度精确度d.2( )2f xx第五步第五步,判断判断f(m)是否等于或者是否等于或者a,b的长的长度是否小于度是否小于d，若是，则，若是，则m是方程的近似解是方程的近似解;否否则，返回第三步则，返回第三步a ab b|a-b|a-b|1 12 21 11 11.51.50.50.51.251.251.51.50.250.251.3751.3751.51.50.1250.1251.3751.3751.437 51.437 50.062 50.062 51.406 251.406 251.437 51.437 50.031 250.0

15、31 251.406 251.406 251.421 8751.421 8750.015 6250.015 6251.414 6251.414 6251.421 8751.421 8750.007 812 50.007 812 51.414 062 51.414 062 51.417 968 751.417 968 75 0.003 906 250.003 906 25当当d d=0.005=0.005时时，按照以上算法，可得下面表和图，按照以上算法，可得下面表和图. .y=x2-2121.51.3751.25 于是，开区间于是，开区间（1.4140625,1.41796875）中中的实数都是

16、当精确度为的实数都是当精确度为0.005时的原方程的时的原方程的近近似解似解.四四 课堂检测课堂检测: 给出求给出求1+2+3+4+5+6的一个算法的一个算法.按照逐一相加的程序进行按照逐一相加的程序进行. .第一步第一步:计算计算1+2,得得3;第二步第二步:将第一步中的运算结果将第一步中的运算结果3与与3相加得相加得6;第三步第三步:将第二步中的运算结果将第二步中的运算结果6与与4相加得相加得10;第四步第四步:将第三步中的运算结果将第三步中的运算结果10与与5相加得相加得15;第五步第五步:将第四步中的运算结果将第四步中的运算结果15与与6相加得相加得21.运用下面公式直接计算运用下面公式直接计算. .(1)12342n nn第一步第一步, ,取取 n = =6; ;第二步第二步, ,计算计算 ; ;2)1( nn第三步第三步, ,输出计算结果输出计算结果. .用循环方法求和用循环方法求和. .第一步第一步:使使S=1.第二步第二步:使使i=2.第三步第三步:使使S=S+i.第四步第四步:使使i=i+1.第五步：如果第五步：如果i7，则返回第三步，否则输出，则返回第三步，否则输