13算法案例.ppt

《13算法案例.ppt》由会员分享，可在线阅读，更多相关《13算法案例.ppt（66页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1.3 1.3 算法案例算法案例1.3.4 1.3.4 十进制化十进制化K K进制进制1.3.1 1.3.1 辗转相除法和更相减损术辗转相除法和更相减损术1.3.2 1.3.2 秦九韶算法秦九韶算法1.3.3 K1.3.3 K进制化十进制进制化十进制1.3 1.3 算法案例算法案例1.3.1 1.3.1 辗转相除法辗转相除法和更相减损术和更相减损术复习复习1.1.研究一个实际问题的算法，主要从哪几方面展开？研究一个实际问题的算法，主要从哪几方面展开？2.2.在程序框图中算法的基本逻辑结构有哪几种？在程序框图中算法的基本逻辑结构有哪几种？3.3.在程序设计中基本的算法语句有哪几种？在程序设计中基

2、本的算法语句有哪几种？算法步骤、程序框图和编写程序算法步骤、程序框图和编写程序三方面展开三方面展开.顺序结构、条件结构、循环结构顺序结构、条件结构、循环结构输入语句、输出语句、赋值语句、条件语句、循环语句输入语句、输出语句、赋值语句、条件语句、循环语句探究一,辗转相除法思考思考1:在小学中我们是如何求出两个正整数在小学中我们是如何求出两个正整数的最大公约数的呢的最大公约数的呢?算法案例算法案例之求最大公约数之求最大公约数求以下几组正整数的最大公约数。(注：若整数m和n满足n整除m，则（m,n）=n。用（m,n）来表示m和n的最大公约数。)（1）（18，30）（2）（24，16）（3）（63，6

3、3）（4）（72，8）（5）（301，133）解：2 1 8 2 4 用公有质因数2除，3 9 1 2 用公有质因数3除，3 4 3和4互质不除了。得：18和24最大公约数是：236 例、求18与24的最大公约数：6；8；63；8；7；短除法短除法想一想，如何求8251与6105的最大公约数？思考思考2:2:对于对于82518251与与61056105这两个数，它们这两个数，它们的最大公的最大公约数是多少？你是怎样得到的？约数是多少？你是怎样得到的？由于它们公有的质因数较大，利用上述方法求最由于它们公有的质因数较大，利用上述方法求最大公约数就比较困难大公约数就比较困难.有没有其它的方法可以较简

4、单有没有其它的方法可以较简单的找出它们的最大公约数呢？的找出它们的最大公约数呢？思考思考3 3：注意到：注意到8251=61058251=61051+21461+2146，那么，那么82518251与与61056105这两个数的公约数和这两个数的公约数和61056105与与21462146的公约数有什么的公约数有什么关系？关系？我们发现我们发现6105=21466105=21462+18132+1813，同理，同理，61056105与与21462146的公约数和的公约数和21462146与与18131813的公约数相等的公约数相等.思考思考4 4：重复上述操作，你能得到：重复上述操作，你能得到

5、82518251与与61056105这这两个数的最大公约数吗？两个数的最大公约数吗？2146=18132146=18131+3331+333，148=37148=374+0.4+0.333=148333=1482+372+37，1813=3331813=3335+1485+148，8251=61058251=61051+21461+2146，6105=21466105=21462+18132+1813，定义定义:所谓的辗转相除法,就是对于给定的两个数,用较大的数除以较小的数,若余数不为零,则将余数和较小的数构成新的数对,继续上面的除法,直到大数被小数除尽,则这是较小的数就是原来两个数的最大公约

6、数第一步，给定两个正整数第一步，给定两个正整数m m，n(mn).n(mn).第二步，计算第二步，计算m m除以除以n n所得的余数所得的余数r.r.第三步，第三步，m=nm=n，n=r.n=r.第四步，若第四步，若r=0r=0，则，则m m，n n的最大公约数等于的最大公约数等于m m；否则，返回第二步否则，返回第二步.思考思考5:5:你能把辗转相除法编成一个计算机程序吗？你能把辗转相除法编成一个计算机程序吗？程序框图程序框图开始开始输入输入m m，n n求求m m除以除以n n的余数的余数r rm=nm=nn=rn=rr=0r=0？是是输出输出m m结束结束否否INPUT mINPUT m

