人教版高中数学必修三第一章第1节 111 算法的概念课件.ppt

1、理论研究科学实验科学计算研究算法研究算法问题问题1请你回顾并写出解二元一次方程组的详请你回顾并写出解二元一次方程组的详细求解过程细求解过程.2121xyxy -2得得:5y=3 解解得得:35y +2得得:5x=1 解解得得:51x得到方程组的解为得到方程组的解为5351yx第一步第一步:第二步第二步:第三步第三步:第四步第四步:第五步第五步:01221222111 babacybxacybxa 第一步：a1-a2，得：12211221cacaybaba 第二步：解得 12211221babacacay ；第三步：将12211221babacacay 代入，得12212112babacbcbx

2、 .推推 广广 算法算法通常指可以用来解决的某一类问题的通常指可以用来解决的某一类问题的步步骤或程序骤或程序，这些步骤或程序必须是，这些步骤或程序必须是明确明确的和的和有效有效的，而且能够在的，而且能够在有限步有限步之内完成的。之内完成的。三、概念形成三、概念形成概念概念.算法（算法（algorithmalgorithm）一般来说，一般来说，“用算法解决问题用算法解决问题”可以利用可以利用计计算机算机帮助完成。帮助完成。例例1 1、设计一个算法判断、设计一个算法判断7 7是否为质数。是否为质数。第一步第一步：用：用2 2除除7 7，得到余数，得到余数1 1。因为余数不为。因为余数不为0 0，所

3、以，所以2 2不能整除不能整除7 7。第二步第二步：用：用3 3除除7 7，得到余数，得到余数1 1。因为余数不为。因为余数不为0 0，所以，所以3 3不能整不能整除除7 7。第三步第三步：用：用4 4除除7 7，得到余数，得到余数3 3。因为余数不为。因为余数不为0 0，所以，所以4 4不能整除不能整除7 7。第四步第四步：用：用5 5除除7 7，得到余数，得到余数2 2。因为余数不为。因为余数不为0 0，所以，所以5 5不能整除不能整除7 7。第五步第五步：用：用6 6除除7 7，得到余数，得到余数1 1。因为余数不为。因为余数不为0 0，所以，所以6 6不能整除不能整除7 7。质数：只能

4、被质数：只能被1和自身整除的大于和自身整除的大于1的整数叫质的整数叫质数。数。探究：探究：2,3,4,5,6是否为质数。是否为质数。综上：综上：7是质数是质数。变式：设计一个算法，判断变式：设计一个算法，判断3535是否为质数。是否为质数。第一步第一步：用：用2 2除除3535，得到余数，得到余数1 1。因为余数不为。因为余数不为0 0，所以所以2 2不能整除不能整除3535。第二步第二步：用：用3 3除除3535，得到余数，得到余数2 2。因为余数不为。因为余数不为0 0，所以所以3 3不能整除不能整除3535。第三步第三步：用：用4 4除除3535，得到余数，得到余数3 3。因为余数不为。

