1.3算法案例ppt

1.3算法案例1.3.4十进制化K进制1.3.1辗转相除法和更相减损术1.3.2秦九韶算法1.3.3K进制化十进制1.3算法案例1.3.1辗转相除法和更相减损术复习1.研究一个实际问题的算法，主要从哪几方面展开？2.在程序框图中算法的基本逻辑结构有哪几种？3.在程序设计中基本的算法语句有哪几种？算法步骤、程序框图和编写程序三方面展开.顺序结构、条件结构、循环结构输入语句、输出语句、赋值语句、条件语句、循环语句探究一,辗转相除法思考1:在小学中我们是如何求出两个正整数的最大公约数的呢?算法案例之求最大公约数求以下几组正整数的最大公约数。(注：若整数m和n满足n整除m，则（m,n）=n。用（m,n）来表示m和n的最大公约数。)（1）（18，30）（2）（24，16）（3）（63，63）（4）（72，8）（5）（301，133）解：21824用公有质因数2除，3912用公有质因数3除，343和4互质不除了。得：18和24最大公约数是：2×3＝6例、求18与24的最大公约数：6；8；63；8；7；短除法想一想，如何求8251与6105的最大公约数？思考2:对于8251与6105这两个数，它们的最大公约数是多少？你是怎样得到的？由于它们公有的质因数较大，利用上述方法求最大公约数就比较困难.有没有其它的方法可以较简单的找出它们的最大公约数呢？思考3：注意到8251=6105×1+2146，那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系？我们发现6105=2146×2+1813，同理，6105与2146的公约数和2146与1813的公约数相等.思考4：重复上述操作，你能得到8251与6105这两个数的最大公约数吗？2146=1813×1+333，148=37×4+0.333=148×2+37，1813=333×5+148，8251=6105×1+2146，6105=2146×2+1813，定义:所谓的辗转相除法,就是对于给定的两个数,用较大的数除以较小的数,若余数不为零,则将余数和较小的数构成新的数对,继续上面的除法,直到大数被小数除尽,则这是较小的数就是原来两个数的最大公约数第一步，给定两个正整数m，n(mn).第二步，计算m除以n所得的余数r.第三步，m=n，n=r.第四步，若r=0，则m，n的最大公约数等于m；否则，返回第二步.思考5:你能把辗转相除法编成一个计算机程序吗？程序框图开始输入m，n求m除以n的余数rm=nn=rr=0？是输出m结束否INPUTm，nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND思考6:如果用当型循环结构构造算法，则用辗转相除法求两个正整数m、n的最大公约数的程序框图和程序分别如何表示？开始输入m，n求m除以n的余数rm=nr≠0？否输出m结束是n=rINPUTm，nWHILEr0r=mMODnm=nn=rWENDPRINTmEND练习：用辗转相除法求下列两数的最大公约数：（1）（225，135）（2）（98，196）（3）（72，168）（4）（153，119）45982417二、更相减损术《九章算术》是中国古代的数学专著，其中的“更相减损术”也可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也.以等数约之.”意思是：第一步：任意给定两个正整数，判断它们是否都是偶数.若是，用2约简；若不是，执行第二步.第二步：以较大的数减去较小的数，接着把差与较小的数比较，并以大数减小数.继续这个操作，直到所得的数相等为止，则这个等数或这个数与约简的数的乘积就是所求的最大公约数.例1：用更相减损术求98与63的最大公约数.98-63=35，14-7=7.21-7=14，28-7=21，35-28=7，63-35=28，因为63不是偶数，所以所以最大公约数是7.例2分别用辗转相除法和更相减损术求168与93的最大公约数.168=93×1+75，93=75×1+18，75=18×4+3，18=3×6.辗转相除法：更相减损术:168-93=75，93-75=18，75-18=57，57-18=39，39-18=21，21-18=3，18-3=15，15-3=12，12-3=9，9-3=6，6-3=3.例4求325，130，270三个数的最大公约数.因为325=130×2+65，130=65×2，所以325与130的最大公约数是65.因为270=65×4+10，65=10×6+5，10=5×2，所以65与270最大公约数是5.故325，130，270三个数的最大公约数是5.练习:用更相减损术求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？第一步，给定两个正整数m，n(mn).第二步，计算m-n所得的差k.第三步，比较n与k的大小，其中大者用m表示，小者用n表示.第四步，若m=n，则m，n的最大公约数等于m；否则，返回第二步.讨论:该算法的程序框图如何表示？开始输入m，nnk？m=n是输出m结束m≠n？k=m-n是否n=km=k否讨论:该程序框图对应的程序如何表述？INPUTm，nWHILEm≠nk=m-nIFnkTHENm=nn=kELSEm=kENDIFWENDPRINTmEND开始输入m，nnk？m=n是输出m结束m≠n？k=m-n是否n=km=k否布置作业：P45练习：1.P48习题1.3A组：1.1.3.2秦九韶算法1、什么是辗转相除法和更相减损术？2、辗转相除法和更相减损术，是求两个正整数的最大公约数的优秀算法，我们将算法转化为程序后，就可以由计算机来执行运算，实现了古代数学与现代信息技术的完美结合.复习探究三、秦九昭算法•思考1,在初中,我们是如何求一个多项式的值的?•思考2,已知一个n次多项式f(x)=anxn+an-1xn-1+…+a1x+a0当x=x0时，除了用代入法求解外是否还有更好的方法呢？秦九韶算法的基本思想思考1:对于多项式f(x)=x5+x4+x3+x2+x+1，求f(5)的值.4+3+2+1=10次乘法运算，5次加法运算.分析：把5代入多项式，若先计算各项的值，然后再相加，那么一共要做：思考2:另一种做法是先计算x2的值，然后依次计算x2·x，(x2·x)·x，((x2·x)·x)·x的值，这样每次都可以利用上一次计算的结果，这时一共做了：4次乘法运算，5次加法运算.思考3:有没有更有效的算法呢？利用后一种算法求多项式f(x)=anxn+an-1xn-1+…+a1x+a0的值，这个多项式应写成哪种形式？f(x)=anxn+an-1xn-1+…+a1x+a0=(anxn-1+an-1xn-2+…+a2x+a1)x+a0=((anxn-2+an-1xn-3+…+a2)x+a1)x+a0=…=(…((anx+an-1)x+an-2)x+…+a1)x+a0.这就是我国南宋时期数学家秦九韶在他的著作《数书九章》中提出的算法.思考4:对于f(x)=(…((anx+an-1)x+an-2)x+…+a1)x+a0，由内向外逐层计算一次多项式的值，其算法步骤如何？第一步，计算v1=anx+an-1.第二步，计算v2=v1x+an-2.第三步，计算v3=v2x+an-3.…第n步，计算vn=vn-1x+a0.上述方法称为秦九韶算法.思考5:在秦九韶算法中，记v0=an，那么第k步的算式是什么？vk=vk-1x+an-k(k=1，2，…，n)解：f(x)=((((4x+2)x+3.5)x-2.6)x+1.7)x-0.8.v1=4×5+2=22；v2=22×5+3.5=113.5；v3=113.5×5-2.6=564.9；v4=564.9×5+1.7=2826.2；v5=2826.2×5-0.8=14130.2.所以f(5)==14130.2.例1已知一个5次多项式为用秦九韶算法求f(5)的值.8.07.16.25.3242345xxxxxxf练习：阅读下列程序，说明它解决的实际问题是什么？INPUT“x=”；an=0y=0WHLEn5y=y+(n+1)*a∧nn=n+1WENDPRINTyEND求多项式在x=a时的值.12345234xxxxxf二、秦九韶算法的程序设计思考1:用秦九韶算法求多项式的值，可以用什么逻辑结构来构造算法？其算法步骤如何设计？第一步，输入多项式的次数n，最高次项的系数an和x的值.第二步，令v=an，i=n-1.第三步，输入i次项的系数ai.第四步，v=vx+ai，i=i-1.第五步，判断i≥0是否成立.若是，则返回第三步；否则，输出多项式的值v.程序框图开始输入n、an、x的值v=anv=vx+ai输入aii≥0？i=n-1i=i-1结束是输出v否讨论：请参照程序框图，写出该算法程序.开始输入n、an、x的值v=anv=vx+ai输入aii≥0？i=n-1i=i-1结束是输出v否INPUT“n=”；nINPUT“an=”；aINPUT“x=”；xv=ai=n-1WHILEi=0INPUT“ai=”；av=v*x+ai=i-1WENDPRINTvENDPRINT“i=”；i小结2.计算机的一个很重要的特点就是运算速度快，但评价算法好坏的一个重要标志是运算的次数，如果一个算法从理论上需要超出计算机允许范围内的运算次数，那么这样的算法就只能是一个理论算法.在多项式求值的各种算法中，秦九韶算法是一个优秀算法.1.秦九韶算法计算多项式的值及程序设计.布置作业：P45练习：2.P48习题1.3A组：2.1.3.3K进制化十进制1.简述辗转相除法和更相减损术的用途及内容.2、秦九韶算法的用途及内容.将这些算法转化为程序，就可以由计算机来完成相关运算.复习进位制的概念进位制是为了计数和运算方便而约定的记数系统.约定满二进一，就是二进制；满十进一，就是十进制；七天为一周，就是七进制；十二个月为一年，就是十二进制；六十秒为一分钟，六十分钟为一个小时，就是六十进制；等等.一般地，“满几进一”就是几进制.思考1:十进制使用0～9十个数字，那么二进制、五进制、七进制分别使用哪些数字？在十进制中10表示十，在二进制中10表示2.一般地，若k是一个大于1的整数，则以k为基数的k进制数可以表示为一串数字连写在一起的形式：anan-1…a1a0(k).“满K进一”就是K进制，其中k称为k进制的基数.那么k是一个什么范围内的数？与十进制类似，其它的进位制也可以按照位置原则计数.思考2：其中各个数位上的数字an，an-1，…，a1，a0的取值范围如何？例如:十进制数3721表示的数可以写成：110011（2）=1×25+1×24+0×23+0×22+1×21+1×20=515671（8）=5×83+6×82+7×81+1×80=3001.例1：把二进制数110011（2）化为十进制数.练习：把八进制数5671（8）化为十进制数.3×103+7×102+2×101+1×100.探究:如何将k进制数anan-1…a1a0(k)写成各数位上的数字与基数k的幂的乘积之和的形式？讨论:在二进制中，0+0，0+1，1+0，1+1的值分别是多少？anan-1……a1a0(k)=an×kn+an-1×kn-1+……+a1×k1+a0×k0例2:二进制数110011（3）化为十进制数是什么数？110011（3）讨论:anan-1……a1a0(2)中ai化为十进制数是什么数？=1×35+1×34+0×33+0×32+1×31+1×30=243+81+3+1=328.ai2i-1练习：将下列各进制数化为十进制数.（1）10304（4）；（2）4321（5）.10304（4）=1×44+3×42+4×40=308.4321（5）=4×53+3×52+2×51+1×50=586.探究：如何改进上述算法，把其他进位制化为十进制数？请举例说明.例3:设计一个算法，把2进制数a（共有n位）化为十进制数b，并转化成程序框图，写出程序.第二步，令b=0，i=1.