7、，n nDODOr=m MOD nr=m MOD nm=nm=nn=rn=rLOOP UNTIL r=0LOOP UNTIL r=0PRINT mPRINT mENDEND 思考思考6:6:如果用当型循环结构构造算法，则用辗如果用当型循环结构构造算法，则用辗转相除法求两个正整数转相除法求两个正整数m m、n n的最大公约数的程序框的最大公约数的程序框图和程序分别如何表示？图和程序分别如何表示？开始开始输入输入m m，n n求求m m除以除以n n的余数的余数r rm=nm=nr r00？否否输出输出m m结束结束是是n=rn=rINPUT mINPUT m，n nWHILE r0WHILE r

8、0r=m MOD nr=m MOD nm=nm=nn=rn=rWENDWENDPRINT mPRINT mENDEND练习：用辗转相除法求下列两数的最大公约数：（1）（225，135）（2）（98，196）（3）（72，168）（4）（153，119）45982417二、更相减损术二、更相减损术 九章算术是中国古代的数学专著，其中的九章算术是中国古代的数学专著，其中的“更相减损术更相减损术”也可以用来求两个数的最大公约数，也可以用来求两个数的最大公约数，即即“可半者半之，不可半者，副置分母、子之数，可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也以少减多，更相减损，求其等也

9、.以等数约之以等数约之.”意思是：意思是：第一步：任意给定两个正整数，判断它们是否第一步：任意给定两个正整数，判断它们是否都是偶数都是偶数.若是，用若是，用2约简；若不是，执行第二步约简；若不是，执行第二步.第二步：以较大的数减去较小的数，接着把差第二步：以较大的数减去较小的数，接着把差与较小的数比较，并以大数减小数与较小的数比较，并以大数减小数.继续这个操作，继续这个操作，直到所得的数相等为止，则这个等数或这个数与约直到所得的数相等为止，则这个等数或这个数与约简的数的乘积就是所求的最大公约数简的数的乘积就是所求的最大公约数.例例1 1：用更相减损术求：用更相减损术求9898与与6363的最大

10、公约数的最大公约数.98-63=3598-63=35，14-7=7.14-7=7.21-7=1421-7=14，28-7=2128-7=21，35-28=735-28=7，63-35=2863-35=28，因为因为63不是偶数，所以不是偶数，所以所以最大公约数是所以最大公约数是7.例例2 2 分别用辗转相除法和更相减损术求分别用辗转相除法和更相减损术求168168与与9393的最大公约数的最大公约数.168=93168=931+751+75，93=7593=751+181+18，75=1875=184+34+3，18=318=36.6.辗转相除法：辗转相除法：更相减损术更相减损术:168-93

11、=75 168-93=75，93-75=18 93-75=18，75-18=57 75-18=57，57-18=39 57-18=39，39-18=21 39-18=21，21-18=3 21-18=3，18-3=15 18-3=15，15-3=12 15-3=12，12-3=9 12-3=9，9-3=6 9-3=6，6-3=3.6-3=3.例例4 4 求求325325，130130，270270三个数的最大公约数三个数的最大公约数.因为因为325=130325=1302+652+65，130=65130=652 2，所以，所以325325与与130130的最大公约数是的最大公约数是65.65

12、.因为因为270=65270=654+104+10，65=1065=106+56+5，10=510=52 2，所，所以以6565与与270270最大公约数是最大公约数是5.5.故故325325，130130，270270三个数的最大公约数是三个数的最大公约数是5.5.练习练习:用更相减损术求两个正整数用更相减损术求两个正整数m m，n n的最大公的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？如何设计？第一步，给定两个正整数第一步，给定两个正整数m m，n(mn).n(mn).第二步，计算第二步，计算m-nm-n所得的差所得的差k.

13、k.第三步，比较第三步，比较n n与与k k的大小，其中大者用的大小，其中大者用m m表示，表示，小者用小者用n n表示表示.第四步，若第四步，若m=nm=n，则，则m m，n n的最大公约数等于的最大公约数等于m m；否则，返回第二步否则，返回第二步.讨论讨论:该算法的程序框图如何表示？该算法的程序框图如何表示？开始开始输入输入m m，n nnknk？m=nm=n是是输出输出m m结束结束mnmn？k=m-nk=m-n是是否否n=kn=km=km=k否否 讨论讨论:该程该程序框图对应的程序框图对应的程序如何表述？序如何表述？INPUT mINPUT m，n nWHILE mWHILE mn

