1.3 算法案例　　教案1

1.3 算法案例教学目标：1.理解算法案例的算法步骤和程序框图;2.引导学生得出自己设计的算法程序;3.体会算法的基本思想,提高逻辑思维能力,发展有条理地思考与数学表达能力.教学重点：引导学生得出自己设计的算法步骤、程序框图和算法程序.教学难点：体会算法的基本思想,提高逻辑思维能力,发展有条理地思考与数学表达能力.教学过程：一、引入前面我们学习了算法步骤、程序框图和算法语句.今天我们将通过学习辗转相除法与更项减损术,秦九韶算法,排序,进位制等案例来进一步体会算法的思想.二、讲授新课(一)辗转相除法与更相减损术1.短除法 求两个正整数的最大公约数的步骤:先用两个数公有的质因数连续去除,一直除到所有的商是两个互质的数为止,然后把所有的处暑连乘起来.2.穷举法(也叫枚举法) 穷举法求两个正整数的最大公约数的解题步骤:从两个较小的数开始由大到小列举,直到找到公约数立即中断列举,得到的公约数便是最大公约数.3.辗转相除法 (1)辗转相除法:该算法又称欧几里得算法,就是对于给定的两个正整数,用较大的数除以较小的数,若余数不为零,则将余数和较小的数构成一对新数,继续上面的除法,直到余数为零,此时处暑就是所求两正整数的最大公约数. (2)算法步骤:以求正整数的最大公约数为例. 第一步,输入两个正整数. 第二步,判断的大小,让表示较大的数,表示较小的数. 第三步,计算除以的余数. 第四步,让. 第五步,如果,则的最大公约数等于;否则返回第三步. (3)程序框图为:略 (4)程序1为: INPUT “m,n=”;m,n IF mn THEN t=m m=n n=t END IF DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END 程序2为:INPUT “m,n=”;m,n IF mn THEN t=m m=n n=t END IF r=1 WHILE r0 r=m MOD n m=n n=r WEND PRINT m END4.更项减损术 (1)更项减损术:我国早期也有解决求最大公约数问题的算法,就是更相减损术.九章算术是中国古代的数学专著,其中的“更相减损术”也可以来用来求两个数的最大公约数,即“可半者半之,不可半者,副置分母、子子之数,以少减多,更相减损,求其等也.以等数约之.” (2)算法步骤: 第一步,任意给定两个正整数,判断它们是否都是偶数,若是,用约简之;若不是,执行第二步. 第二步,以较大的数减去较小的数,接着把所得的差与较小的数比较,并以大数减去小数,继续这个操作,直到所得的数相等为止.则这个数(等数)或这个数与约简数的乘积就是所求的最大公约数. (3)程序框图为:略 (4)程序为: INPUT “m,n=”;m,n IF mn THEN t=m m=n n=t END IF k=0 WHILE (m MOD 2=0) AND (n MOD 2=0) m=m/2 n=n/2 k=k+1 WEND d=m-n WHILE dn IF dn THEN m=d ELSE m=n n=d END IF d=m-n WEND d=2k*d PRINT d END (二)秦九韶算法1.怎么求多项式当时的值? 一个自然的做法是把代入多项式,急速各项的值,然后把它们加起来,这时,我们一共做了次乘法运算,次加法运算. 另一种算法是先计算的值,然后计算的值,这样每次都可以利用上一次计算的结构,这时,我们一共做了次乘法运算,次加法运算. 第二种做法与第一种做法相比,乘法的运算此时减少了,因而能够提高运算效率,对于计算机来说,做一次乘法运算所用的时间比做一次加法运算要长得多,所以采用第二种算法,计算机能更快地得到结果.2.求多项式的值时,常用秦九韶算法,这种算法的运算次数较少,是多项式求值比较先进的算法,其实质是转化为求个一次多项式的值,共进行次乘法运算和次加法运算.3.秦九韶算法 (1)改写多项式: 设,.(2)算法步骤: 第一步,输入多项式次数,最高次项的系数和的值. 第二步,. 第三步,输入次项的系数. 第四步,. 第五步,判断是否大于等于,若是,则返回第三步;否则,输出多项式的值.(3)程序框图为:略(4)程序为: INPUT “n=”;n INPUT “an=”;a INPUT “x=”;x v=a i=n-1 WHILE i=0 PRINT “i=”;i INPUT “ai=”;a v=v*x+a i=i-1 WEND PRINT v END(三)进位制算法1.定义:人们为了计数和运算方面而约定的计数系统,“满进一”就是进制,是基数(其中是大于的整数).进制的数可以表示为一串数字连写在一起的形式.2.在日常生活中,我们最熟悉、最常用的是十进制.除此之外还有二进制,七进制,八进制,十二进制,十六进制,六十进制等.3.非十进制的进制数(共有位)化为十进制数的计算公式为: (1)算法步骤: 第一步,输入的值. 第二步,. 第三步,. 第四步,判断是否成立,若是,则执行第五步;否则,返回第三步. 第五步,输出的值. (2)程序框图为:略 (3)程序为: INPUT “a,k,n=”;a,k,n b=0 i=1 t=a MOD 10 DO b=b+t*k(i-1) a=a10 t= a MOD 10i=i+1 LOOP UNTIL in PRINT b END4.十进制数转化为非十进制的进制数的方法 (1)算法步骤: 第一步,输入的值. 第二步,求出除以所得的商,余数. 第三步,若,则,返回第二步;否则执行第四步. 第四步,将依次得到的余数从右到左排列,得到进制数. (2)程序框图为:略 (3)程序为: INPUT “a,k=”;a,n b=0 i=0 DO q=ak r=a MOD k b=b+r*10ii=i+1 LOOP UNTIL q=0 PRINT b END(四)实数排序算法1.直接插入排序法 从第一个数开始,依次把每个数插入到前面已排好序的序列的适当位置,具体操作时,把要插入的数与有序序列的最后一个数比较,如果该数大于序列中的最后一个数,则直接将该数作为前面序列的最后一个数,否则继续与前面的数相比较,直到找到合适的位置为止. 程序为: INPUT “n=”;n DIM a(n) INPUT a a(1)=a i=2 WHILE i=n Input a flag=0 j=1 DO IF a(j)=i IF flag=0 THEN a(i)=a ELSE t=i DO a(t)=a(t-1) t=t-1 LOOP UNTIL t=k a(k)=a END IF i=i+1 WEND i=1 WHILE i=n PRINT a(i) i=i+1 WEND END2.冒泡排序法 这种方法的基本思路是:将待排序的数看作是竖着排列的“气泡”,较小的数比较轻,要往上浮.在这种方法中,我们要对这个“气泡”序列进行若干趟处理,每一趟处理都要自上而下两两进行比较,按较大数在下,较小数在上的原则,如果顺序不对,就交换两个数的位置.排序完成的已经是在某一趟中无交换,即交换次数为.在排序过程中,小的数就如气泡一样逐层上浮,大的数逐个下沉,因此被形象地比喻为“冒泡”,古城这种排序算法为冒泡法. 程序1为: INPUT “n=”;n DIM a(n) i=1 WHILE i=n INPUT a a(i)=a i=i+1 WEND i=1 WHILE i=n-1 j=1 WHILE j=n-i IF a(j)a(j+1) THEN t=a(j) a(j)=a(j+1) a(j+1)=t END IF j=j+1 WEND i=i+1 WEND i=1 WHILE i=n PRINT a(i) i=i+1 WEND END程序2为: INPUT “n=”;n DIM a(n) i=1 WHILE i=n INPUT a a(i)=a i=i+1 WEND i=1 DO flag=1j=1 WHILE j=n-i IF a(j)a(j+1) THEN t=a(j) a(j)=a(j+1) a(j+1)=t flag=0 END IF j=j+1 WEND i=i+1 LOOP UNTIL flag=1 i=1 WHILE i=n PRINT a(i) i=i+1 WEND END3.选择排序法 这种方法是在所有的数据中找出最小的元素,并与序列中的第一个数据互换,然后在余下的数据中再找出最小的数与第二个数据相互换,如此直到最后排序完为止. 该法与冒泡法相比,需要交换的次数较少,因而效率要比冒泡法高.程序1为: INPUT “n=”;n DIM a(n) i=1 WHILE i=n INPUT a a(i)=a i=i+1 WEND i=1 WHILE i=n-1 j=i+1 WHILE j=n IF a(i)a(j) THEN t=a(i) a(i)=a(j) a(j)=t END IF j=j+1 WEND i=i+1 WEND i=1 WHILE i=n PRINT a(i) i=i+1 WEND END程序2为: INPUT “n=”;n DIM a(n) i=1 WHILE i=n INPUT a a(i)=a i=i+1 WEND i=1 WHILE i=n-1 k=ij=i+1 WHILE j=n IF a(k)a(j) THEN j=j END IF j=j+1 WEND IF ik THEN t=a(i) a(i)=a(k) a(k)=t END IF i=i+1 WEND i=1 WHILE i=n PRINT a(i) i=i+1 WEND END4.快速排序法 在序列中任取一个数作为基准(设为),一次基准将序列划分为左右两个较小的序列区,且坐标序列区中的数均小于基准,右边序列区中的数均大于基准,然后对两个序列区分别再选择基准排序,直到所有序列区中的数据元素均已排好序.三、典例剖析(一)辗转相除法与更项减损术例1 分别用辗转相除法和更相减损术求与的最大公约数.解: (1)辗转相除法 第一步, 第二步, 第三步, 因此,是与的最大公约数. (2)更相减损术 第一步, 第二步, 第三步, 因此,是与的最大公约数.点评: 更相减损术与辗转相除法的比较:尽管两种算法分别来源于东西方古代数学专著,但是二者的算理却是相似的,右异曲同工之妙.主要区别在于辗转相除法进行的是出发运算,即辗转相除;而更相减损术进行的是减法运算,即辗转相减,但是实质都是一个不断的递归过程.例2 请用辗转相除法和更相减损术求和的最大公约数.解：(1)辗转相除法 第一步, 第二步, 因此,是和的最大公约数. (2)更相减损术 第一步,因为两个数皆为偶数,首先除以得到,在求这两个数的最大公约数 第二步, 第三步, 第四步, 第五步, 第六步, 因此,是和的最大公约数. 例3 用辗转相除法和更相减损术求三个数的最大公约数.解：(1)辗转相除法 , 则与的最大公约数为 又, 则与的最大公约数为 因此,三个数的最大公约数为.(2)更相减损术 , 则与的最大公约数为 又, 则与的最大公约数为 因此,三个数的最大公约数为.练习: 1.用辗转相除法求和的最大公约数.(答案:) 2.用更相减损术求和的最大公约数.(答案:) 3.求的最大公约数.(答案:)(二)秦九韶算法例1 已知次多项式,如果在一种算法中,计算的值需要次乘法,计算的值共需要次运算(次乘法次加法),那么计算的值需要_次运算.下面给出一种减少运算次数的算法:,.利用该算法,计算的值共需要次运算,计算的值共需要_次运算.答案: 点评: 秦九韶算法使用一般的多项式的求值问题.直接法乘法运算的次数最多可到达,加法最多次.秦九韶算法通过转化把乘法运算的次数减少到最多次,加法最多次.例2 已知一个次多项式为,用秦九韶算法求这个多项式当时的值.解: 根据秦九韶算法,把多项式改写成如下形式: 按照从内到外的顺序,一次计算一次多项式当时的值: ,所以,当时,多项式的值为点评: 如果多项式函数中又缺项的画,要以系数为的项补齐后再计算.练习: 1.已知多项式函数,求. 2.当时,用秦九韶算法求多项式的值. 3.用秦九韶算法求多项式当时的值.答案: 1.; 2.; 3.例3 某城市2001年末汽车保有量为万辆,预计此后每年报废上一年末汽车保有量的,并且每年新增汽车万辆.设计算法,计算经过多少年可使汽车保有量达到万辆.将此算法用程序语言给出.解：设,经过几年的汽车保有量为,则 上述各式充分说明了秦九韶算法的优点:可以通过递推关系进行迭代处理.程序为:C=0.94A=30n=0WHILE A40 A=A*C+3 n=n+1WENDPRINT nEND(三)进位制算法例1 (1)二进制数用十进制表示是( ) A. B. C. D. (2)十进制数用二进制表示是( ) A. B. C. D.答案: (1) C (2) A例2 (1)一斤半的东西,用现在的两制(即两等于斤)计是两,若按过去的 两制(即两等于斤)计是_两. (2)现在最常用的十进制是逢十进一,而用角度制度量角时,却是是逢六十进一.在角度制中,度分等于_分.答案: (1) (2) 例3 (1)把二进制数化为十进制数.(2)把转化为二进制数.解: (1) (2) 所以例4 (1)将八进制数化为十进制数,并编写出一个实现算法的程序. (2)把十进制数化为三进制数,并写出程序语句.解：(1) 程序略(可参加把进制数转化为十进制数的一般方法)(2) 所以 程序略(可参加把十进制数转化为进制数的一般方法)练习: 1.将十进制数转化为二进制数. 2.把分别转化为十进制数和