《离散数学课件-第2章-4.ppt》由会员分享，可在线阅读，更多相关《离散数学课件-第2章-4.ppt（58页珍藏版）》请在三一办公上搜索。
1、2023/11/16,1,1,离散数学Discrete Mathematics,汪荣贵 教授合肥工业大学软件学院专用课件2010.03,2023/11/16,2,第二章 算法基础,2023/11/16,3,2.1 Algorithms算法2.2 Complexity of Algorithms算法的复杂性2.3 The Integers and Division整数和除法2.4 Integers and Algorithm整数和算法2.5 Applications of Number Theory数论的应用2.6 Matrices矩阵2.7 Recursion 递归,学习内容,2023/11/
2、16,4,The Euclidean Of Algorithms 欧几里德算法Representations Of Integers 整数表示Algorithms For Integers Operations整数运算算法,整数和除法,2023/11/16,5,上一节中的用整数的素因子分解求两个整数最大公约数的算法效率不高 古希腊数学家欧几里德，在他的书Elements中记载了效率更高的方法,欧几里德算法,2023/11/16,6,欧几里德算法求解gcd（91，287）用两数中的小者91去除两数中的大者287287=913+1491和287的任何公约数必定是287-913=14的因数91和14
3、的任何公约数也必定是287=913+14的因数287和91的最大公约数和91与14的最大公约数相同 求gcd（91，287）的问题已被化简为 gcd（91，14）的问题,欧几里德算法,2023/11/16,7,欧几里德算法,Let a=bq+r,where a,b,q,r are integers.Then gcd(a,b)=gcd(b,r).,引理1 令a=bq+r,其中a，b，q，r为整数，则gcd（a，b）=gcd（b，r）.,2023/11/16,8,例 用欧几里德算法求414和622的最大公约数解 662=4141+248 414=2481+166 248=1661+82 66=82
4、2+2因此，gcd（414，662）=2,欧几里德算法,2023/11/16,9,欧几里德算法伪码 Procedure gcd（a，b：正整数）x：=a y：=b While y0 Begin r：=x mod y x：=y y：=r end gcd(a,b)是x时间复杂性O(logb),2023/11/16,10,x和y的初值分别是a和b。在过程的每一步都是x用y代替，而y用x mod y代替，x mod y即是x被y除的余数。只要y0，这个过程就重复下去。当y=0时算法终止，此时x的值，也就是这一过程中最后一个非零余数，即为a和b的最大公约数。,欧几里德算法,2023/11/16,11,I
5、t follows from Lemma 1 that gcd(a,b)=gcd(r0,r1)=gcd(r1,r2)=gcd(rn-2,rn-1)=gcd(rn-1,rn)=gcd(rn,0)=rn,Suppose that a and b are positive integers with ab.Let r0=a and r1=b.r0=r1q1+r2 0r2r1,r1=r2q2+r3 0r3r2,rn-2=rn-1qn-1+rn 0rn-1rn,rn-1=rnqn.,2023/11/16,12,ALGORITHM 1 The Euclidean Algorithm.Procedure g
6、cd(a,b:positive integers)x:=ay:=bwhile y0begin r:=x mod y x:=y y:=rend gcd(a,b)is x,欧几里德算法,2023/11/16,13,GCD(22,8),GCD(8,6),GCD(6,2),GCD(2,0),2,递推,递推,递推,递推,回归,回归,回归,回归,结果为GCD(22,8)=2,例：GCD(22,8)=GCD(8,6)=GCD(6,2)=GCD(2,0)=2;,2023/11/16,14,The Euclidean Of Algorithms 欧几里德算法Representations Of Integers
7、 整数表示Algorithms For Integers Operations整数运算算法,整数和除法,2023/11/16,15,基本概念二进制转为十进制十六进制八进制十进制转二进制一般进制,整数表示,2023/11/16,16,生活中其实很多地方的计数方法都多少有点不同进制的影子。我们最常用的10进制，起源于人有10个指头。至于二进制没有袜子称为0只袜子，有一只袜子称为1只袜子，但若有两袜子，则我们常说的是：1双袜子。还有：七进制，比如星期。十六进制，比如小时或“一打”，六十进制，比如分钟或角度,基本概念,2023/11/16,17,定理1 令b为大于1的正整数。那么如果n是个正整数，就可
8、以唯一地表示为下面的形式:n=akbk+ak-1bk-1+a1b+a0 其中k是个非负整数，a0，a1ak是小于b的非负整数，ak0Theorem 1 Let b be a positive integer greater than 1.Then if n is a positive integer,it can be expressed uniquely in the form n=akbk+ak-1bk-1+a1b+a0,where k is a nonnegative integer,a0,a1,ak are nonnegative integers less than b,and ak
9、0.,基本概念,2023/11/16,18,2进制，用两个阿拉伯数字：0、1；8进制，用八个阿拉伯数字：0、1、2、3、4、5、6、7；10进制，用十个阿拉伯数字：0到9；16进制，用十六个阿拉伯数字等等,基本概念,2023/11/16,19,数据在计算机中的表示最终以二进制的形式存在二进制数表示数码很长：比如int 类型占用4个字节，32位。比如100，用int类型的二进制数表达将是：0000 0000 0000 0000 0110 0100 面对这么长的数进行思考或操作，非常麻烦 用16进制或8进制可以解决这个问题。因为，进制越大，数的表达长度也就越短。为什么偏偏是16或8进制，而不其它的
10、，诸如9或20进制呢？,2023/11/16,20,基本概念二进制转为十进制十六进制八进制十进制转二进制一般进制,整数表示,2023/11/16,21,2、8、16，分别是2的1次方，3次方，4次方。这一点使得三种进制之间可以非常直接地互相转换。8进制或16进制缩短了二进制数，但保持了二进制数的表达特点。,二进制转十进制,2023/11/16,22,二进制数第0位的权值是2的0次方，第1位的权值是2的1次方所以，设有一个二进制数：0110 0100，转换为10进制为：下面是竖式：0110 0100 换算成 十进制第0位 0*20=0第1位 0*21=0第2位 1*22=4第3位 0*23=0第
11、4位 0*24=0第5位 1*25=32第6位 1*26=64第7位 0*27=0-100,2023/11/16,23,用横式计算为：0*20+0*21+1*22+1*23+0*24+1*25+1*26+0*27=1000乘以多少都是0，所以我们也可以直接跳过值为0的位：1*22+1*23+1*25+1*26=100,二进制转十进制,2023/11/16,24,例 以(101011111)2为二进制张开的整数，其十进制展开是什么?解(101011111)2=28+26+24+23+22+2+1=351,二进制转十进制,2023/11/16,25,基本概念二进制转为十进制十六进制八进制十进制转二
12、进制一般进制,整数表示,2023/11/16,26,16进制就是逢16进1，但我们只有0到9这十个数字，所以我们用A，B，C，D，E，F这五个字母来分别表示10，11，12，13，14，15。字母不区分大小写。,十六进制,2023/11/16,27,十六进制数的第0位的权值为16的0次方，第1位的权值为16的1次方，第2位的权值为16的2次方所以，在第N（N从0开始）位上，如果是数 X（X 大于等于0，并且X小于等于 15，即：F）表示的大小为 X*16的N次方。,十六进制,2023/11/16,28,一个十六进数 2AF5,那么如何换算成10进制呢？用竖式计算：2AF5换算成10进制:第0位
13、：5*160=5第1位：F*161=240第2位：A*162=2560第3位：2*163=8192-10997,十六进制,2023/11/16,29,直接计算就是：5*160+F*161+A*162+2*163=10997(别忘了，在上面的计算中，A表示10，而F表示15)现在可以看出，所有进制换算成10进制，关键在于各自的权值不同。如果不使用特殊的书写形式，16进制数也会和10进制相混。C，C+规定，16进制数必须以 0 x开头。如：0 xff,0 xFF,0X102A,十六进制,2023/11/16,30,例 十六进制展开(2AE0B)16的十进制展开是什么?(2AE0B)16=2 164
14、+10163+14162+016+11=(175627)10,十六进制,2023/11/16,31,基本概念二进制转为十进制十六进制八进制十进制转二进制一般进制,整数表示,2023/11/16,32,八进制就是逢8进1。八进制数采用 07这八数来表达一个数。八进制数第0位的权值为8的0次方，第1位权值为8的1次方，第2位权值为8的2次方,八进制,2023/11/16,33,所以，设有一个八进制数：1507，转换为十进制为：用竖式表示：1507换算成十进制。第0位 7*80=7第1位 0*81=0 第2位 5*82=320 第3位 1*83=512-839同样，我们也可以用横式直接计算：7*80
15、+0*81+5*82+1*83=839结果是，八进制数 1507 转换成十进制数为 839,2023/11/16,34,基本概念二进制转为十进制十六进制八进制十进制转二进制一般进制,整数表示,2023/11/16,35,10进制数转换成二进制数，一个连续除2的过程：把要转换的数，除以2，得到商和余数，将商继续除以2，直到商为0。最后,将所有余数倒序排列，得到数就是转换结果。,十进制转二进制,2023/11/16,36,我们结合例子来说明。比如要转换6为二进制数。“把要转换的数，除以2，得到商和余数”。要转换的数是6，6 2，得到商是3，余数是0。“将商继续除以2,直到商为0”现在商是3，还不是
16、0，所以继续除以2。那就：3 2,得到商是1,余数是1。“将商继续除以2，直到商为0”现在商是1，还不是0，所以继续除以2。那就：1 2,得到商是0，余数是1（“将商继续除以2，直到商为0最后将所有余数倒序排列”)现在商已经是0。,2023/11/16,37,我们三次计算依次得到余数分别是：0、1、1，将所有余数倒序排列，那就是：110了！6转换成二进制，结果是110。,十进制转二进制,2023/11/16,38,所更常见的换算过程是使用下图的连除：,2023/11/16,39,基本概念二进制转为十进制十六进制八进制十进制转二进制一般进制,整数表示,2023/11/16,40,构造整数n的基数
17、b展开的算法首先，用b除n得到商和余数，即 n=bq0+a0，0a0 b余数a0就是n的基数b展开的最右边一位数字下一步用b除q0得q0=bq1+a1 a1是n的基数b 展开中右数第二数字继续这一过程，不断用b除商并以余数为新的基数b数字，直到商为0时终止,一般进制,2023/11/16,41,例 求(12345)10的基数8展开解 首先用8除12345，得 12345=81543+1 相继用8除商，得 1543=8192+7 192=824+0 24=83+0 3=80+3(2345)10=(30071)8,一般进制,2023/11/16,42,整数n的基数b展开伪码Procedure ba
18、se b expansion（n：正整数）q：=n k：=0 While q0 Begin ak：=q mod b q：=q/b k：=k+1 end n的基数b展开是(ak-1a1a0)b,一般进制,2023/11/16,43,The Euclidean Of Algorithms 欧几里德算法Representations Of Integers 整数表示Algorithms For Integers Operations整数运算算法,整数和除法,2023/11/16,44,整数运算方法 1 1 1 1 1 0 1 0 1 1 1 1 0 0 1(1110)2(1011)2相加,整数运算算
19、法,2023/11/16,45,a=（an-1an-2a1a0）2 与b=（bn-1bn-2b1b0）2两个二进制符号表示的整数相加方法：首先把他们最右边的数字相加a0+b0=c0*2+s0，其中：s0是a+b的二进制展开中最右边的一位数字，c0是进位,整数运算算法,2023/11/16,46,然后，下一对字位及进位相加：a1+b1=c1*2+s1 其中：s1是a+b的二进制展开中下一位（从右数）数字，c0是进位 继续这一过程，把两个二进制展开中对应的字位及进位相加，给出a+b的二进制展开中从右数的下一位数字。,整数运算算法,2023/11/16,47,最后：把an-1,bn-1和cn-1相加
20、得cn-1*2+sn-1.a+b的首位数字是sn=cn-1a+b=(snsn-1s0)2,整数运算算法,2023/11/16,48,例 把a=(1110)2和b=(1011)2相加解 a0+b0=0+1=02+1 c0=0 而s0=1 a1+b1+c0=1+1+0=12+0 c1=1 而s1=0 a2+b2+c1=1+0+1=12+0 c2=1 而s2=0 a3+b3+c2=1+1+1=12+1 c3=1 且 s3=1 s4=c3=1 s=a+b=(11001)2,整数运算算法,2023/11/16,49,整数相加伪码Procedure add(a,b:int)a和b的二进制展开分别是（an-
21、1an-2a1a0）2和(bn-1bn-2b1b0)2 c:=0 for j:=0 to n-1 begin d:=(aj+bj+c)/2 sj=aj+bj+c-2d c:=d end sn=c和的二进制展开是(snsn-1s0)2,2023/11/16,50,一步一步把（10111）2（11010）2相加解：1 1 1 1 0 1 1 1 1 1 0 1 0 1 1 0 0 0 1,2023/11/16,51,整数运算算法,考虑两个n位整数的乘法，根据乘法分配律：,2023/11/16,52,注意到：当bj=1时，abj=a，当bj=0时，abj=0；每当用2乘以一项的时候，就等于把这一项的
22、二进制展开向左移一位，并在尾部加一个零；可以把abj的二进制向左移j位，并在尾部加上j个0来计算（abj）2j；最后，把n个整数abj2j相加，得到ab。,2023/11/16,53,例7 求a=（110）2和b=(101)2的乘积解：ab020=（110）2*1*20=(110)2 ab121=（110）2*0*21=(0000)2及.ab222=(110)2*1*22=(11000)2用上面算法把（110）2，（0000）2，（11000）2相加，得到ab=（11110）2,2023/11/16,54,1 1 0 1 0 1 1 1 0 0 0 0 1 1 0 1 1 1 1 0,计算过程
23、：,2023/11/16,55,整数乘法伪码Procedure multiply(a,b:int)a和b的二进制展开分别是（an-1an-2a1a0）2和(bn-1bn-2b1b0)2 for j:=0 to n-1 begin if bj:=1 then cj:=a移j位 else cj:=0 endc0,c1,cn-1是部分积 p:=0 for j:=0 to n-1 p:=p+cjp是ab的值,2023/11/16,56,例 将（1110）和（1010）相乘 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 0 0 1 0 1,2023/11/16,57,自己分析二进制加法和乘法算法的计算复杂度。（见教材相关的部分）,整数运算算法,2023/11/16,58,本节内容到此结束,谢谢大家！,
