离散数学课件-第2章-4

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,1,离散数学,Discrete Mathematics,汪荣贵 教授,合肥工业大学软件学院专用课件,2010.03,11/28/2024,1,第二章 算法基础,11/28/2024,2,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,递归,学习内容,11/28/2024,3,The Euclidean Of,Algorithms,欧几里德算法,Representations Of Integers,整数表示,Algorithms For,Integers Operations,整数运算算法,整数和除法,11/28/2024,4,上一节中的用整数的素因子分解求两个整数最大公约数的算法效率不高,古希腊数学家欧几里德，在他的书,Elements,中记载了效率更高的方法,欧几里德算法,11/28/2024,5,欧几里德算法,求解,gcd,（,91,，,287,）,用两数中的小者,91,去除两数中的大者,287,287=913+14,91,和,287,的任何公约数必定是,287-913=14,的因数,91,和,14,的任何公约数也必定是,287=913+14,的因数,287,和,91,的最大公约数和,91,与,14,的最大公约数相同,求,gcd,（,91,，,287,）,的问题已被化简为,gcd,（,91,，,14,）,的问题,欧几里德算法,11/28/2024,6,欧几里德算法,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）.,11/28/2024,7,例,用欧几里德算法求,414,和,622,的最大公约数,解,662=4141+248,414=2481+166,248=1661+82,66=822+2,因此，,gcd,（,414,，,662,）,=2,欧几里德算法,11/28/2024,8,欧几里德算法伪码,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),11/28/2024,9,x和y的初值分别是a和b。在过程的每一步都是x用y代替，而y用x mod y代替，x mod y即是x被y除的余数。只要y0，这个过程就重复下去。当y=0时算法终止，此时x的值，也就是这一过程中最后一个非零余数，即为a和b的最大公约数。,欧几里德算法,11/28/2024,10,It follows from Lemma 1 that,gcd(,a,b,) = gcd(,r,0, r,1,) = gcd(,r,1, r,2,),= = gcd(,r,n,-2, r,n,-1,) = gcd(,r,n,-1, r,n,),= gcd(,r,n, 0,) =,r,n,Suppose that,a,and,b,are positive integers with,a,b,.,Let,r,0,=,a,and,r,1,=,b,.,r,0,= r,1,q,1,+ r,2,0r,2,r,1,r,1,= r,2,q,2,+ r,3,0r,3,r,2,r,n,-2,= r,n-1,q,n,-1,+ r,n,0r,n,-1,r,n,r,n-1,= r,n,q,n .,11/28/2024,11,ALGORITHM 1,The Euclidean Algorithm.,Procedure gcd (,a,b,: positive integers),x,:=,a,y,:=,b,while,y,0,begin,r,:=,x,mod,y,x,:=,y,y,:=,r,end,gcd(,a,b,) is,x,欧几里德算法,11/28/2024,12,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;,11/28/2024,13,The Euclidean Of,Algorithms,欧几里德算法,Representations Of Integers,整数表示,Algorithms For,Integers Operations,整数运算算法,整数和除法,11/28/2024,14,基本概念,二进制转为十进制,十六进制,八进制,十进制转二进制,一般进制,整数表示,11/28/2024,15,生活中其实很多地方的计数方法都多少有点不同进制的影子。,我们最常用的,10,进制，起源于人有,10,个指头。,至于二进制,没有袜子称为,0,只袜子，有一只袜子称为,1,只袜子，但若有两袜子，则我们常说的是：,1,双袜子。,还有：七进制，比如星期。十六进制，比如小时或“一打”，六十进制，比如分钟或角度,基本概念,11/28/2024,16,定理,1,令,b,为大于,1,的正整数。那么如果,n,是个正整数，就可以唯一地表示为下面的形式,:,n=a,k,b,k,+a,k-1,b,k-1,+a,1,b+a,0,其中,k,是个非负整数，,a,0,，,a,1,a,k,是小于,b,的非负整数，,a,k,0,Theorem 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=,a,k,b,k,+ a,k-1,b,k-1,+, +,a,1,b +a,0,where,k,is a nonnegative integer,a,0,a,1,a,k,are nonnegative integers less than,b,and,a,k,0.,基本概念,11/28/2024,17,2进制，用两个阿拉伯数字：0、1；,8进制，用八个阿拉伯数字：0、1、2、3、4、5、6、7；,10进制，用十个阿拉伯数字：0到9；,16进制，用十六个阿拉伯数字等等,基本概念,11/28/2024,18,数据在计算机中的表示最终以二进制的形式存在,二进制数表示数码很长：,比如,int,类型占用,4,个字节，,32,位。,比如,100,，用,int,类型的二进制数表达将是：,0000,0000,0000,0000,0110 0100,面对这么长的数进行思考或操作，非常麻烦,用,16,进制或,8,进制可以解决这个问题。,因为，,进制越大，数的表达长度也就越短,。,为什么偏偏是,16,或,8,进制，而不其它的，诸如,9,或,20,进制呢？,11/28/2024,19,基本概念,二进制转为十进制,十六进制,八进制,十进制转二进制,一般进制,整数表示,11/28/2024,20,2,、,8,、,16,，分别是,2,的,1,次方，,3,次方，,4,次方。 这一点使得三种进制之间可以非常直接地互相转换。,8,进制或,16,进制缩短了二进制数，但保持了二进制数的表达特点。,二进制转十进制,11/28/2024,21,二进制数第0位的权值是2的0次方，第1位的权值是2的1次方,所以，设有一个二进制数：0110 0100，转换为10进制为：,下面是竖式：,0110 0100 换算成 十进制,第0位 0 * 2,0,= 0,第1位 0 * 2,1,= 0,第2位 1 * 2,2,= 4,第3位 0 * 2,3,= 0,第4位 0 * 2,4,= 0,第5位 1 * 2,5,= 32,第6位 1 * 2,6,= 64,第7位 0 * 2,7,= 0 ,-,100,11/28/2024,22,用横式计算为：,0 * 2,0,+ 0 * 2,1,+ 1 * 2,2,+ 1 * 2,3,+ 0 * 2,4,+ 1 * 2,5,+ 1 * 2,6,+ 0 * 2,7,= 100,0乘以多少都是0，所以我们也可以直接跳过值为0的位：,1 * 2,2,+ 1 * 2,3,+ 1 * 2,5,+ 1 * 2,6,= 100,二进制转十进制,11/28/2024,23,例,以(101011111),2,为二进制张开的整数，其十进制展开是什么?,解,(101011111),2,=2,8,+2,6,+2,4,+2,3,+2,2,+2+1=351,二进制转十进制,11/28/2024,24,基本概念,二进制转为十进制,十六进制,八进制,十进制转二进制,一般进制,整数表示,11/28/2024,25,16,进制就是逢,16,进,1,，但我们只有,0,到,9,这十个数字，所以我们,用,A,，,B,，,C,，,D,，,E,，,F,这五个字母来分别表示,10,，,11,，,12,，,13,，,14,，,15,。字母不区分大小写。,十六进制,11/28/2024,26,十六进制数的第,0,位的权值为,16,的,0,次方，第,1,位的权值为,16,的,1,次方，第,2,位的权值为,16,的,2,次方,所以，在第,N,（,N,从,0,开始）位上，如果是数,X,（,X,大于等于,0,，并且,X,小于等于,15,，即：,F,）表示的大小为,X * 16,的,N,次方。,十六进制,11/28/2024,27,一个十六进数 2AF5, 那么如何换算成10进制呢？,用竖式计算：,2AF5换算成10进制:,第0位： 5 * 16,0,= 5,第1位： F * 16,1,= 240,第2位： A * 16,2,= 2560,第3位： 2 * 16,3,= 8192 ,-,10997,十六进制,11/28/2024,28,直接计算就是：,5 * 16,0,+ F * 16,1,+ A * 16,2,+ 2 * 16,3,= 10997,(别忘了，在上面的计算中，A表示10，而F表示15),现在可以看出，所有进制换算成10进制，关键在于各自的权值不同。,如果不使用特殊的书写形式，16进制数也会和10进制相混。 C，C+规定，,16进制数必须以 0x开头,。,如：0xff,0xFF,0X102A,十六进制,11/28/2024,29,例,十六进制展开(2AE0B),16,的十进制展开是什么?,(2AE0B),16,=2 16,4,+1016,3,+1416,2,+016+11,=(175627 ),10,十六进制,11/28/2024,30,基本概念,二进制转为十进制,十六进制,八进制,十进制转二进制,一般进制,整数表示,11/28/2024,31,八进制就是逢8进1。,八进制数采用 07这八数来表达一个数。,八进制数第0位的权值为8的0次方，第1位权值为8的1次方，第2位权值为8的2次方,八进制,11/28/2024,32,所以，设有一个八进制数：1507，转换为十进制为：,用竖式表示：,1507换算成十进制。,第0位 7 * 8,0,= 7,第1位 0 * 8,1,= 0,第2位 5 * 8,2,= 320,第3位 1 * 8,3,= 512 ,-,839,同样，我们也可以用横式直接计算：,7 * 80 + 0 * 81 + 5 * 82 + 1 * 83 = 839,结果是，八进制数 1507 转换成十进制数为 839,11/28/2024,33,基本概念,二进制转为十进制,十六进制,八进制,十进制转二进制,一般进制,整数表示,11/28/2024,34,10进制数转换成二进制数，,一个连续除2的过程：,把要转换的数，除以2，得到商和余数，,将商继续除以2，直到商为0。,最后,将所有余数倒序排列，得到数就是转换结果。,十进制转二进制,11/28/2024,35,我们结合例子来说明。比如要转换6为二进制数。,“把要转换的数，除以2，得到商和余数”。,要转换的数是6， 6 2，得到,商是3，余数是0,。,“将商继续除以2,直到商为0”,现在商是3，还不是0，所以继续除以2。,那就： 3 2, 得到,商是1,余数是1,。,“将商继续除以2，直到商为0”,现在商是1，还不是0，所以继续除以2。,那就： 1 2, 得到,商是0，余数是1,（ “将商继续除以2，直到商为0最后将所有余数倒序排列”),现在,商已经是0,。,11/28/2024,36,我们三次计算依次得到余数分别是：,0,、,1,、,1,，,将所有余数倒序排列，那就是：,110,了！,6,转换成二进制，结果是,110,。,被除数,计算过程,商,余数,6,6/2,3,0,3,3/2,1,1,1,1/2,0,1,十进制转二进制,11/28/2024,37,所更常见的换算过程是使用下图的连除：,11/28/2024,38,基本概念,二进制转为十进制,十六进制,八进制,十进制转二进制,一般进制,整数表示,11/28/2024,39,构造整数n的基数b展开的算法,首先，用,b,除,n,得到商和余数，即,n=bq,0,+a,0,，,0a,0,b,余数,a,0,就是,n,的基数,b,展开的最右边一位数字,下一步用,b,除,q,0,得,q,0,= bq,1,+a,1,a,1,是,n,的基数,b,展开中右数第二数字,继续这一过程，不断用,b,除商并以余数为新的基数,b,数字，直到商为,0,时终止,一般进制,11/28/2024,40,例 求(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,一般进制,11/28/2024,41,整数n的基数b展开伪码,Procedure,base b expansion（n：正整数）,q：= n,k：= 0,While,q0,Begin,ak：=q mod b,q：=,q/b,k：= k+1,end,n的基数b展开是(a,k-1,a,1,a,0,),b,一般进制,11/28/2024,42,The Euclidean Of,Algorithms,欧几里德算法,Representations Of Integers,整数表示,Algorithms For,Integers Operations,整数运算算法,整数和除法,11/28/2024,43,整数运算方法,1 1,1 1 1 0,1 0 1 1,1 1 0 0 1,(1110),2,(1011),2,相加,整数运算算法,11/28/2024,44,a=（a,n-1,a,n-2,a,1,a,0,）,2,与b=（b,n-1,b,n-2,b,1,b,0,）,2,两个二进制符号表示的整数相加方法：,首先把他们最右边的数字相加,a,0,+b,0,= c,0,*2+s,0，,其中：,s,0,是a+b的二进制展开中最右边的一位数字,，,c,0,是进位,整数运算算法,11/28/2024,45,然后，下一对字位及进位相加：,a,1,+b,1,=c,1,*2+s,1,其中：,s,1,是a+b的二进制展开中下一位（从右数）数字,，,c,0,是进位,继续这一过程，把两个二进制展开中对应的字位及进位相加，给出a+b的二进制展开中从右数的下一位数字。,整数运算算法,11/28/2024,46,最后：,把a,n-1,b,n-1,和c,n-1,相加得c,n-1,*2+s,n-1.,a+b的首位数字是s,n,=c,n-1,a+b= (s,n,s,n-1,s,0,),2,整数运算算法,11/28/2024,47,例 把a=(1110),2,和b=(1011),2,相加,解 a,0,+b,0,=0+1=02+1 c,0,=0 而s,0,=1,a,1,+b,1,+c,0,=1+1+0=12+0 c,1,=1 而s,1,=0,a,2,+b,2,+c,1,=1+0+1=12+0 c,2,=1 而s,2,=0,a,3,+b,3,+c,2,=1+1+1=12+1 c,3,=1 且 s,3,=1,s,4,=c,3,=1,s=a+b=(11001),2,整数运算算法,11/28/2024,48,整数相加伪码,Procedure,add(a,b:int),a和b的二进制展开分别是（a,n-1,a,n-2,a,1,a,0,）,2,和(b,n-1,b,n-2,b,1,b,0,),2,c:=0,for j:=0 to n-1,begin,d:=,(a,j,+b,j,+c)/2,s,j,=a,j,+b,j,+c-2d,c:=d,end,s,n,=c,和的二进制展开是(s,n,s,n-1,s,0,),2,11/28/2024,49,一步一步把（10111）,2,（11010）,2,相加,解：,1 1 1,1 0 1 1 1,1 1 0 1 0,1 1 0 0 0 1,11/28/2024,50,整数运算算法,考虑两个n位整数的乘法，根据乘法分配律：,11/28/2024,51,注意到：,当,b,j,=1,时，,ab,j,=a,，当,b,j,=0,时，,ab,j,=0,；,每当用,2,乘以一项的时候，就等于把这一项的二进制展开向左移一位，并在尾部加一个零；,可以把,ab,j,的二进制向左移,j,位，并在尾部加上,j,个,0,来计算（,ab,j,）,2,j,；,最后，把,n,个整数,ab,j,2,j,相加，得到,ab,。,11/28/2024,52,例7 求a=（110）,2,和b=(101),2,的乘积,解：ab,0,2,0,=（110）,2,*1*2,0=,(110),2,ab,1,2,1,=（110）,2,*0*2,1,=(0000),2,及,.,ab,2,2,2,=(110),2,*1*2,2,=(11000),2,用上面算法把（110）,2,，（0000）,2,，（11000）,2,相加，得到,ab=（11110）,2,11/28/2024,53,1 1 0,1 0 1,1 1 0,0 0 0,1 1 0,1 1 1 1 0,计算过程：,11/28/2024,54,整数乘法伪码,Procedure,multiply(a,b:int),a和b的二进制展开分别是（a,n,-1a,n-2,a,1,a,0,）,2,和(b,n-1,b,n-2,b,1,b,0,),2,for j:=0 to n-1,begin,if b,j:,=1 then c,j,:=a移j位,else c,j,:=0,end,c,0,c,1,c,n-1,是部分积,p:=0,for,j:=0 to n-1,p:=p+ c,j,p是ab的值,11/28/2024,55,例,将（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,11/28/2024,56,自己分析二进制加法和乘法算法的,计算复杂度。,（见教材相关的部分）,整数运算算法,11/28/2024,57,本节内容到此结束,谢谢大家！,11/28/2024,58,