14、nk=m-nk=m-nIF nk THENIF nk THENm=nm=nn=kn=kELSEELSEm=km=kEND IFEND IFWENDWENDPRINT mPRINT mENDEND开始开始输入输入m m，n nnknk？m=nm=n是是输出输出m m结束结束mnmn？k=m-nk=m-n是是否否n=kn=km=km=k否否布置作业：布置作业：P45P45练习：练习：1.1.P48P48习题习题1.3A1.3A组：组：1.1.1.3.2 1.3.2 秦九韶算法秦九韶算法 1 1、什么是辗转相除法和更相减损术？、什么是辗转相除法和更相减损术？2 2、辗转相除法和更相减损术，是求两个正

15、整、辗转相除法和更相减损术，是求两个正整数的最大公约数的优秀算法，我们将算法转化为程数的最大公约数的优秀算法，我们将算法转化为程序后，就可以由计算机来执行运算，实现了古代数序后，就可以由计算机来执行运算，实现了古代数学与现代信息技术的完美结合学与现代信息技术的完美结合.复习复习探究三、秦九昭算法思考思考1,在初中在初中,我们是如何求一个多项式的我们是如何求一个多项式的值的值的?思考思考2,已知一个已知一个n 次多项式次多项式f(x)=anxn+an-1xn-1+a1x+a0当当x=x0时，除时，除了用代入法求解外是否还有更好的方法呢了用代入法求解外是否还有更好的方法呢？秦九韶算法秦九韶算法的基

16、本思想的基本思想 思考思考1:1:对于多项式对于多项式f(x)=xf(x)=x5 5+x+x4 4+x+x3 3+x+x2 2+x+1+x+1，求，求f(5)f(5)的值的值.4+3+2+1=104+3+2+1=10次乘法运算，次乘法运算，5 5次加法运算次加法运算.分析：把分析：把5 5代入多项式，若先计算各项的值，代入多项式，若先计算各项的值，然后再相加，那么一共要做：然后再相加，那么一共要做：思考思考2:2:另一种做法是先计算另一种做法是先计算x x2 2的值，然后依的值，然后依次计算次计算x x2 2x x，(x(x2 2x)x)x x，(x(x2 2x)x)x)x)x x的的值，这样

17、每次都可以利用上一次计算的结果，这值，这样每次都可以利用上一次计算的结果，这时一共做了：时一共做了：4 4次乘法运算，次乘法运算，5 5次加法运算次加法运算.思考思考3:3:有没有更有效的算法呢？利用后一种算有没有更有效的算法呢？利用后一种算法求多项式法求多项式f(x)=af(x)=an nx xn n+a+an-1n-1x xn-1n-1+a+a1 1x+ax+a0 0的值，这的值，这个多项式应写成哪种形式？个多项式应写成哪种形式？f(x)=af(x)=an nx xn n+a+an-1n-1x xn-1n-1+a+a1 1x+ax+a0 0=(a=(an nx xn-1n-1+a+an-1

18、n-1x xn-2n-2+a+a2 2x+ax+a1 1)x+a)x+a0 0=(a=(an nx xn-2n-2+a+an-1n-1x xn-3n-3+a+a2 2)x+a)x+a1 1)x+a)x+a0 0 =(=(a(an nx+ax+an-1n-1)x+a)x+an-2n-2)x+)x+a+a1 1)x+a)x+a0 0.这就是我国南宋时期数学家秦九韶在他的著作这就是我国南宋时期数学家秦九韶在他的著作数书九章中提出的算法数书九章中提出的算法.思考思考4:4:对于对于f(x)=(f(x)=(a(an nx+ax+an-1n-1)x+a)x+an-2n-2)x+)x+a+a1 1)x+a)

