第一章第一章 算法初步算法初步1.1 1.1 算法与程序框图算法与程序框图1.1.1 1.1.1 算法的概念算法的概念高中新课程数学必修高中新课程数学必修问题提出问题提出1.1.用计算机解二元一次方程组用计算机解二元一次方程组 .exe2.2.在上述解二元一次方程组的过程中，在上述解二元一次方程组的过程中，计算机是按照一定的指令来工作的，其计算机是按照一定的指令来工作的，其中最基础的数学理论就是中最基础的数学理论就是算法算法，本节课，本节课我们就来学习我们就来学习: : 知识探究（一）：算法的概念知识探究（一）：算法的概念思考思考1:1:在初中，对于解二元一次方程组在初中，对于解二元一次方程组你学过哪些方法？你学过哪些方法？ 思考2：用加减消元法解二元一次方程组 x-2y=-1 2x+y=1 的具体步骤是什么？加减消元法和代入消元法加减消元法和代入消元法思考思考2 2: :用加减消元法解二元一次方程组用加减消元法解二元一次方程组 的具体步骤是什么？的具体步骤是什么？ +2 2，得，得 5x=1 . 5x=1 . 解解，得，得 . . -2 2，得，得 5y5y3 3 . . 解解，得，得 . .第一步，第一步，第二步，第二步，第三步，第三步，第四步，第四步，第五步，第五步， 得到方程组的解为得到方程组的解为 . . 思考思考3:3:参照上述思路，一般地，解方程参照上述思路，一般地，解方程组组 的基的基本步骤是什么？本步骤是什么？第一步第一步， - - ，得，得 . . 第二步第二步，解，解 ，得，得 . . 第三步第三步， - - ，得，得 . . 第四步第四步，解，解 ，得，得 . . 第五步第五步，得到方程组的解为，得到方程组的解为 思考思考4:4:根据上述分析，用加减消元法解根据上述分析，用加减消元法解二元一次方程组，可以分为五个步骤进二元一次方程组，可以分为五个步骤进行，这五个步骤就构成了解二元一次方行，这五个步骤就构成了解二元一次方程组的一个程组的一个“算法算法”. .我们再根据这一算我们再根据这一算法编制计算机程序，就可以让计算机来法编制计算机程序，就可以让计算机来解二元一次方程组解二元一次方程组. .那么解二元一次方程那么解二元一次方程组的组的算法算法包括哪些内容？包括哪些内容？ 思考思考5:5:一般地，算法是由一般地，算法是由按照一定规则按照一定规则解决某一类问题的基本步骤组成的解决某一类问题的基本步骤组成的. .你认为：你认为：(1)(1)这些步骤的个数是有限的还是无限这些步骤的个数是有限的还是无限 的？的？(2)(2)每个步骤是否有明确的计算任务？每个步骤是否有明确的计算任务？思考思考6:6:有人对哥德巴赫猜想有人对哥德巴赫猜想“任何大于任何大于4 4的的偶数都能写成两个质数之和偶数都能写成两个质数之和”设计了如下操设计了如下操作步骤：作步骤：第一步，检验第一步，检验6=3+36=3+3，第二步，检验第二步，检验8=3+58=3+5，第三步，检验第三步，检验10=5+510=5+5， 利用计算机无穷地进行下去！利用计算机无穷地进行下去！请问：这是一个算法吗？请问：这是一个算法吗？思考思考7:7:根据上述分析，你能归纳出根据上述分析，你能归纳出算法算法的概念吗？的概念吗？ 在数学中，按照一定规则解决某一在数学中，按照一定规则解决某一类问题的明确和有限的步骤类问题的明确和有限的步骤称为算法称为算法. . 知识探究（二）知识探究（二）: :算法的步骤设计算法的步骤设计思考思考1:1:如果让计算机判断如果让计算机判断7 7是否为质数，如是否为质数，如何设计算法步骤？何设计算法步骤？ 第一步第一步，用，用2 2除除7 7，得到余数，得到余数1,1,所以所以2 2不能整除不能整除7.7.第四步第四步，用，用5 5除除7 7，得到余数，得到余数2,2,所以所以5 5不能整除不能整除7. 7. 第五步第五步，用，用6 6除除7 7，得到余数，得到余数1,1,所以所以6 6不能整除不能整除7.7. 第二步第二步，用，用3 3除除7 7，得到余数，得到余数1,1,所以所以3 3不能整除不能整除7.7.第三步第三步，用，用4 4除除7 7，得到余数，得到余数3,3,所以所以4 4不能整除不能整除7. 7. 因此，因此，7 7是质数是质数. .思考思考2:2:如果让计算机判断如果让计算机判断3535是否为质数，如是否为质数，如何设计算法步骤？何设计算法步骤？ 第一步第一步，用，用2 2除除3535，得到余数，得到余数1,1,所以所以2 2不能整除不能整除35.35.第二步第二步，用，用3 3除除3535，得到余数，得到余数2,2,所以所以3 3不能整除不能整除35.35.第三步第三步，用，用4 4除除3535，得到余数，得到余数3,3,所以所以4 4不能整除不能整除35. 35. 第四步第四步，用，用5 5除除3535，得到余数，得到余数0,0,所以所以5 5能整除能整除35.35.因此，因此，3535不是质数不是质数. .思考思考3:3:整数整数8989是否为质数？如果让计算是否为质数？如果让计算机判断机判断8989是否为质数，按照上述算法需是否为质数，按照上述算法需要设计多少个步骤？要设计多少个步骤？ 第一步第一步，用，用2 2除除8989，得到余数，得到余数1,1,所以所以2 2不能整除不能整除89.89.第二步第二步，用，用3 3除除8989，得到余数，得到余数2,2,所以所以3 3不能整除不能整除89.89.第三步第三步，用，用4 4除除8989，得到余数，得到余数1,1,所以所以4 4不能整除不能整除89.89. 第八十七步第八十七步，用，用8888除除8989，得到余数，得到余数1,1,所以所以8888不能不能 整除整除89.89.因此，因此，8989是质数是质数. .思考思考4:4:用用2 28888逐一去除逐一去除8989求余数，需要求余数，需要8787个个步骤，这些步骤基本是重复操作，我们可以步骤，这些步骤基本是重复操作，我们可以按下面的思路改进这个算法，减少算法的步按下面的思路改进这个算法，减少算法的步骤骤. .（1 1）用）用i i表示表示2 28888中的任意一个整数，并从中的任意一个整数，并从2 2开始取数；开始取数；（2 2）用）用i i除除8989，得到余数，得到余数r. r. 若若r=0r=0，则，则8989不不是质数；若是质数；若r0r0，将，将i i用用i+1i+1替代，再执行同替代，再执行同样的操作；样的操作； （3 3）这个操作一直进行到）这个操作一直进行到i i取取8888为止为止. .你能按照这个思路，设计一个你能按照这个思路，设计一个“判断判断8989是否是否为质数为质数”的算法步骤吗？的算法步骤吗？用用i i除除8989，得到余数，得到余数r r； 令令i=2i=2； 若若r=0r=0，则，则8989不是质数，结束算不是质数，结束算法；若法；若r0r0，将，将i i用用i+1i+1替代；替代； 判断判断“i i8888”是否成立？若是，是否成立？若是，则则8989是质数，结束算法；否则，是质数，结束算法；否则，返回第二步返回第二步. . 第一步，第一步， 第四步，第四步， 第三步，第三步， 第二步，第二步， 算法设计算法设计: :思考思考5:5:一般地，判断一个大于一般地，判断一个大于2 2的整数是否的整数是否为质数的算法步骤如何设计？为质数的算法步骤如何设计？ 第一步第一步，给定一个大于，给定一个大于2 2的整数的整数n n； 第二步第二步，令，令i=2i=2； 第三步第三步，用，用i i除除n n，得到余数，得到余数r r； 第四步第四步，判断，判断“r=0r=0”是否成立是否成立. .若是，则若是，则n n 不是质数，结束算法；否则，将不是质数，结束算法；否则，将i i 的值增加的值增加1 1，仍用，仍用i i表示；表示； 第五步第五步，判断，判断“i i(n-1)(n-1)”是否成立，若是，是否成立，若是， 则则n n是质数，结束算法；否则，返回是质数，结束算法；否则，返回 第三步第三步. . 理论迁移理论迁移 例例 设函数设函数f(xf(x) )的图象是一条连续的图象是一条连续不断的曲线，写出用不断的曲线，写出用“二分法二分法”求方程求方程 f(xf(x)=0)=0的一个近似解的算法的一个近似解的算法. . 第一步，第一步，取函数取函数f(xf(x) )，给定精确度，给定精确度d.d. 第二步，第二步，确定区间确定区间 a，bb，满足，满足f(f(a) )f(bf(b) )0. 0. 第五步，第五步，判断判断 a,b,b 的长度是否小于的长度是否小于d d或或f(mf(m) )是否等于是否等于0. 0. 若是，则若是，则m m是方程的近似解；是方程的近似解；否则，返回第三步否则，返回第三步. .第三步，第三步，取区间中点取区间中点 . .第四步，第四步，若若f(f(a) )f(mf(m) )0,0,则含零点的区间则含零点的区间 为为 a,m,m,否则，含零点的区间为否则，含零点的区间为mm，b.b. 将新得到的含零点的区间仍记为将新得到的含零点的区间仍记为 a,b,b;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.031 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 750.003 906 250.003 906 25对于方程对于方程 , ,给定给定d=0.005.d=0.005.小结作业小结作业 算法是建立在解法基础上的操作过程，算法算法是建立在解法基础上的操作过程，算法不一定要有运算结果，问题答案可以由计算机解决不一定要有运算结果，问题答案可以由计算机解决设计一个解决某类问题的算法的核心内容是设计设计一个解决某类问题的算法的核心内容是设计算法的步骤，它没有一个固定的模式，但有以下几算法的步骤，它没有一个固定的模式，但有以下几个基本要求：个基本要求： (1)(1)符合运算规则，计算机能操作；符合运算规则，计算机能操作；(2)(2)每个步骤都有一个明确的计算任务每个步骤都有一个明确的计算任务；(4)(4)步骤个数尽可能少步骤个数尽可能少；(5)(5)每个步骤的语言描述要准确、简明每个步骤的语言描述要准确、简明. .(3)(3)对对重复操作重复操作步骤作返回处理步骤作返回处理；作业作业: :P P5 5练习：练习：1 1，2.2.