5、因为余数不为0 0，所以所以4 4不能整除不能整除7 7。第四步第四步：用：用5 5除除3535，得到余数，得到余数0 0。因为余数为。因为余数为0 0，所，所以以5 5能整除能整除3535。因此，因此，35不是质数不是质数。例例2 2设计一个算法，判断整数设计一个算法，判断整数n(nn(n2 2）是否为质数。）是否为质数。第一步第一步：给定大于：给定大于2 2的整数的整数n n。第二步第二步：令：令i=2i=2。第三步第三步：用：用i i除除n n，得余数，得余数r r。第四步第四步：判断：判断“r=0”r=0”是否成立，若成立，则是否成立，若成立，则n n不是不是质数，结束算法；否则，质数

6、，结束算法；否则，将将i i的值增加的值增加1 1仍用仍用i i表示表示.第五步第五步:判断判断i i n-1n-1是否成立，若是，则是否成立，若是，则n n是质数；是质数；否则返回第三步。否则返回第三步。据德国新一期科学画报杂志报道，岁的加拿大青年迈克尔卡梅伦不久前利用分布式计算方法找到一个目前已知的最大素数，即的次方减，其位数超过百万位，是第个梅森素数。据悉，卡梅伦利用其配备的兆赫兹芯片的电脑加入到全球分布式计算网络中，花费天的时间得到了这一结果。尽管这台电脑自身性能并不高，但由于分布式计算网络连接了全球数十万台电脑，这些电脑自身有富裕资源的时候就通过网络进行运算，因此总的运算速度可达到每

7、秒万亿次，相当于一台超级计算机。素数又名质数，只能被和自身整除。法国教士马丁梅森于年介绍了一些形式为的次方减的素数，后来人们将该形式的素数称为梅森素数。年，美国程序设计师乔治沃特曼开始整理有关梅森素数的资料，编制了一个梅森素数计算程序，并将其放置在互联网上供数学爱好者使用。这就是“因特网梅森素数大搜索”（）计划。第和第个梅森素数都是用这种方法找到的。美国一家基金会还专门设了万美元的奖金，鼓励第一个找到超过千万位素数的人课堂练习课堂练习1.任意给定一个正实数，试设计一个算法求任意给定一个正实数，试设计一个算法求以这个正实数为半径的圆的面积。以这个正实数为半径的圆的面积。解解:第一步：第一步：_.

8、第二步：第二步：_.第三步：第三步：_.给定一个正实数给定一个正实数r得到圆的面积得到圆的面积S计算以计算以r为半径的圆的面积为半径的圆的面积2Sr练习练习2.任意定一个大于任意定一个大于1的整数的整数n，设计一算法求出，设计一算法求出n的所有因数。的所有因数。解：第一步第一步:给定一个大于给定一个大于1的正整数的正整数n.第二步第二步:令令i=1.第三步第三步:用用i除除n，得到余数，得到余数r.第四步第四步:判断判断“r=0”是否成立是否成立.若是，则若是，则i是是n的因的因数；否则，数；否则，i不是不是n的因数的因数.第五步第五步:使使i的值增加的值增加1，仍用，仍用i表示表示.第六步第

9、六步:判断判断“in”是否成立是否成立.若是，则算若是，则算法结束；否则，返回第三步法结束；否则，返回第三步.2.2.算法的特点：程序性、明确性、有限性算法的特点：程序性、明确性、有限性.六、课堂总结六、课堂总结1.1.知识结构知识结构算法的概念算法的概念算法的步骤算法的步骤 算法的特点算法的特点算法算法3.3.设计算法的注意事项设计算法的注意事项:(1)(1)认真分析问题，联系解决此问题的一般数学方认真分析问题，联系解决此问题的一般数学方法；法；(2)(2)综合考虑此类问题中可能涉及的各种情况；综合考虑此类问题中可能涉及的各种情况；(3)(3)借助有关的变量或参数对算法加以表达；借助有关的变

10、量或参数对算法加以表达；(4)(4)将解决问题的过程划分为若干个步骤；将解决问题的过程划分为若干个步骤；(5)(5)然后用简练的语言将各个步骤表示出来。然后用简练的语言将各个步骤表示出来。七、布置作业七、布置作业作业：作业：1.给出求给出求1+2+3+4+5的一个算的一个算法法.2.回顾二分法和用二分法求方程的近回顾二分法和用二分法求方程的近似解的算法似解的算法.3.预习预习1.1.2（程序框图与算法的基本（程序框图与算法的基本逻辑结构）逻辑结构）练习.给出求1+2+3+4+5的一个算法.算法1 按照逐一相加的程序进行.S1 计算1+2，得到3；S2 将第一步中的运算结果3与3相加，得到6；S

11、3 将第二步中的运算结果6与4相加，得到10；S4 将第三步中的运算结果10与5相加，得到15.算法2 可以运用公式1+2+3+n=n(n+1)/2直接计算.S1取n=5;S2计算n(n+1)/2;S3 输出运算结果.例例2.2.用用二分法二分法设计一个求方程设计一个求方程 x2-2=0（x0）的近似根的算法的近似根的算法.(.(精确度为精确度为0.005)0.005)第一步：第一步：第二步：第二步：第三步：第三步：第四步：第四步：第五步：第五步：2()2f xx令令 ，并且并且d=0.005.确定区间确定区间 a，b，满足满足f(a)f(b)0.0.2ab取区间中点取区间中点m 若若f(a)

12、f(m)0,0,则含零点的区间为则含零点的区间为否则，含零点的区间为否则，含零点的区间为将新得到的含零点的区间仍记为将新得到的含零点的区间仍记为 a,b；判断判断|a-b|d是否成立是否成立或或f(m)是否等于是否等于0.0.若是，则若是，则m是方程的近似解；是方程的近似解；否则，返回否则，返回 a,m；m，b.第三步第三步.对于区间对于区间a,b 上连续不断、上连续不断、且且f(a)f(b)0的函数的函数y=f(x),通过不断地把函通过不断地把函数数f(x)的零点所在的区间一分二，使区间的零点所在的区间一分二，使区间的两个端点逐步逼近零点，进而得到零点的两个端点逐步逼近零点，进而得到零点近似

13、值的方法叫做近似值的方法叫做二分法二分法.二分法二分法:ab|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 2522(0)yxx