19、x+a0 0，由内向外逐层计算一次多项式的值，其算法步骤如何？由内向外逐层计算一次多项式的值，其算法步骤如何？第一步，计算第一步，计算v v1 1=a=an nx+ax+an-1n-1.第二步，计算第二步，计算v v2 2=v=v1 1x+ax+an-2n-2.第三步，计算第三步，计算v v3 3=v=v2 2x+ax+an-3n-3.第第n n步，计算步，计算v vn n=v=vn-1n-1x+ax+a0 0.上述方法称为秦九韶算法上述方法称为秦九韶算法.思考思考5:5:在秦九韶算法中，记在秦九韶算法中，记v v0 0=a=an n，那么第，那么第k k步的步的算式是什么？算式是什么？v v

20、k k=v=vk-1k-1x+ax+an-kn-k(k=1(k=1，2 2，n)n)解：解：f(x)=(4x+2)x+3.5)x-2.6)x+1.7)x-0.8.f(x)=(4x+2)x+3.5)x-2.6)x+1.7)x-0.8.v v1 1=4=45+2=225+2=22；v v2 2=22=225+3.5=113.55+3.5=113.5；v v3 3=113.5=113.55-2.6=564.95-2.6=564.9；v v4 4=564.9=564.95+1.7=2826.25+1.7=2826.2；v v5 5=2826.2=2826.25-0.8=14130.2.5-0.8=14

21、130.2.所以所以f(5)=14130.2.f(5)=14130.2.例例1 1 已知一个已知一个5 5次多项式为次多项式为 用秦九韶算法求用秦九韶算法求f(5)f(5)的值的值.练习：阅读下列程序，说明它解决的实际问题是什么？练习：阅读下列程序，说明它解决的实际问题是什么？INPUT INPUT“x=x=”；a an=0n=0y=0y=0WHLE n5WHLE n=0WHILE i=0INPUT INPUT“ai=ai=”；a a v=v*x+a v=v*x+ai=i-1i=i-1 WEND WENDPRINT vPRINT vENDENDPRINT PRINT “i=i=”；i i小结小

22、结 2.2.计算机的一个很重要的特点就是运算速度快，计算机的一个很重要的特点就是运算速度快，但评价算法好坏的一个重要标志是运算的次数，如但评价算法好坏的一个重要标志是运算的次数，如果一个算法从理论上需要超出计算机允许范围内的果一个算法从理论上需要超出计算机允许范围内的运算次数，那么这样的算法就只能是一个理论算法运算次数，那么这样的算法就只能是一个理论算法.在多项式求值的各种算法中，秦九韶算法是一个优在多项式求值的各种算法中，秦九韶算法是一个优秀算法秀算法.1.1.秦九韶算法计算多项式的值及程序设计秦九韶算法计算多项式的值及程序设计.布置作业：布置作业：P45P45练习：练习：2.2.P48P4

23、8习题习题1.3A1.3A组：组：2.2.1.3.3 K1.3.3 K进制化十进制进制化十进制 1.1.简述辗转相除法和更相减损术的用途及内容简述辗转相除法和更相减损术的用途及内容.2、秦九韶算法的用途及内容、秦九韶算法的用途及内容.将这些算法转化为程序，就可以由计算机来完将这些算法转化为程序，就可以由计算机来完成相关运算成相关运算.复习复习进位制的概念进位制的概念 进位制是为了计数和运算方便而约定的记数系统进位制是为了计数和运算方便而约定的记数系统.约定满二进一，就是二进制；约定满二进一，就是二进制；满十进一，就是十进制；满十进一，就是十进制；七天为一周，就是七进制；七天为一周，就是七进制；

24、十二个月为一年，就是十二进制；十二个月为一年，就是十二进制；六十秒为一分钟，六十分钟为一个小时，就是六六十秒为一分钟，六十分钟为一个小时，就是六十进制；等等十进制；等等.一般地，一般地，“满几进一满几进一”就是就是几进制几进制.思考思考1:1:十进制使用十进制使用0 09 9十个数字，那么二进制、十个数字，那么二进制、五进制、七进制分别使用哪些数字？五进制、七进制分别使用哪些数字？在十进制中在十进制中1010表示十，在二进制中表示十，在二进制中1010表示表示2.2.一一般地，若般地，若k k是一个大于是一个大于1 1的整数，则以的整数，则以k k为基数的为基数的k k进制进制数可以表示为一串

