论文部分内容阅读
案例1 展转相除法与更相减损术的应用
例1 用展转相除法编写求63,81的最小公约数的程序.
程序如下:
总结 辗转相除法:辗转相除法就是把给定的两个数,用较大的数除以较小的数,若余数不为零,则将余数和较小的数,继续上面的除法,直到余数为零,此时的除数就是所求的最大公约数.
从算法思想我们可以看出,辗转相除法的基本步骤是用较大的数(用[a]表示)除以较小的数(用[b]表示),得到:[a=nb+r0≤r 由于这是一个反复执行的步骤,且执行的次数由余数[r]是否等于0决定,所以我们可以把它看作一个循环体,用循环结构就可以实现其算法.
例2 写出利用更相减损术求249与186的最大公约数的程序.
总结 1. 用更相减损术求两数最大公约数时,是当大数减小数恰好等于小数时停止减法,这时的小数就是要求的两数的最大公约数.
2. “更相减损术”与“辗转相除法”的异同点:“更相减损术”与“辗转相除法”这两种算法分别来源于东西方古代数学名著,但二者的算理却是相似的,有异曲同工之妙,主要区别在于辗转相除法进行的是除法运算,即辗转相除;而更相减损术进行的是减法运算,即辗转相减,但实质都是一个不断的递归过程.
案例2 秦九韶算法的应用
秦九韶算法的特点:通过一次式的反复计算,逐步得出高次多项式的值,对于一个[n]次多项式,只需做[n]次乘法和[n]次加法即可.秦九韶算法的计算量小,且逻辑简单.
例3 已知[n]次多项式[pn(x)=a0xn+a1xn-1][+⋯+an-1x+an],如果通常算法中,计算[x0k(k=2,3,4,⋯,n)]的值需[k-1]次乘法,计算[p3(x0)]的值是需要9次运算(6次乘法,3次加法),那么计算[pn(x0)]的值需要[12n(n+3)]次运算.
其算法步骤:
第一步:计算最内层[a0x+a1]的值,将[a0x+a1]的值赋给一个变量[v1];
第二步:计算[(a0x+a1)x+a2]的值,可以改写为[v1x+a2],将[v1x+a2]的值赋给一个变量[v2];
以此类推,即每一步计算之后都赋于一个新值[vn],即从最内层括号到最外层括号的值依次赋予变量[v1],[v2],[v3],[⋯],[vk],[⋯],[vn],第[n]步的求值[vn=vn-1x+an]即为所求多项式的值.
秦九韶的算法中:[p0(x)=a,pk+1(x)=xpk(x)][+ak+1(k=0,1,2,⋯,n-1)].
利用该算法,计算[p3(x0)]的值共需6次运算,计算[pn(x0)]的值共需要[2n]次运算.
案例3 算法在二分法中的应用
例4 设区间[0,1]是方程[fx=0]的有解区间,设计一个用二分法求此方程在区间[0,1]上一个近似解的方法,并画出程序框图,要求精确到[ε].
算法如下:
第一步,确定有解的区间[[a,b]][fafb<0.]
第二步,取[[a,b]]的中点[a+b2].
第三步,计算函数[fx]在中点处的函数值[fa+b2].
第四步,判断函数值[fa+b2]是否为0.
(1)如果为0,[x=a+b2]就是方程的解,问题就得到了解决.
(2)如果函数值[fa+b2]不为0,则分两种情况:
①若[fafa+b2<0],则确定新的有解区间[a,a+b2];
②若[fafa+b2>0],则确定新的有解区间[a+b2,b].
第五步,判断新的有解区间的长度大于误差[ε]:
(1)如果新的有解区间的长度大于误差[ε],则在新的有解区间的基础上重复上述步骤;
(2)如果新的有解区间长度小于或等于误差[ε],则取新的有解区间的中点为方程的近似解.
程序框图如下图:
案例4 算法在分期付款中的应用
例5 张老师购买安居工程集资房92m2,单价为1000元/m2,一次性国家财政补贴28800元,学校补贴14400元,余款由个人负担,房地产开发公司对教师实行分期付款(注①),每期为一年,等额付款,签订购房合同后一年付款一次,再经过一年又付款一次等等,共付10次,10年后付清,如果按年利率7.5%,每年按复利计算(注②),那么每年应付款多少元?画出程序框图,并写出计算所需的程序.(计算结果精确到百元)(注③)
注:①分期付款,各期所付的款以及最后一次付款时所生的利息合计应等于个人负担后购房余款的现价及这个现价到最后一次付款时所生的利息之和.
②每年按复利计算,即本年利息计入次年的本金利息.
③必要时参考下列数据:
总结 循环语句作用主要用来处理算法中的循环结构,在处理一些需要重复计算的问题,如累加求和,累乘求积等问题时,常用到循环语句来编写程序.
【练习】
1.用辗转相除法和更相减损术求48与30的最大公约数,写出具体算法步骤.
2.写出求[m=60]和[n=33]的最大公约数的算法和程序框图.
3.用秦九韶算法计算多项式[f(x)=x6-12x5+60x4-][160x3+240x2-192x+64]当[x=2]时的值.
4.在国内投寄外埠平信,每封信不超过20g需付邮资8角,超过20g而不超过40g付邮资16角,超过40g而不超过60g付邮资24角,若信的质量为[x0
例1 用展转相除法编写求63,81的最小公约数的程序.
程序如下:
总结 辗转相除法:辗转相除法就是把给定的两个数,用较大的数除以较小的数,若余数不为零,则将余数和较小的数,继续上面的除法,直到余数为零,此时的除数就是所求的最大公约数.
从算法思想我们可以看出,辗转相除法的基本步骤是用较大的数(用[a]表示)除以较小的数(用[b]表示),得到:[a=nb+r0≤r 由于这是一个反复执行的步骤,且执行的次数由余数[r]是否等于0决定,所以我们可以把它看作一个循环体,用循环结构就可以实现其算法.
例2 写出利用更相减损术求249与186的最大公约数的程序.
总结 1. 用更相减损术求两数最大公约数时,是当大数减小数恰好等于小数时停止减法,这时的小数就是要求的两数的最大公约数.
2. “更相减损术”与“辗转相除法”的异同点:“更相减损术”与“辗转相除法”这两种算法分别来源于东西方古代数学名著,但二者的算理却是相似的,有异曲同工之妙,主要区别在于辗转相除法进行的是除法运算,即辗转相除;而更相减损术进行的是减法运算,即辗转相减,但实质都是一个不断的递归过程.
案例2 秦九韶算法的应用
秦九韶算法的特点:通过一次式的反复计算,逐步得出高次多项式的值,对于一个[n]次多项式,只需做[n]次乘法和[n]次加法即可.秦九韶算法的计算量小,且逻辑简单.
例3 已知[n]次多项式[pn(x)=a0xn+a1xn-1][+⋯+an-1x+an],如果通常算法中,计算[x0k(k=2,3,4,⋯,n)]的值需[k-1]次乘法,计算[p3(x0)]的值是需要9次运算(6次乘法,3次加法),那么计算[pn(x0)]的值需要[12n(n+3)]次运算.
其算法步骤:
第一步:计算最内层[a0x+a1]的值,将[a0x+a1]的值赋给一个变量[v1];
第二步:计算[(a0x+a1)x+a2]的值,可以改写为[v1x+a2],将[v1x+a2]的值赋给一个变量[v2];
以此类推,即每一步计算之后都赋于一个新值[vn],即从最内层括号到最外层括号的值依次赋予变量[v1],[v2],[v3],[⋯],[vk],[⋯],[vn],第[n]步的求值[vn=vn-1x+an]即为所求多项式的值.
秦九韶的算法中:[p0(x)=a,pk+1(x)=xpk(x)][+ak+1(k=0,1,2,⋯,n-1)].
利用该算法,计算[p3(x0)]的值共需6次运算,计算[pn(x0)]的值共需要[2n]次运算.
案例3 算法在二分法中的应用
例4 设区间[0,1]是方程[fx=0]的有解区间,设计一个用二分法求此方程在区间[0,1]上一个近似解的方法,并画出程序框图,要求精确到[ε].
算法如下:
第一步,确定有解的区间[[a,b]][fafb<0.]
第二步,取[[a,b]]的中点[a+b2].
第三步,计算函数[fx]在中点处的函数值[fa+b2].
第四步,判断函数值[fa+b2]是否为0.
(1)如果为0,[x=a+b2]就是方程的解,问题就得到了解决.
(2)如果函数值[fa+b2]不为0,则分两种情况:
①若[fafa+b2<0],则确定新的有解区间[a,a+b2];
②若[fafa+b2>0],则确定新的有解区间[a+b2,b].
第五步,判断新的有解区间的长度大于误差[ε]:
(1)如果新的有解区间的长度大于误差[ε],则在新的有解区间的基础上重复上述步骤;
(2)如果新的有解区间长度小于或等于误差[ε],则取新的有解区间的中点为方程的近似解.
程序框图如下图:
案例4 算法在分期付款中的应用
例5 张老师购买安居工程集资房92m2,单价为1000元/m2,一次性国家财政补贴28800元,学校补贴14400元,余款由个人负担,房地产开发公司对教师实行分期付款(注①),每期为一年,等额付款,签订购房合同后一年付款一次,再经过一年又付款一次等等,共付10次,10年后付清,如果按年利率7.5%,每年按复利计算(注②),那么每年应付款多少元?画出程序框图,并写出计算所需的程序.(计算结果精确到百元)(注③)
注:①分期付款,各期所付的款以及最后一次付款时所生的利息合计应等于个人负担后购房余款的现价及这个现价到最后一次付款时所生的利息之和.
②每年按复利计算,即本年利息计入次年的本金利息.
③必要时参考下列数据:
总结 循环语句作用主要用来处理算法中的循环结构,在处理一些需要重复计算的问题,如累加求和,累乘求积等问题时,常用到循环语句来编写程序.
【练习】
1.用辗转相除法和更相减损术求48与30的最大公约数,写出具体算法步骤.
2.写出求[m=60]和[n=33]的最大公约数的算法和程序框图.
3.用秦九韶算法计算多项式[f(x)=x6-12x5+60x4-][160x3+240x2-192x+64]当[x=2]时的值.
4.在国内投寄外埠平信,每封信不超过20g需付邮资8角,超过20g而不超过40g付邮资16角,超过40g而不超过60g付邮资24角,若信的质量为[x0