人教A版高中数学必修3第一章 算法初步1.3 算法案例课件(4).ppt

1.3算法案例,1.3.4十进制化K进制,1.3.1辗转相除法和更相减损术,1.3.2秦九韶算法,1.3.3K进制化十进制,1.3算法案例,1.3.1辗转相除法和更相减损术,复习,1.研究一个实际问题的算法，主要从哪几方面展开？,2.在程序框图中算法的基本逻辑结构有哪几种？,3.在程序设计中基本的算法语句有哪几种？,算法步骤、程序框图和编写程序三方面展开.,顺序结构、条件结构、循环结构,输入语句、输出语句、赋值语句、条件语句、循环语句,情境创设,韩信是秦末汉初的著名军事家.据说有一次汉高祖刘邦在卫士的簇拥下来到练兵场,刘邦问韩信有什么方法,不要逐个报数,就能知道场上的士兵的人数,韩信先令士兵排成3列纵队,结果有2人多余,接着下令排成5列纵队,结果又多出3人,随后他又下令改为7列纵队,这次又剩下2人无法成整行.在场的人都哈哈大笑,以为韩信不能清点出准确的人数,不料笑声刚落,韩信高声报告共有士兵2333人.众人听了一楞,不知道韩信用什么方法这么快就能得到正确的结果的.今天,我们将以这些古典案例的思想,设计出适宜计算机的运行程序,提高我们对基本算法结构和算法语句在实际中的运用能力.,探究一,辗转相除法,思考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）,例、求18与24的最大公约数：,6；,8；,63；,8；,7；,短除法,想一想，如何求8251与6105的最大公约数？,思考2:对于8251与6105这两个数，它们的最大公约数是多少？你是怎样得到的？,由于它们公有的质因数较大，利用上述方法求最大公约数就比较困难.有没有其它的方法可以较简单的找出它们的最大公约数呢？,思考3：注意到8251=61051+2146，那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系？,我们发现6105=21462+1813，同理，6105与2146的公约数和2146与1813的公约数相等.,思考4：重复上述操作，你能得到8251与6105这两个数的最大公约数吗？,2146=18131+333，,148=374+0.,333=1482+37，,1813=3335+148，,8251=61051+2146，,6105=21462+1813，,定义:所谓的辗转相除法,就是对于给定的两个数,用较大的数除以较小的数,若余数不为零,则将余数和较小的数构成新的数对,继续上面的除法,直到大数被小数除尽,则这是较小的数就是原来两个数的最大公约数,辗转相除法求两个数的最大公约数，其算法可以描述如下：,辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构,思考4：辗转相除直到何时结束？主要运用的是哪种算法结构？,如此循环，直到得到结果。,输入两个正整数m和n；,求余数r：计算m除以n，将所得余数存放到变量r中；,更新被除数和余数：m=n，n=r。,判断余数r是否为0：若余数为0则输出结果，否则转向第步继续循环执行。,第一步，给定两个正整数m，n(mn).,第二步，计算m除以n所得的余数r.,第三步，m=n，n=r.,第四步，若r=0，则m，n的最大公约数等于m；否则，返回第二步.,思考5:你能把辗转相除法编成一个计算机程序吗？,程序框图,INPUTm，n,DO,r=mMODn,m=n,n=r,LOOPUNTILr=0,PRINTm,END,思考6:如果用当型循环结构构造算法，则用辗转相除法求两个正整数m、n的最大公约数的程序框图和程序分别如何表示？,INPUTm，n,WHILEr0,r=mMODn,m=n,n=r,WEND,PRINTm,END,练习：用辗转相除法求下列两数的最大公约数：（1）（225，135）（2）（98，196）（3）（72，168）（4）（153，119）,45,98,24,17,二、更相减损术,九章算术是中国古代的数学专著，其中的“更相减损术”也可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也.以等数约之.”,意思是：,第一步：任意给定两个正整数，判断它们是否都是偶数.若是，用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=931+75，93=751+18，75=184+3，18=36.,辗转相除法：,更相减损术:,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.,例3用更相减损术求80与36的最大公约数.,例4求325，130，270三个数的最大公约数.,因为325=1302+65，130=652，所以325与130的最大公约数是65.,因为270=654+10，65=106+5，10=52，所以65与270最大公约数是5.,故325，130，270三个数的最大公约数是5.,练习:用更相减损术求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？,第一步，给定两个正整数m，n(mn).,第二步，计算m-n所得的差k.,第三步，比较n与k的大小，其中大者用m表示，小者用n表示.,第四步，若m=n，则m，n的最大公约数等于m；否则，返回第二步.,讨论:该算法的程序框图如何表示？,讨论:该程序框图对应的程序如何表述？,INPUTm，n,WHILEmn,k=m-n,IFnkTHEN,m=n,n=k,ELSE,m=k,ENDIF,WEND,PRINTm,END,1、辗转相除法.,小结,2、更相减损术.,布置作业：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的值，然后依次计算x2x，(x2x)x，(x2x)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=45+2=22；,v2=225+3.5=113.5；,v3=113.55-2.6=564.9；,v4=564.95+1.7=2826.2；,v5=2826.25-0.8=14130.2.,所以f(5)=14130.2.,例1已知一个5次多项式为用秦九韶算法求f(5)的值.,练习：阅读下列程序，说明它解决的实际问题是什么？,INPUT“x=”；an=0y=0WHLEn=0,INPUT“ai=”；a,v=v*x+a,i=i-1,WEND,PRINTv,END,PRINT“i=”；i,小结,2.计算机的一个很重要的特点就是运算速度快，但评价算法好坏的一个重要标志是运算的次数，如果一个算法从理论上需要超出计算机允许范围内的运算次数，那么这样的算法就只能是一个理论算法.在多项式求值的各种算法中，秦九韶算法是一个优秀算法.,1.秦九韶算法计算多项式的值及程序设计.,布置作业：P45练习：2.P48习题1.3A组：2.,1.3.3K进制化十进制,1.简述辗转相除法和更相减损术的用途及内容.,2、秦九韶算法的用途及内容.,将这些算法转化为程序，就可以由计算机来完成相关运算.,复习,进位制的概念,进位制是为了计数和运算方便而约定的记数系统.,约定满二进一，就是二进制；,满十进一，就是十进制；,七天为一周，就是七进制；,十二个月为一年，就是十二进制；,六十秒为一分钟，六十分钟为一个小时，就是六十进制；等等.,一般地，“满几进一”就是几进制.,思考1:十进制使用09十个数字，那么二进制、五进制、七进制分别使用哪些数字？,在十进制中10表示十，在二进制中10表示2.一般地，若k是一个大于1的整数，则以k为基数的k进制数可以表示为一串数字连写在一起的形式：anan-1a1a0(k).,“满K进一”就是K进制，其中k称为k进制的基数.那么k是一个什么范围内的数？,与十进制类似，其它的进位制也可以按照位置原则计数.,思考2：其中各个数位上的数字an，an-1，a1，a0的取值范围如何？,例如:十进制数3721表示的数可以写成：,110011（2）=125+124+023+022+121+120=51,5671（8）=583+682+781+180=3001.,例1：把二进制数110011（2）化为十进制数.,练习：把八进制数5671（8）化为十进制数.,3103+7102+2101+1100.,探究:如何将k进制数anan-1a1a0(k)写成各数位上的数字与基数k的幂的乘积之和的形式？,讨论:在二进制中，0+0，0+1，1+0，1+1的值分别是多少？,anan-1a1a0(k)=ankn+an-1kn-1+a1k1+a0k0,例2:二进制数110011（3）化为十进制数是什么数？,110011（3）,讨论:anan-1a1a0(2)中ai化为十进制数是什么数？,=135+134+033+032+131+130,=243+81+3+1,=328.,ai2i-1,练习：将下列各进制数化为十进制数.（1）10304（4）；（2）4321（5）.,10304（4）=144+342+440=308.,4321（5）=453+352+251+150=586.,探究：如何改进上述算法，把其他进位制化为十进制数？请举例说明.,例3:设计一个算法，把2进制数a（共有n位）化为十进制数b，并转化成程序框图，写出程序.,第二步，令b=0，i=1.,第四步，判断in是否成立.若是，则执行第五步；否则，返回第三步.,第一步，输入a，2和n的值.,第三步，b=b+ai2i-1，i=i+1.,第五步，输出b的值.,练习:设计一个算法，把k进制数a（共有n位）化为十进制数b.,第二步，令b=0，i=1.,第四步，判断in是否成立.若是，则执行第五步；否则，返回第三步.,第一步，输入a，k和n的值.,第三步，b=b+aiki-1，i=i+1.,第五步，输出b的值.,程序框图,INPUT“a，k，n=”;a,k,n,b=0,i=1,t=aMOD10,DO,b=b+t*k（i-1）,a=a10,t=aMOD10,i=i+1,LOOPUNTILin,PRINTb,END,例4：已知20a1（2）=b10（3）,求数字a，b的值.,所以2a+17=9b+3，即9b-2a=14.,20a1（2）=223+a2+1=2a+17.,b10（3）=b32+13=9b+3.,故a=2，b=2.,1、k进制数使用0（k-1）共k个数字，但左侧第一个数位上的数字（首位数字）不为0.,小结,布置作业：P48习题1.3B组：1.,1.3.4十进制化K进制,1、“满几进一”就是几进制.,2、k进制使用0，1，k-1这k个数字.,3、k进制数化为十进制数的一般算式:,anan-1a1a0(k)=ankn+an-1kn-1+a1k1+a0k0,复习,4、利用k进制数化十进制数的一般算式，可以构造算法，设计程序，通过计算机就能把任何一个k进制数化为十进制数.,练习:把二进制数100101（2）化为十进制数.,100101（2）=25+22+1=37.,讨论:怎样把十进制数89化为二进制数？,例1:把十进制数89化为二进制数.,观察下面的算式你有什么发现吗？,89=2（2（2（2（22+1）+1）+0）+0）+1,=126+025+124+123+022+021+120,=1011001（2）.,根据二进制“满二进一”的原则，可以用2连续去除89或所得商，然后取余数.,例1:把十进制数89化为二进制数.,上述化十进制数为二进制数的算法叫做除2取余法.,练习:把十进制数196化为五进制数.,除二取余法也可以推广为把十进制数化为k进制数的算法，称为除k取余法.,196=1241（5）,若十进制数a除以k所得的商是q0，余数是r0，即a=kq0+r0；q0除以k所得的商是q1，余数是r1，即q0=kq1+r1；qn-1除以k所得的商是0，余