25、数字连写在一起的形式：数可以表示为一串数字连写在一起的形式：a an na an-1n-1a a1 1a a0(k)0(k).“满满K K进一进一”就是就是K K进制进制，其中，其中k k称为称为k k进制的进制的基数基数.那么那么k k是一个什么范围内的数？是一个什么范围内的数？与十进制类似，其它的进位制也可以按照位置原与十进制类似，其它的进位制也可以按照位置原则计数则计数.思考思考2 2：其中各个数位上的数字：其中各个数位上的数字a an n，a an-1n-1，a a1 1，a a0 0的取值范围如何？的取值范围如何？例如例如:十进制数十进制数37213721表示的数可以写成：表示的数可

26、以写成：110011110011（2 2）=1=12 25 5+1+12 24 4+0+02 23 3+0+02 22 2+1+12 21 1+1+12 20 0 =51=51 56715671（8 8）=5=58 83 3+6+68 82 2+7+78 81 1+1+18 80 0=3001.=3001.例例1 1：把二进制数：把二进制数110011110011（2 2）化为十进制数化为十进制数.练习：把八进制数练习：把八进制数 5671 5671（8 8）化为十进制数化为十进制数.3 310103 3+7+710102 2+2+210101 1+1+110100 0.探究探究:如何将如何将

27、k k进制数进制数a an na an-1n-1a a1 1a a0(k)0(k)写成各数位写成各数位上的数字与基数上的数字与基数k k的幂的乘积之和的形式？的幂的乘积之和的形式？讨论讨论:在二进制中，在二进制中，0+00+0，0+10+1，1+01+0，1+11+1的值分的值分别是多少？别是多少？a an n a an-1n-1a a1 1a a0(k)0(k)=a=an nk kn n+a+an-1n-1k kn-1n-1+a+a1 1k k1 1+a+a0 0k k0 0 例例2:2:二进制数二进制数110011110011（3 3）化为十进制数是什么数？化为十进制数是什么数？11001

28、1110011（3 3）讨论讨论:an an-1a1a0(2)中a ai i化为十进制数是什么数？化为十进制数是什么数？=1=13 35 5+1+13 34 4+0+03 33 3+0+03 32 2+1+13 31 1+1+13 30 0=243+81+3+1=243+81+3+1=328.=328.a ai i2 2i-1i-1 练习：将下列各进制数化为十进制数练习：将下列各进制数化为十进制数.（1 1）1030410304（4 4）；（2 2）43214321（5 5）.1030410304（4 4）=1=14 44 4+3+34 42 2+4+44 40 0=308.=308.4321

29、4321（5 5）=4=45 53 3+3+35 52 2+2+25 51 1+1+15 50 0=586.=586.探究：如何改进上述算法，把其他进位制化为十探究：如何改进上述算法，把其他进位制化为十进制数？请举例说明进制数？请举例说明.例例3:3:设计一个算法，把设计一个算法，把2 2进制数进制数a a（共有（共有n n位）化位）化为十进制数为十进制数b b，并转化成程序框图，写出程序，并转化成程序框图，写出程序.第二步，令第二步，令b=0b=0，i=1.i=1.第四步，判断第四步，判断in in 是否成立是否成立.若是，则执行第五若是，则执行第五步；否则，返回第三步步；否则，返回第三步.

30、第一步，输入第一步，输入a a，2 2和和n n的值的值.第三步，第三步，b=b+ab=b+ai i2 2i-1i-1，i=i+1.i=i+1.第五步，输出第五步，输出b b的值的值.练习练习:设计一个算法，把设计一个算法，把k k进制数进制数a a（共有（共有n n位）化位）化为十进制数为十进制数b.b.第二步，令第二步，令b=0b=0，i=1.i=1.第四步，判断第四步，判断in in 是否成立是否成立.若是，则执行第五步；若是，则执行第五步；否则，返回第三步否则，返回第三步.第一步，输入第一步，输入a a，k k和和n n的值的值.第三步，第三步，b=b+ab=b+ai ik ki-1i

31、-1，i=i+1.i=i+1.第五步，输出第五步，输出b b的值的值.开始开始输入输入a a，k k，n nb=0b=0i=1i=1把把a a的右数第的右数第i i位数字赋给位数字赋给t tb=b+tb=b+tk ki-1i-1i=i+1i=i+1in?in?结束结束是是输出输出b b否否程序框图程序框图INPUT INPUT“a a，k k，n=n=”;a,k,n;a,k,nb=0b=0i=1i=1t=a MOD 10t=a MOD 10DODOb=b+t*kb=b+t*k（i-1i-1）a=a10a=a10t=a MOD 10t=a MOD 10i=i+1i=i+1LOOP UNTIL i

