1–3算法案列〔1课时2013–5–30.ppt

1.3 算法案例 复习 1.在程序框图中算法的基本逻辑结构有哪几种？ 顺序结构、条件结构、循环结构 一、辗转相除法 例1 求225和135的最大公约数 显然45是90和45的最大公约数，也就是225和135的最大公约数 思考1：从上面的两个例子可以看出计算的规律是什么？ S1：用大数除以小数 S2：除数变成被除数，余数变成除数 S3：重复S1，直到余数为0 225=135×1+90 135=90×1+45 90=45×2 8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+333 1813=333×5+148 333=148×2+37 148=37×4+0 显然37是148和37的最大公约数，也就是8251和6105的最大公约数 例2 用辗转相除法求8251和6105的最大公约数 开始 输入m，n 求m除以n的余数r m=n n=r r=0？ 是 输出m 结束 否 例1：用更相减损术求98与63的最大公约数. 98-63=35， 14-7=7. 21-7=14， 28-7=21， 35-28=7， 63-35=28， 因为63不是偶数，所以 所以最大公约数是7. 二、更相减损术 例2 用更相减损术求80与36的最大公约数. 练习：用更相减损术求30与12的最大公约数. 二、更相减损术 《九章算术》是中国古代的数学专著，其中的“更相减损术”也可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也.以等数约之.” 意思是： 第一步：任意给定两个正整数，判断它们是否都是偶数. 若是，用2约简；若不是，执行第二步. 第二步：以较大的数减去较小的数，接着把差与较小的数比较，并以大数减小数.继续这个操作，直到所得的数相等为止，则这个等数或这个数与约简的数的乘积就是所求的最大公约数. 开始 输入m，n nk？ m=n 是 输出m 结束 m≠n？ k=m-n 是 否 n=k m=k 否 例1 计算多项式ｆ（ｘ） =ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１当x = 5的值 因为ｆ（ｘ） =ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１ 所以ｆ（5）=5５＋5４＋5３＋5２＋5＋１ =3125＋625＋125＋25＋5＋１ = 3906 算法2： ｆ（5）=5５＋5４＋5３＋5２＋5＋１ =5×（5４＋5３＋5２＋5＋１） ＋１ =5×（5×（5３＋5２＋5 ＋１ ）＋１ ） ＋１ =5×（5×（ 5× （5２＋5 ＋１） ＋１ ）＋１ ） ＋１ =5×（5×（ 5× （5 × （5 ＋１ ） ＋１ ） ＋１ ）＋１ ） ＋１ 三、秦九韶算法 算法1： 例2 已知一个五次多项式为 用秦九韶算法求这个多项式当x = 5的值。 解： 将多项式变形： 按由里到外的顺序，依此计算一次多项式当x = 5时的值： 所以，当x = 5时，多项式的值等于17255.2 你从中看到了怎样的规律？怎么用程序框图来描述呢？ 程序框图 开始 输入n、an、x的值 v=an v=vx+ai 输入ai i≥0？ i=n-1 i=i-1 结束 是 输出v 否 * * * * * * * * * *