离散数学期末复习考试题VIP专享

1 / 5 总复习提纲：1． 判断一个数a 是否为素数的算法，最多、一般情况下、至少要作多少次除法运算？要达到最少的次数应该附加什么？依据是什么（素数定义、性质(Th9.2.2) ） P184、P185 观察一正整数a 是否素数，要用小于a 大于 1 的整数一一来试除吗？不要。定理 9.2.2 若 a 是大于 1 的整数，而所有小于或等于a 的素数都不能整除a，则 a 是素数。令 π( x)表示不超过x 的素数个数，可以证明0)(limxxx它表明了 :尽管素数个数无穷多，但它比起正整数的个数来少得很多。2． 欧几里德算法思想及时间复杂度问题？P201本质上是用辗转相除把求两个正整数最大公因数的问题化为求两个较小整数的最大公因数，直到两个整数中的一个为0。现将定理 9.3.2 欧几里德算法以伪码形式给出如下：Euclid ( a，b：整数 ) if b=0 then return a while b>0 { r← a( mod b)a←bb←r} return a算法中过程的每一步都是a 用 b 代替，而 b 用 a( mod b) 代替。 只要 b>0，这个过程就重复下去，当b=0 时算法终止，此时a 的值也就是这一过程的非零余数，即为a 和 b 的最大公因数。在欧几里德算法中基本操作是除法，为研究欧几里德算法的时间复杂性，需要求出算法中所使用的除法次数，下面拉梅定理给出解答。证明：如下定理定理 10.2.1 设 a 和 b 是满足 a≥b 的正整数，则欧几里德算法求得( a， b) 而使用除法的次数小于或等于b 的十进制位数的5 倍。3． 两个 n 位的二进制整数a 和 b 的乘法算法P204 可按下面等式进行计算：ab=a102niiib=102)(niiiab计算过程：如下 (核心思想：将abi 当作一个整体，做平移，再做加法，而不是直接做乘法运算 ) 首先注意在bi=1 时 abi=a，而 bi=0 时 abi=0。每当用 2 乘一项时，结果都是把该项的二进制展开向左移一位并在尾部加上一个0，因此，可把abi 的二进制展开向左移i 位，再在尾部加上 i 个 0 来计算 ( abi) 2i。最后，将n 个整数 ( abi) 2i，i=0，1，⋯， n- 1，相加得到ab。两个正整数a 和 b 二进制展开的乘法算法：mul( a， b)for i← 0 ton- 1 ifbi=1 thenci← a 左移 i 位elseci← 0 //c0c1⋯cn-1 是部分积2 / 5 p ← 0 for i← 0 ton- 1 p ← p+ci//p 是 ab 的值读者不难得出：移位个数是O( n2) ，位加法个数是O( n2) ，这是因为，所有n 个整数 ( abi) 2i，i=0，1，⋯，...