32、nLOOP UNTIL inPRINT bPRINT bENDEND开始开始输入输入a a，k k，n nb=0b=0i=1i=1把把a a的右数第的右数第i i位数字赋给位数字赋给t tb=b+tb=b+tk ki-1i-1i=i+1i=i+1in?in?结束结束是是输出输出b b否否 例例4 4：已知：已知20a120a1（2 2）=b10=b10（3 3）,求数字求数字a a，b b的值的值.所以所以2a+17=9b+32a+17=9b+3，即，即9b-2a=14.9b-2a=14.20a120a1（2 2）=2=22 23 3+a+a2+1=2a+17.2+1=2a+17.b10b10

33、（3 3）=b=b3 32 2+1+13=9b+3.3=9b+3.故故a=2a=2，b=2.b=2.1 1、k k进制数使用进制数使用0 0（k-1k-1）共）共k k个数字，但左个数字，但左侧第一个数位上的数字（首位数字）不为侧第一个数位上的数字（首位数字）不为0.0.小结小结 2 2、用、用 表示表示k k进制数，其中进制数，其中k k称为基数，十进制数一般不标注基数称为基数，十进制数一般不标注基数.a an n a an-1n-1a a1 1a a0(k)0(k)3 3、把、把k k进制数化为十进制数的一般算式是：进制数化为十进制数的一般算式是：a an n a an-1n-1a a1

34、1a a0(k)0(k)=a=an nk kn n+a+an-1n-1k kn-1n-1+a+a1 1k k1 1+a+a0 0k k0 0布置作业：布置作业：P48P48习题习题1.3B1.3B组：组：1.1.1.3.4 1.3.4 十进制化十进制化K K进制进制1 1、“满几进一满几进一”就是几进制就是几进制.2 2、k k进制使用进制使用0 0，1 1，k-1k-1这这k k个数字个数字.3 3、k k进制数化为十进制数的一般算式进制数化为十进制数的一般算式:a an n a an-1n-1a a1 1a a0(k)0(k)=a=an nk kn n+a+an-1n-1k kn-1n-1

35、+a+a1 1k k1 1+a+a0 0k k0 0 复习复习4 4、利用、利用k k进制数化十进制数的一般算式，可以进制数化十进制数的一般算式，可以构造算法，设计程序，通过计算机就能把任何构造算法，设计程序，通过计算机就能把任何一个一个k k进制数化为十进制数进制数化为十进制数.练习练习:把二进制数把二进制数100101100101（2 2）化为十进制数化为十进制数.100101100101（2 2）=2=25 5+2+22 2+1=37.+1=37.讨论讨论:怎样把十进制数怎样把十进制数8989化为二进制数？化为二进制数？例例1:1:把十进制数把十进制数8989化为二进制数化为二进制数.观

36、察下面的算式你有什么发现吗？观察下面的算式你有什么发现吗？89=289=2（2 2（2 2（2 2（2 22+12+1）+1+1）+0+0）+0+0）+1+1=1=12 26 6+0+02 25 5+1+12 24 4+1+12 23 3+0+02 22 2+0+02 21 1+1+12 20 0=1011001=1011001（2 2）.根据二进制根据二进制“满二进一满二进一”的原则，可以用的原则，可以用2 2连续去连续去除除8989或所得商，然后取余数或所得商，然后取余数.2 21 12 22 22 25 50 02 211112 222222 244442 289891 10 00 01

37、 11 10 01 1余数余数例例1:1:把十进制数把十进制数8989化为二进制数化为二进制数.上述化十进上述化十进制数为二进制数制数为二进制数的算法叫做的算法叫做除除2 2取余法取余法.练习练习:把十进制数把十进制数196196化为五进制数化为五进制数.除二取余法也可以推广为把十进制数化为除二取余法也可以推广为把十进制数化为k k进制进制数的算法，称为数的算法，称为除除k k取余法取余法.0 05 51 15 57 75 539395 51961961 14 42 21 1余数余数196=1241196=1241（5 5）若十进制数若十进制数a a除以除以k k所得的商是所得的商是q q0

