1.3 算法案例　　教案1

《1.3 算法案例　　教案1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§1.3算法案例教学目标：1.理解算法案例的算法步骤和程序框图;2.引导学生得出自己设计的算法程序;3.体会算法的基本思想,提高逻辑思维能力,发展有条理地思考与数学表达能力.教学重点：引导学生得出自己设计的算法步骤、程序框图和算法程序.教学难点：体会算法的基本思想,提高逻辑思维能力,发展有条理地思考与数学表达能力.教学过程：一、引入前面我们学习了算法步骤、程序框图和算法语句.今天我们将通过学习辗转相除法与更项减损术,秦九韶算法,排序,进位制等案例来进一步体会算法的思想.二、讲授新课(一)辗转相除法与更相减损术1.短除法求两

2、个正整数的最大公约数的步骤:先用两个数公有的质因数连续去除,一直除到所有的商是两个互质的数为止,然后把所有的处暑连乘起来.2.穷举法(也叫枚举法)穷举法求两个正整数的最大公约数的解题步骤:从两个较小的数开始由大到小列举,直到找到公约数立即中断列举,得到的公约数便是最大公约数.3.辗转相除法(1)辗转相除法:该算法又称欧几里得算法,就是对于给定的两个正整数,用较大的数除以较小的数,若余数不为零,则将余数和较小的数构成一对新数,继续上面的除法,直到余数为零,此时处暑就是所求两正整数的最大公约数.(2)算法步骤:以求正整数的最大

3、公约数为例.第一步,输入两个正整数.第二步,判断的大小,让表示较大的数,表示较小的数.第三步,计算除以的余数.第四步,让.第五步,如果,则的最大公约数等于;否则返回第三步.(3)程序框图为:略(4)程序1为:INPUT“m,n=”;m,nIFm0r=mMODnm=nn=rWENDPRINTmEND4.更项减

4、损术(1)更项减损术:我国早期也有解决求最大公约数问题的算法,就是更相减损术.《九章算术》是中国古代的数学专著,其中的“更相减损术”也可以来用来求两个数的最大公约数,即“可半者半之,不可半者,副置分母、子子之数,以少减多,更相减损,求其等也.以等数约之.”(2)算法步骤:第一步,任意给定两个正整数,判断它们是否都是偶数,若是,用约简之;若不是,执行第二步.第二步,以较大的数减去较小的数,接着把所得的差与较小的数比较,并以大数减去小数,继续这个操作,直到所得的数相等为止.则这个数(等数)或这个数与约简数的乘积就是所求的最大公

5、约数.(3)程序框图为:略(4)程序为:INPUT“m,n=”;m,nIFmnIFd>nTHENm=dELSEm=nn=dENDIFd=m-nWENDd=2^k*dPRINTdEND(二)秦九韶算法1.怎么求多项式当时的值?一个自然的做法是把代入多项式,急速各项的值,然后把它们加起来,这时,我们一共做了次乘法运算,次加法运算.另一种算法是先计算的值,然后计算的值,

6、这样每次都可以利用上一次计算的结构,这时,我们一共做了次乘法运算,次加法运算.第二种做法与第一种做法相比,乘法的运算此时减少了,因而能够提高运算效率,对于计算机来说,做一次乘法运算所用的时间比做一次加法运算要长得多,所以采用第二种算法,计算机能更快地得到结果.2.求多项式的值时,常用秦九韶算法,这种算法的运算次数较少,是多项式求值比较先进的算法,其实质是转化为求个一次多项式的值,共进行次乘法运算和次加法运算.3.秦九韶算法(1)改写多项式:设,,,.(2)算法步骤:第一步,输入多项式次数,最高次项的系数和的值.第二步,.第

7、三步,输入次项的系数.第四步,.第五步,判断是否大于等于,若是,则返回第三步;否则,输出多项式的值.(3)程序框图为:略(4)程序为:INPUT“n=”;nINPUT“an=”;aINPUT“x=”;xv=ai=n-1WHILEi>=0PRINT“i=”;iINPUT“ai=”;av=v*x+ai=i-1WENDPRINTvEND(三)进位制算法1.定义:人们为了计数和运算方面而约定的计数系统,“满进一”就是进制,是基数(其中是大于的整数).进制的数可以表示为一串数字连写在一起的形式.2.在日常生活中,我们最熟悉、最常用的

8、是十进制.除此之外还有二进制,七进制,八进制,十二进制,十六进制,六十进制等.3.非十进制的进制数(共有位)化为十进制数的计算公式为:(1)算法步骤:第一步,输入的值.第二步,.第三步,.第四步,判断是否成立,若是,则执行第五步;否则,返回第三步.第五步,输出的值.(2)程序框图为:略(3)程序为:IN