资源描述
114算法案例算法案例学习目标学习目标1通过案例,进一步体会算法的思想;通过案例,进一步体会算法的思想;2理解并能利用案例中的算法解决具体问题理解并能利用案例中的算法解决具体问题课堂互动讲练课堂互动讲练知能优化训练知能优化训练11.4算算法法案案例例课前自主学案课前自主学案课前自主学案课前自主学案温故夯基温故夯基1编写算法常用的语句有输入语句、编写算法常用的语句有输入语句、_、赋值语句、赋值语句、_、循环语句,对应着、循环语句,对应着_结结构、条件结构、构、条件结构、_结构结构2在两个正数的所有公约数中最大的一个公约数在两个正数的所有公约数中最大的一个公约数为它们的为它们的_输出语句输出语句条件语句条件语句顺序顺序循环循环最大公约数最大公约数知新益能知新益能1辗转相除法辗转相除法伪代码如下:伪代码如下:a MOD b2秦九韶算法秦九韶算法伪代码如下:伪代码如下:问题探究问题探究1用秦九韶算法求用秦九韶算法求x2时,时,f(x)x33x2x1的的值第一个一次多项式的值为多少?值第一个一次多项式的值为多少?提示:提示:由秦九韶算法知由秦九韶算法知f(x)(x3)x1x1.由内到外第一个一次多项式的值为由内到外第一个一次多项式的值为235.2“秦九韶算法秦九韶算法”的实质是什么?的实质是什么?提示:提示:其实质是通过一次式的反复计算,逐步得出其实质是通过一次式的反复计算,逐步得出高次多项式的值,对于一个高次多项式的值,对于一个n次多项式,最多只需次多项式,最多只需做做n次乘法和次乘法和n次加法即可次加法即可课堂互动讲练课堂互动讲练辗转相除法辗转相除法考点突破考点突破辗转相除法的操作过程是先用两个数中较大的数除辗转相除法的操作过程是先用两个数中较大的数除以较小的数,得商和余数;再用除数除以余数,重以较小的数,得商和余数;再用除数除以余数,重复操作,直到出现余数为零,易出错的地方是用商复操作,直到出现余数为零,易出错的地方是用商除以余数,要特别注意除以余数,要特别注意 利用辗转相除法求利用辗转相除法求294和和84的最大公约数的最大公约数【思路点拨思路点拨】利用辗转相除法,依据利用辗转相除法,依据mnqr,反复执行,直到反复执行,直到r0为止为止【解解】29484342,84422,即,即294与与84的最大公约数为的最大公约数为42.【名师点评】【名师点评】利用辗转相除法求给定的两个数的利用辗转相除法求给定的两个数的最大公约数,即利用带余除法,用数对中较大的数最大公约数,即利用带余除法,用数对中较大的数除以较小的数,若余数不为零,则将余数和较小的除以较小的数,若余数不为零,则将余数和较小的数构成新的数对,再利用带余除法,直到大数被小数构成新的数对,再利用带余除法,直到大数被小数除尽,则这时的较小数就是原来两个数的最大公数除尽,则这时的较小数就是原来两个数的最大公约数约数变式训练变式训练1利用辗转相除法求利用辗转相除法求46,115和和276的最大的最大公约数的最大公约数公约数的最大公约数解:解:求三个数的最大公约数,可以先求两个数的最求三个数的最大公约数,可以先求两个数的最大公约数,然后求第三个数与前两个数的最大公约大公约数,然后求第三个数与前两个数的最大公约数数276211546,11524623,46232所以所以276与与115的最大公约数为的最大公约数为23.又又46与与23的最大公约数为的最大公约数为23,所以,所以46、115和和276的的最大公约数为最大公约数为23.用二分法求方程的近似解或函数的零点可以设计程用二分法求方程的近似解或函数的零点可以设计程序用计算机来完成序用计算机来完成二分法二分法 写出用二分法求方程写出用二分法求方程x220的一个正的近的一个正的近似解似解(误差不超过误差不超过0.005)的算法的算法【思路点拨思路点拨】令令f(x)x22,确定有解区间,确定有解区间1,2,用二分法确定符合限制条件的解即可,用二分法确定符合限制条件的解即可【名师点评】【名师点评】用二分法求方程的近似解的步骤用二分法求方程的近似解的步骤:(1)画草图探索解所在的区间;画草图探索解所在的区间;(2)用二分法求符合用二分法求符合限制条件的解;限制条件的解;(3)编制程序用计算机完成编制程序用计算机完成变式训练变式训练2写出用二分法求方程写出用二分法求方程x32x30在在区间区间1,2内的一个近似解内的一个近似解(误差不超过误差不超过0.001)的一个的一个算法算法秦九韶算法秦九韶算法利用秦九韶算法将利用秦九韶算法将f(x)改写成如下形式改写成如下形式f(x)(anxan1)xan2)xa1)xa0,其计算步,其计算步骤为:先计算骤为:先计算v1anxan1,再计算,再计算v2v1xan2,每次都是把上一次的结果乘以,每次都是把上一次的结果乘以x再与下一再与下一个系数相加,其计算量为乘法个系数相加,其计算量为乘法n次,加法次,加法n次次 用秦九韶算法计算多项式用秦九韶算法计算多项式f(x)x612x560 x4160 x3240 x2192x64当当x2时的值时的值【解】【解】将将f(x)改写为改写为f(x)(x12)x60)x160)x240)x192)x64.由内向外依次计算一次多项式当由内向外依次计算一次多项式当x2时的值时的值v01,v1121210,v21026040,v340216080,v480224080,v580219232,v6322640,f(2)0,即,即x2时,原多项式的值为时,原多项式的值为0.【名师点评名师点评】利用秦九韶算法计算多项式的值关利用秦九韶算法计算多项式的值关键是能正确地将所给多项式改写,然后由内向外逐键是能正确地将所给多项式改写,然后由内向外逐次计算,由于后项计算需用到前项的结果,故应认次计算,由于后项计算需用到前项的结果,故应认真、细心,确保中间结果的准确性真、细心,确保中间结果的准确性变式训练变式训练3用秦九韶算法求多项式用秦九韶算法求多项式f(x)5x54x43x28x6,当,当x3时的值时的值解:解:f(x)5x54x43x28x6(5x4)x0)x3)x8)x6,当当x3时,时,v05,v153411,v2113033,v33333102,v410238314,v531436936.f(3)936.方法感悟方法感悟1辗转相除法是当大数被小数除尽时,结束除法辗转相除法是当大数被小数除尽时,结束除法运算,较小的数就是最大公约数运算,较小的数就是最大公约数2用秦九韶算法可大大降低乘法的运算次数,提用秦九韶算法可大大降低乘法的运算次数,提高了运算速度用此方法求值,关键是正确地将所高了运算速度用此方法求值,关键是正确地将所给多项式改写,然后由内向外计算,由于后项计算给多项式改写,然后由内向外计算,由于后项计算需用到前项结果,故应认真、细心,确保结果的准需用到前项结果,故应认真、细心,确保结果的准确性确性知能优化训练知能优化训练本部分内容讲解结束本部分内容讲解结束点此进入课件目录点此进入课件目录按按ESC键退出全屏播放键退出全屏播放谢谢使用谢谢使用
展开阅读全文