38、0，余数是，余数是r r0 0，即即a=ka=kq q0 0+r+r0 0；q q0 0除以除以k k所得的商是所得的商是q q1 1，余数是，余数是r r1 1，即即q q0 0=k=kq q1 1+r+r1 1；q qn-1n-1除以除以k k所得的商是所得的商是0 0，余数是，余数是r rn n，即即q qn-1n-1=r=rn n，那么十进制数那么十进制数a a化为化为k k进制数是：进制数是：a=ra=rn nr rn-1n-1r r1 1r r0(2)0(2)推广：怎样把十进制数转化为推广：怎样把十进制数转化为k k进制数？进制数？例例2:2:根据上面的分析，将十进制数根据上面的分

39、析，将十进制数a a化为二进化为二进制数的算法步骤如何设计？制数的算法步骤如何设计？第四步，若第四步，若q0q0，则，则a=qa=q，返回第二步；否则，返回第二步；否则，输出全部余数输出全部余数r r排列得到的二进制数排列得到的二进制数.第一步，输入十进制数第一步，输入十进制数a a的值的值.第二步，求出第二步，求出a a除以除以2 2所得的商所得的商q q，余数，余数r.r.第三步，把所得的余数依次从右到左排列第三步，把所得的余数依次从右到左排列.练习练习:设计一个程序，实现设计一个程序，实现“除除k k取余法取余法”（kNkN，2k92k9）.第四步，若第四步，若q0q0，则，则a=qa=

40、q，返回第二步；否则，返回第二步；否则，输出全部余数输出全部余数r r排列得到的排列得到的k k进制数进制数.第一步，输入十进制数第一步，输入十进制数a a和转化后的数的基数和转化后的数的基数k.k.第二步，求出第二步，求出a a除以除以k k所得的商所得的商q q，余数，余数r.r.第三步，把所得的余数依次从右到左排列第三步，把所得的余数依次从右到左排列.开始开始输入输入a a，k k求求a a除以除以k k的商的商q q求求a a除以除以k k的余数的余数r r把所得的余数依次从右到左排列把所得的余数依次从右到左排列a=qa=qq=0q=0？结束结束输出全部余数输出全部余数r r排排列得到

41、的列得到的k k进制数进制数是是否否程序框图程序框图INPUT aINPUT a，k kb=0b=0i=0i=0DODOq=akq=akr=a MOD kr=a MOD kb=b+r*10b=b+r*10i ii=i+1i=i+1a=qa=qLOOP UNTIL q=0LOOP UNTIL q=0PRINT bPRINT bENDEND把所得的余数依次从右到左排列把所得的余数依次从右到左排列 开始开始输入输入a a，k k求求a a除以除以k k的商的商q q求求a a除以除以k k的余数的余数r ra=qa=qq=0q=0？结束结束输出全部余数输出全部余数r r排排列得到的列得到的k k进制

42、数进制数是是否否 练习练习 将十进制数将十进制数258258分别转化为四进制数和六进制数分别转化为四进制数和六进制数.0 04 4 1 14 44 44 416164 464644 42582582 20 00 00 01 1余数余数0 06 61 16 67 76 643436 62582580 01 11 11 1余数余数258=10002258=10002（4 4）=1110=1110（6 6）练习练习 将五进制数将五进制数12341234（5 5）转化为七进制数转化为七进制数.12341234（5 5）=1=15 53 3+2+25 52 2+3+35+4=194.5+4=194.0

43、07 73 37 727277 71941945 56 63 3余数余数12341234（5 5）=365=365（7 7）小结小结 1 1、进位制的概念及转化方法、进位制的概念及转化方法.2 2、通过、通过k k进制数与十进制数的相互转化，实现计进制数与十进制数的相互转化，实现计算机操作算机操作.布置作业：布置作业：P45P45练习：练习：3.3.P48P48习题习题1.3A1.3A组：组：3 3，4.4.设两数为a、b(b1），则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)dc，b=nc=ycd，故a与b最大公约数成为cd，而非c，与前面结论矛盾】从而可知gcd(b,r)=c，继而gcd(a,b)=gcd(b,r）。证毕。