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

1 离散数学 Discrete Mathematics 汪荣贵贵 教授 合肥工业业大学软软件学院专专用课课件 2010.03 Date 1 第二章第二章 算法基础算法基础 Date 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 递归 Date 13 The Euclidean Of Algorithms 欧几里德算法 Representations Of Integers 整数表示 Algorithms For Integers Operations 整数运算算法 &整数和除法 Date 14 基本概念 二进制转为十进制 十六进制 八进制 十进制转二进制 一般进制 & 整数表示 Date 15 生活中其实很多地方的计数方法都多少有点不同 进制的影子。 我们最常用的10进制，起源于人有10个指头。 至于二进制没有袜子称为0只袜子，有一只 袜子称为1只袜子，但若有两袜子，则我们常说 的是：1双袜子。 还有：七进制，比如星期。十六进制，比如小 时或“一打”，六十进制，比如分钟或角度 & 基本概念 Date 16 定理1 令b为大于1的正整数。那么如果n是个 正整数，就可以唯一地表示为下面的形式: n=akbk+ak-1bk-1+a1b+a0 其中k是个非负整数，a0，a1ak是小于b的非 负整数，ak0 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=akbk+ ak-1bk-1 + + a1b +a0, where k is a nonnegative integer, a0, a1,ak are nonnegative integers less than b,and ak0. & 基本概念 Date 17 2进制，用两个阿拉伯数字：0、1； 8进制，用八个阿拉伯数字：0、1、2、3、 4、5、6、7； 10进制，用十个阿拉伯数字：0到9； 16进制，用十六个阿拉伯数字等等 & 基本概念 Date 18 数据在计算机中的表示最终以二进制的形式存在 二进制数表示数码很长： 比如int 类型占用4个字节，32位。 比如100，用int类型的二进制数表达将是： 0000 0000 0000 0000 0110 0100 面对这么长的数进行思考或操作，非常麻烦 用16进制或8进制可以解决这个问题。 因为，进制越大，数的表达长度也就越短。 为什么偏偏是16或8进制，而不其它的，诸如9或 20进制呢？ Date 19 基本概念 二进制转为十进制 十六进制 八进制 十进制转二进制 一般进制 & 整数表示 Date 20 2、8、16，分别是2的1次方，3次方，4 次方。 这一点使得三种进制之间可以 非常直接地互相转换。 8进制或16进制缩短了二进制数，但保 持了二进制数的表达特点。 & 二进制转十进制 Date 21 二进制数第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 第4位 0 * 24 = 0 第5位 1 * 25 = 32 第6位 1 * 26 = 64 第7位 0 * 27 = 0 - 100 Date 22 用横式计算为： 0 * 20 + 0 * 21 + 1 * 22 + 1 * 23 + 0 * 24 + 1 * 25 + 1 * 26 + 0 * 27 = 100 0乘以多少都是0，所以我们也可以直接跳过值 为0的位： 1 * 22 + 1 * 23 + 1 * 25 + 1 * 26 = 100 & 二进制转十进制 Date 23 例 以(101011111)2为二进制张开的 整数，其十进制展开是什么? 解 (101011111)2 =28+26+24+23+22+2+1=351 & 二进制转十进制 Date 24 基本概念 二进制转为十进制 十六进制 八进制 十进制转二进制 一般进制 & 整数表示 Date 25 16进制就是逢16进1，但我们只有0到9 这十个数字，所以我们用A，B，C，D ，E，F这五个字母来分别表示10，11 ，12，13，14，15。字母不区分大小 写。 & 十六进制 Date 26 十六进制数的第0位的权值为16的0次方 ，第1位的权值为16的1次方，第2位的 权值为16的2次方 所以，在第N（N从0开始）位上，如果 是数 X （X 大于等于0，并且X小于等 于 15，即：F）表示的大小为 X * 16 的N次方。 & 十六进制 Date 27 一个十六进数 2AF5, 那么如何换算成10进制呢？ 用竖式计算： 2AF5换算成10进制: 第0位： 5 * 160 = 5 第1位： F * 161 = 240 第2位： A * 162 = 2560 第3位： 2 * 163 = 8192 - 10997 & 十六进制 Date 28 直接计算就是： 5 * 160 + F * 161 + A * 162 + 2 * 163 = 10997 (别忘了，在上面的计算中，A表示10，而F表示15) 现在可以看出，所有进制换算成10进制，关键在于各 自的权值不同。 如果不使用特殊的书写形式，16进制数也会和10进制 相混。 C，C+规定，16进制数必须以 0x开头。 如：0xff,0xFF,0X102A & 十六进制 Date 29 例 十六进制展开(2AE0B)16的十进制 展开是什么? (2AE0B)16=2 164+10163+14162+016+11 =(175627 )10 & 十六进制 Date 30 基本概念 二进制转为十进制 十六进制 八进制 十进制转二进制 一般进制 & 整数表示 Date 31 八进制就是逢8进1。 八进制数采用 07这八数来表达一个数 。 八进制数第0位的权值为8的0次方，第1 位权值为8的1次方，第2位权值为8的2 次方 & 八进制 Date 32 所以，设有一个八进制数：1507，转换为十进制为： 用竖式表示： 1507换算成十进制。 第0位 7 * 80 = 7 第1位 0 * 81 = 0 第2位 5 * 82 = 320 第3位 1 * 83 = 512 - 839 同样，我们也可以用横式直接计算： 7 * 80 + 0 * 81 + 5 * 82 + 1 * 83 = 839 结果是，八进制数 1507 转换成十进制数为 839 Date 33 基本概念 二进制转为十进制 十六进制 八进制 十进制转二进制 一般进制 & 整数表示 Date 34 10进制数转换成二进制数， 一个连续除2的过程： 把要转换的数，除以2，得到商和余数， 将商继续除以2，直到商为0。 最后,将所有余数倒序排列，得到数就是 转换结果。 & 十进制转二进制 Date 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。 Date 36 !我们三次计算依次得到余数分别是：0、1、1， !将所有余数倒序排列，那就是：110了！ !6转换成二进制，结果是110。 被除数计算过程商余数 66/230 33/211 11/201 & 十进制转二进制 Date 37 所更常见的换算过程是使用下图的连除： Date 38 基本概念 二进制转为十进制 十六进制 八进制 十进制转二进制 一般进制 & 整数表示 Date 39 构造整数n的基数b展开的算法 首先，用b除n得到商和余数，即 n=bq0+a0，0a0 b 余数a0就是n的基数b展开的最右边一位数字 下一步用b除q0得 q0 = bq1+a1 a1是n的基数b 展开中右数第二数字 继续这一过程，不断用b除商并以余数为新的基数b数 字，直到商为0时终止 & 一般进制 Date 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 & 一般进制 Date 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展开是(ak-1a1a0)b & 一般进制 Date 42 The Euclidean Of Algorithms 欧几里德算法 Representations Of Integers 整数表示 Algorithms For Integers Operations 整数运算算法 &整数和除法 Date 43 整数运算方法整数运算方法 1 11 1 1 1 1 0 1 1 1 0 1 0 1 1 1 0 1 1 1 1 0 0 11 1 0 0 1 (1110)(1110) 2 2 (1011)(1011) 2 2 相加相加 & 整数运算算法 Date 44 a=（an-1an-2a1a0）2 与b=（bn-1bn-2b1b0）2 两个二进制符号表示的整数相加方法： 首先把他们最右边的数字相加 a0+b0 = c0*2+s0， 其中： s0是a+b的二进制展开中最右边的一位数字， c0是进位 & 整数运算算法 Date 45 然后，下一对字位及进位相加： a1+b1=c1*2+s1 其中： s1是a+b的二进制展开中下一位（从右数） 数字，c0是进位 继续这一过程，把两个二进制展开中对应 的字位及进位相加，给出a+b的二进制展开中 从右数的下一位数字。 & 整数运算算法 Date 46 最后： 把an-1,bn-1和cn-1相加得cn-1*2+sn-1. a+b的首位数字是sn=cn-1 a+b= (snsn-1s0)2 & 整数运算算法 Date 47 例 把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 & 整数运算算法 Date 48 整数相加伪码 Procedure add(a,b:int) a和b的二进制展开分别是（an-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 Date 49 一步一步把（10111）2（11010）2 相加 解： 1 1 1 1 0 1 1 1 1 1 0 1 0 1 1 0 0 0 1 Date 50 & 整数运算算法 考虑两个n位整数的乘法，根据乘法 分配律： Date 51 注意到： 当bj=1时，abj=a，当bj=0时， abj=0； 每当用2乘以一项的时候，就等于把这一 项的二进制展开向左移一位，并在尾部 加一个零； 可以把abj的二进制向左移j位，并在尾部 加上j个0来计算（abj）2j； 最后，把n个整数abj2j相加，得到ab。 Date 52 例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 Date 53 1 1 0 1 0 1 1 1 0 0 0 0 1 1 0 1 1 1 1 0 计算过程： Date 54 整数乘法伪码 Procedure multiply(a,b:int) a和b的二进制展开分别是（an-1an-2a1a0）2和(bn-1