算法设计和分析课件

《算法设计和分析课件》由会员分享，可在线阅读，更多相关《算法设计和分析课件（132页珍藏版）》请在金锄头文库上搜索。

1、算法设计与分析算法设计与分析 国家高性能计算中心（合肥）国家高性能计算中心（合肥）2008.8.191Ch.1 概率算法概率算法1. 故故事事：想想象象自自己己是是神神化化故故事事的的主主人人公公，你你有有一一张张不不易易懂懂的的地地图图，上上面面描描述述了了一一处处宝宝藏藏的的藏藏宝宝地地点点。经经分分析析你你能能确确定定最最有有可可能能的的两两个个地地点点是是藏藏宝宝地地点点，但但二二者者相相距距甚甚远远。假假设设你你如如果果已已到到达达其其中中一一处处，就就立立即即知知道道该该处处是是否否为为藏藏宝宝地地点点。你你到到达达两两处处之之一一地地点点及及从从其其中中一一处处到到另另一一处处的

2、的距距离离是是5天天的的行行程程。进进一一步步假假设设有有一一条条恶恶龙龙，每每晚晚光光顾顾宝宝藏藏并并从从中中拿拿走走一一部部分分财财宝宝。假假设设你你取取宝宝藏的方案有两种：藏的方案有两种：1.1 引言引言2 方方案案1. 花花4天天的的时时间间计计算算出出准准确确的的藏藏宝宝地地点点，然然后出发寻宝，一旦出发不能重新计算后出发寻宝，一旦出发不能重新计算 方方案案2. 有有一一个个小小精精灵灵告告诉诉你你地地图图的的秘秘密密，但但你你必须付给他报酬，相当于龙必须付给他报酬，相当于龙3晚上拿走的财宝晚上拿走的财宝 Prob 1.1.1 若若忽忽略略可可能能的的冒冒险险和和出出发发寻寻宝宝的的

3、代代价价，你是否接受小精灵的帮助？你是否接受小精灵的帮助？ 显显然然，应应该该接接受受小小精精灵灵的的帮帮助助，因因为为你你只只需需给给出出3晚晚上上被被盗盗窃窃的的财财宝宝量量，否否则则你你将将失失去去4晚晚被被盗财宝量。盗财宝量。 但是，若冒险，你可能做得更好！但是，若冒险，你可能做得更好！1.1 引言引言3 设设x是是你你决决定定之之前前当当日日的的宝宝藏藏价价值值，设设y是是恶恶龙龙每每晚盗走的宝藏价值，并设晚盗走的宝藏价值，并设x9y 方方案案1：4天天计计算算确确定定地地址址，行行程程5天天，你你得得到到的的宝宝藏价值为：藏价值为：x-9y 方方案案2：3y付付给给精精灵灵，行行程

4、程5天天失失去去5y，你你得得到到的的宝藏价值为：宝藏价值为：x-8y 方方案案3：投投硬硬币币决决定定先先到到一一处处，失失败败后后到到另另一一处处(冒险方案冒险方案) 一次成功所得：一次成功所得：x-5y，机会，机会1/2 二次成功所得：二次成功所得：x-10y，机会，机会1/21.1 引言引言期望赢利：期望赢利：x-7.5y42. 意义意义 该故事告诉我们：当一个算法面临某种选择该故事告诉我们：当一个算法面临某种选择时，有时随机选择比耗时做最优选择更好，尤其时，有时随机选择比耗时做最优选择更好，尤其是当最优选择所花的时间大于随机选择的平均时是当最优选择所花的时间大于随机选择的平均时间的时

5、侯间的时侯 显然，概率算法只能是期望的时间更有效，显然，概率算法只能是期望的时间更有效，但它有可能遭受到最坏的可能性。但它有可能遭受到最坏的可能性。53. 期望时间和平均时间的区别期望时间和平均时间的区别v确定算法的平均执行时间确定算法的平均执行时间 输入规模一定的所有输入实例是等概率出现时，算法输入规模一定的所有输入实例是等概率出现时，算法的平均执行时间。的平均执行时间。v概率算法的期望执行时间概率算法的期望执行时间 反复解同一个输入实例所花的平均执行时间。反复解同一个输入实例所花的平均执行时间。 因此，对概率算法可以讨论如下两种期望时间因此，对概率算法可以讨论如下两种期望时间平均的期望时间

6、平均的期望时间：所有输入实例上平均的期望执行时：所有输入实例上平均的期望执行时间间最坏的期望时间最坏的期望时间：最坏的输入实例上的期望执行时间：最坏的输入实例上的期望执行时间64. 例子例子快速排序中的随机划分快速排序中的随机划分要要求求学学生生写写一一算算法法，由由老老师师给给出出输输入入实实例例，按按运运行行时时间间打打分分，所所有有学学生生均均不不敢敢用用简简单单的的划划分分，运运行行时时间间在在1500-2600ms，三三个个学学生生用用概率的方法划分，运行时间平均为概率的方法划分，运行时间平均为300ms。8皇后问题皇后问题系系统统的的方方法法放放置置皇皇后后(回回溯溯法法)较较合合

7、适适，找找出出所所有有92个个解解 O(2n)，若若只找只找92个其中的任何一个解可在线性时间内完成个其中的任何一个解可在线性时间内完成O(n)。 随机法：随机法：随机地放置若干皇后能够改进回溯法，特别是当随机地放置若干皇后能够改进回溯法，特别是当n较大时较大时判断大整数是否为素数判断大整数是否为素数确定算法无法在可行的时间内判断一个数百位十进制数是否素数，确定算法无法在可行的时间内判断一个数百位十进制数是否素数，否则密码就不安全。否则密码就不安全。 概率算法将有所作为：若能接受一个任意小的错误的概率概率算法将有所作为：若能接受一个任意小的错误的概率75. 概率算法的特点概率算法的特点 (1)

8、 不可再现性不可再现性 在同一个输入实例上，每次执行结果不尽相同，例在同一个输入实例上，每次执行结果不尽相同，例如如N-皇后问题皇后问题概率算法运行不同次将会找到不同的正确解概率算法运行不同次将会找到不同的正确解找一给定合数的非平凡因子找一给定合数的非平凡因子每次运行的结果不尽相同，但确定算法每次运行结果必每次运行的结果不尽相同，但确定算法每次运行结果必定相同定相同 (2) 分析困难分析困难 要求有概率论，统计学和数论的知识要求有概率论，统计学和数论的知识86. 本章约定本章约定 随机函数随机函数uniform，随机随机，均匀均匀，独立独立设设a，b为实数，为实数，ab, uniform(a,

9、 b) 返回返回x，a x b 设设i，j为整数，为整数，ij, uniform(i, j)=k, i k j 设设X是非空有限集，是非空有限集， uniform(X) X 9例例1：设p是是一一个个素素数数，a是是一一个个整整数数满足足1a0 do if (j is odd) s sa mod p;a a2 mod p;j j div 2;return s;Draw (a, p) / 在在X中随机取一元素中随机取一元素j uniform(1.p-1);return ModularExponent(a, j, p); / 在在X中随机取一元素中随机取一元素11n伪随机数发生器伪随机数发生器在实

10、用中不可能有真正的随机数发生器，多数情况在实用中不可能有真正的随机数发生器，多数情况下是用伪随机数发生器代替。下是用伪随机数发生器代替。大多数伪随机数发生器是基于一对函数：大多数伪随机数发生器是基于一对函数：S: X X, 这里这里X足够大，它是种子的值域足够大，它是种子的值域R: X Y, Y是伪随机数函数的值域是伪随机数函数的值域使用使用S获得种子序列：获得种子序列：x0=g, xi=S(xi-1), i0然后使用然后使用R R获得伪随机序列：获得伪随机序列：yi=R(xi), i 0该序列必然是周期性的，但只要该序列必然是周期性的，但只要S S和和R R选的合适，该选的合适，该周期长度会

11、非常长。周期长度会非常长。TC中可用中可用rand()和和srand(time), 用用GNU C更好更好121.基本特征基本特征随机决策随机决策在同一实例上执行两次其结果可能不同在同一实例上执行两次其结果可能不同在同一实例上执行两次的时间亦可能不太相同在同一实例上执行两次的时间亦可能不太相同2.分类分类Numerical, Monte Carlo, Las Vegas, Sherwood.很多人将所有概率算法很多人将所有概率算法(尤其是数字的概率算法尤其是数字的概率算法)称为称为Monte Carlo算法算法1.2 概率算法的分类概率算法的分类13数字算法数字算法随机性被最早用于求数字问题的

12、近似解随机性被最早用于求数字问题的近似解例如，求一个系统中队列的平均长度的问题，确定算法很例如，求一个系统中队列的平均长度的问题，确定算法很难得到答案难得到答案概率算法获得的答案一般是近似的，但通常算法执行的时概率算法获得的答案一般是近似的，但通常算法执行的时间越长，精度就越高，误差就越小间越长，精度就越高，误差就越小使用的理由使用的理由现实世界中的问题在原理上可能就不存在精确解现实世界中的问题在原理上可能就不存在精确解例如，实验数据本身就是近似的，一个无理数在计算机例如，实验数据本身就是近似的，一个无理数在计算机中只能近似地表示中只能近似地表示精确解存在但无法在可行的时间内求得精确解存在但无

13、法在可行的时间内求得有时答案是以置信区间的形式给出的有时答案是以置信区间的形式给出的1.2 概率算法的分类概率算法的分类14Monte Carlo算法算法 (MC算法算法)蒙蒙特特卡卡洛洛算算法法1945年年由由J. Von Neumann进进行行核核武武模模拟拟提提出出的的。它它是是以以概概率率和和统统计计的的理理论论与与方方法法为为基基础础的的一一种种数数值值计计算算方方法法，它它是是双双重重近近似似：一一是是用用概概率率模模型型模模拟拟近近似似的的数数值值计计算算，二二是是用用伪随机数模拟真正的随机变量的样本。伪随机数模拟真正的随机变量的样本。这里我们指的这里我们指的MC算法是：算法是：

14、 若若问问题题只只有有1个个正正确确的的解解，而而无无近近似解的可能时使用似解的可能时使用MC算法算法例如，判定问题只有真或假两种可能性，没有近似解例如，判定问题只有真或假两种可能性，没有近似解 因式分解，我们不能说某数几乎是一个因子因式分解，我们不能说某数几乎是一个因子1.特特点点：MC算算法法总总是是给给出出一一个个答答案案，但但该该答答案案未未必必正正确确，成成功功(即答案是正确的即答案是正确的)的概率正比于算法执行的时间的概率正比于算法执行的时间2.缺点：缺点：一般不能有效地确定算法的答案是否正确一般不能有效地确定算法的答案是否正确1.2 概率算法的分类概率算法的分类15Las Veg

15、as算法算法 (LV算法算法)LV算法绝不返回错误的答案。算法绝不返回错误的答案。1.特特点点：获获得得的的答答案案必必定定正正确确，但但有有时时它它仍仍根根本本就就找找不不到答案到答案。 和和MC算算法法一一样样，成成功功的的概概率率亦亦随随算算法法执执行行时时间间增增加加而而增增加加。无无论论输输入入何何种种实实例例，只只要要算算法法在在该该实实例例上上运运行行足足够的次数，则算法失败的概率就任意小。够的次数，则算法失败的概率就任意小。 Sherwood算法算法Sherwood算法总是给出正确的答案。算法总是给出正确的答案。当当某某些些确确定定算算法法解解决决一一个个特特殊殊问问题题平平均

16、均的的时时间间比比最最坏坏时时间间快快得得多多时时，我我们们可可以以使使用用Sherwood算算法法来来减减少少，甚甚至是消除好的和坏的实例之间的差别至是消除好的和坏的实例之间的差别。1.2 概率算法的分类概率算法的分类16这类算法主要用于找到一个数字问题的近似解这类算法主要用于找到一个数字问题的近似解1.3.1 值计算值计算n实验：将实验：将n根飞镖随机投向一正方形的靶子，计算落入此正方根飞镖随机投向一正方形的靶子，计算落入此正方形的内切圆中的飞镖数目形的内切圆中的飞镖数目k。假定飞镖击中方形靶子任一点的概率相等假定飞镖击中方形靶子任一点的概率相等(用计算机模拟比任用计算机模拟比任一飞镖高手

17、更能保证此假设成立一飞镖高手更能保证此假设成立)设圆的半径为设圆的半径为r，面积，面积s1= r2, 方靶面方靶面积s2=4r2由等概率假设可知落入圆中的飞镖和正方形内的飞镖平均比为：由等概率假设可知落入圆中的飞镖和正方形内的飞镖平均比为： 由此知：由此知： 1.3 数字概率算法数字概率算法171.求求近似值的算法近似值的算法为简单起见，只以上图的右上为简单起见，只以上图的右上1/4象限为样本象限为样本Darts (n) k 0;for i 1 to n do x uniform(0, 1);y uniform(0, 1); / 随机产生点随机产生点(x,y)if (x2 + y2 1) th

18、en k+; /圆内圆内return 4k/n;实验结果实验结果： =3.141592654n = 1000万万: 3.140740, 3.142568 (2位精确位精确)n = 1亿亿: 3.141691, 3.141363 (3位精确位精确)n = 10亿亿: 3.141527, 3.141507 (4位精确位精确)1.3.1 值计算值计算181.求求近似值的算法近似值的算法Ex.1 若将若将y uniform(0, 1) 改为改为 y x, 则上则上述的算法估计的值是什么？述的算法估计的值是什么？ 1.3.1 值计算值计算19Monte Carlo积分积分(但不是指我们定义的但不是指我们

19、定义的MC算法算法)n概率算法概率算法1设设f: 0, 1 0, 1是一个连续函数，则由曲线是一个连续函数，则由曲线y=f(x), x轴轴, y轴和直线轴和直线x=1围成的面积由下述积分给出：围成的面积由下述积分给出： 向单位面积的正方形内投镖向单位面积的正方形内投镖n次，落入阴影部分的镖的次，落入阴影部分的镖的数目为数目为k，则，则 显然，只要显然，只要n足够大足够大 1.3.2 数字数字积分分 (计算定算定积分的分的值)201.概率算法概率算法1HitorMiss (f, n) k 0;for i 1 to n do x uniform(0, 1);y uniform(0, 1);if y

20、 f(x) then k+;return k/n;Note: 是是S/4的面积，的面积， =S, 1.3.2 数字数字积分分 (计算定算定积分的分的值)211.概率算法概率算法1Ex2. 在机器上用在机器上用 估计估计值，给出不出不同的同的n值及精度。及精度。Ex3. 设a, b, c和和d是是实数，且数，且a b, c d, f:a, b c, d是一个是一个连续函数，写一概率算法函数，写一概率算法计算算积分：分： 注意，函数的参数是注意，函数的参数是a, b, c, d, n和和f, 其中其中f用函用函数指数指针实现，请选一一连续函数做函数做实验，并，并给出出实验结果。果。1.3.2 数字

21、数字积分分 (计算定算定积分的分的值)221.概率算法概率算法1*Ex4. 设设,是是(0,1)之间的常数，证明：之间的常数，证明：若若I是是 的正确值，的正确值，h h是由是由HitorHissHitorHiss算法返回的算法返回的值，则当值，则当n I(1-I)/2时有：时有：Prob|h-I| Tj;1.4.2 随机的随机的预处理理43例例2：离散对数计算：离散对数计算离散对数计算困难使其可用于密码算法，数字签名等离散对数计算困难使其可用于密码算法，数字签名等定义：设定义：设 a=gx mod p记记 logg,pa=x，称，称x为为a的的(以以g为底模除为底模除p)对数对数从从p，g，

22、a计算称计算称x为离散对数问题。为离散对数问题。简单算法：简单算法： 计算计算gx对所有的对所有的x，最多计算，最多计算0x p-1 或或 1xp，实际上离散对数，实际上离散对数是是循环群。循环群。 验证验证a=gx mod p 是否成立。是否成立。dlog(g, a, p) / 当这样的对数不存在时，算法返回当这样的对数不存在时，算法返回p x 0; y 1; do x+;y y*g; / 计算计算y=gx while ( a y mod p) and (x p); return x1.4.2 随机的随机的预处理理44问题：最坏问题：最坏O(p)循环次数难以预料循环次数难以预料当满足一定条件

23、时平均循环当满足一定条件时平均循环p/2次次当当p=24位十进制数，循环位十进制数，循环1024次次千万亿次千万亿次/秒秒 (1016次次/秒秒) 大约算大约算1年年(108秒秒/年年)若若p是数百位十进制？随机选择都可能无法在可行的时间内求解。是数百位十进制？随机选择都可能无法在可行的时间内求解。假设有一个平均时间性能很好，但最坏情况差的确定算法求假设有一个平均时间性能很好，但最坏情况差的确定算法求logp,ga，怎样用，怎样用Sherwood算法求解该问题？算法求解该问题？设设p=19, g=2当当a=14, 6时，时，log2,1914 = 7, log2,196=14，与，与a的取值相

24、关的取值相关当用当用dlog求求14的离散对数时，循环的离散对数时，循环7次，求次，求6的对数时要执行的对数时要执行14次，次，用用sherwood算法应该使得与算法应该使得与a无关，用随机预处理的方法计算无关，用随机预处理的方法计算logg,pa1.4.2 随机的随机的预处理理45定理定理(见见p877, 31.6) dlogRH(g, a p) / 求求logg,pa, a = gx mod p，求，求x / Sherwood算法算法 r uniform(0.p-2); b ModularExponent(g, r, p); /求幂模求幂模b=gr mod p c ba mod p; /

25、y logg,pc; / 使用确定性算法求使用确定性算法求logp,gc, y=r+x return (y-r) mod (p-1); / 求求xEx. 分析分析dlogRH的工作原理，指出该算法相应的的工作原理，指出该算法相应的u和和v1.4.2 随机的随机的预处理理46随机预处理提供了一种加密计算的可能性随机预处理提供了一种加密计算的可能性假定你想计算某个实例假定你想计算某个实例x，通过，通过f(x)计算，但你缺乏计算计算，但你缺乏计算能力或是缺乏有效算法，而别人有相应的计算能力，愿能力或是缺乏有效算法，而别人有相应的计算能力，愿意为你计算意为你计算(可能会收费可能会收费)，若你愿意别人帮

26、你计算，但，若你愿意别人帮你计算，但你不愿意泄露你的输入实例你不愿意泄露你的输入实例x，你将如何做？，你将如何做？可将随机预处理使用到可将随机预处理使用到f的计算上：的计算上： 使用函数使用函数u将将x加密为某一随机实例加密为某一随机实例y 将将y提交给提交给f计算出计算出f(y)的值的值 使用函数使用函数v转换为转换为f(x)上述过程，他人除了知道你的实例大小外，不知道上述过程，他人除了知道你的实例大小外，不知道x的任的任何信息，因为何信息，因为u(x,r)的概率分布的概率分布(只要只要r是随机均匀选择的是随机均匀选择的)是独立于是独立于x的。的。1.4.2 随机的随机的预处理理47设两个数

27、组设两个数组val1.n和和ptr1.n及及head构成一个有构成一个有序的静态链表：序的静态链表：valhead valptrhead valptrptrhead valptrn-1head例：例：1.4.3 搜索有序表搜索有序表48若若val1.n本身有序，可用折半查找找某个给定的本身有序，可用折半查找找某个给定的key，时，时间为间为O(lgn)。但因此处理链式结构，故最坏时间是。但因此处理链式结构，故最坏时间是(n)(n)。尽管如此，我们能够找到一个确定性算法，平均时间为尽管如此，我们能够找到一个确定性算法，平均时间为 。相应的相应的SherwoodSherwood算法的期望时间是算法

28、的期望时间是 ，它虽然并不比确，它虽然并不比确定性算法快，但他消除了最坏实例。定性算法快，但他消除了最坏实例。假定表中元素互不相同，且所求的关键字表中存在，则给定假定表中元素互不相同，且所求的关键字表中存在，则给定x x，我们是求下标，我们是求下标i i，使，使vali=x,这里这里1i n。任何实例可以有两个参数刻画：任何实例可以有两个参数刻画：前前n n个整数的排列个整数的排列x x的的rank1.4.3 搜索有序表搜索有序表49设设Sn是所有是所有n!个排列的集合，设个排列的集合，设A是一个确定性算是一个确定性算法法 tA(n, k, )表示算法表示算法A的执行时间，此时间与被的执行时间

29、，此时间与被查找元素的秩查找元素的秩k，以及，以及val的排序的排序相关。若相关。若A A是一是一个概率算法，则个概率算法，则tA(n, k, )表示算法的期望值。无表示算法的期望值。无论算法是确定的还是概率的，论算法是确定的还是概率的，wA(n)和和mA(n)表示表示最坏时间和平均时间，因此有：最坏时间和平均时间，因此有： 1.4.3 搜索有序表搜索有序表501.时间为时间为O(n)的确定算法的确定算法设设xvali且且x在表中，则从位置在表中，则从位置i开始查找开始查找x的算法为：的算法为：Search(x, i) /仍可改进仍可改进while x vali do i ptri;retur

30、n i;在表在表val1.n中查找中查找x的算法为：的算法为：A(x) return Search(x, head);1.4.3 搜索有序表搜索有序表511.时间为时间为O(n)的确定算法的确定算法分析：分析：设设rank(x)=k, 则：则： 算法算法A在在n个元素的表中查找个元素的表中查找x所需的访问数组所需的访问数组元素的次数，显然与元素的次数，显然与无关无关 算法算法A A最坏时的访问次数最坏时的访问次数 算法算法A A平均的访问次数平均的访问次数 1.4.3 搜索有序表搜索有序表522.时间为时间为O(n)的概率算法的概率算法D(x) i uniform(1.n);y vali;ca

31、se x y: return Search(x, ptri); / case2 otherwise: return i; / x = y 1.4.3 搜索有序表搜索有序表532.时间为时间为O(n)的概率算法的概率算法性能分析：性能分析： 设设rank(x)=k, rank(vali)=j (D访问数组次数访问数组次数)若若 k j, 则则 ，属于，属于case2，从第，从第j小元素搜索小元素搜索若若 k = j, 则则 ，属于，属于case3 1.4.3 搜索有序表搜索有序表543.平均时间为平均时间为 的确定算法的确定算法B(x) /设设x在在val1.n中中i head;max vali

32、; / max初值是表初值是表val中最小值中最小值for j i to do / 在前在前 个数中找不大于个数中找不大于x / 的最大整数的最大整数y相应下标相应下标i y valj; if max y x then i j; max y; / endforreturn Search(x, i); / 从从y向后搜索向后搜索for循环的目的：找不超过循环的目的：找不超过x的最大整数的最大整数y，使搜索从，使搜索从y开始，若将开始，若将val1.n中的中的n个整数看作是均匀随机分布的，则在个整数看作是均匀随机分布的，则在val1.l中求中求y值就相当于在值就相当于在n个整数中，随个整数中，随机

33、地取机地取l个整数，求这个整数，求这l个整数中不大于个整数中不大于x的最大整数的最大整数y。1.4.3 搜索有序表搜索有序表553.平均时间为平均时间为 的确定算法的确定算法4.算法分析：算法分析：可用一个与可用一个与l和和n相关的随机变量来分析，更简单的分析如下：相关的随机变量来分析，更简单的分析如下：设设n个整数的排列满足：个整数的排列满足：a1 a2 0，更好的情况是，更好的情况是Obstinate(x) repeatLV(x, y, success);until success;return y; 设设t(x)是算法是算法obstinate找到一个正确解的期望时间，则找到一个正确解的期

34、望时间，则 若要最小化若要最小化t(x)， 则需在则需在p(x), s(x)和和e(x)之间进行某种折衷，例如，若之间进行某种折衷，例如，若要较少失败的时间，则可降低成功的概率要较少失败的时间，则可降低成功的概率p(x)。1.5 Las Vegas 算法算法591.传统的回溯法传统的回溯法置当前行为第置当前行为第1行，当前列为第行，当前列为第1列，即列，即ij1;while i 8 do / 当前行号当前行号 8检查当前行：从当前列检查当前行：从当前列j起向后逐列试探，寻找安全列号；起向后逐列试探，寻找安全列号；if 找到安全列号找到安全列号 then 放置皇后，将列号记入栈中，并将下一行置为

35、当前行，即放置皇后，将列号记入栈中，并将下一行置为当前行，即i+; j1; /当前列置为当前列置为1 else 退栈回溯到上一行，即退栈回溯到上一行，即i-； 移去该行已已放置的皇后，以该皇后所在列的下一列作为当前移去该行已已放置的皇后，以该皇后所在列的下一列作为当前 列；列；1.5.1 8后后问题60611.5.1 8后后问题2.Las Vegas方法v向量try1.8中存放结果tryi表示第i个皇后放在（i，tryi)位置上vtry1.k称为k-promising是指：若k个皇后的位置(0k 8): (1,try1),(2,try2),(k,tryk)互相不攻击，则称try1.k是k-pr

36、omising的.形式化：对 ，若 有 (式1)则：行冲突：无须考虑，因为第i个皇后放在第i行，故同一行不会有两皇后61621.5.1 8后后问题列冲突：若对任意不同的两行i、j，因为其列数之差不为0，故任意两皇后不可能在同一列上。135对角线冲突： 和 冲突时有：即 。故任两皇后不会在135对角线上冲突。45对角线冲突： 和 冲突时有：即tryi-tryj=i-j故任两皇后不会在45对角线上冲突。综上所述，式1成立时try1.k是k-promising。显然，若k 1，则向量try1.k是k-promising的，对8后问题，解是8-promising的。62631.5.1 8后后问题算法：

37、QueensLv (success)/贪心的LV算法，所有皇后都是随机放置/若Success=true，则try1.8包含8后问题的一个解。col,diag45,diag135；/列及两对角线集合初值为空k 0；/行号repeat /try1.k是k-promising，考虑放第k+1个皇后nb 0；/计数器，nb值为（k+1)th皇后的open位置总数for i i to 8 do /i是列号 if (i col) and (i-k diag45) and (i+k diag135) then /列i对（k+1）th皇后可用，但不一定马上将其放在第i列 nb nb+1； if uniform

38、(1.nb)=1 then /或许放在第i列 j i；/注意第一次uniform一定返回1，即j一定有值1 /endif /endfor63641.5.1 8后后问题if(nb 0) then /nb=0时，第k+1个皇后尚未放好，所有位置不安全。/在所有nb个open位置上，（k+1)th皇后选择位置j的概率为1/nb tryk+1 j；/放置（k+1)th个皇后 col col j ； diag45 diag45 j-k ； diag135 diag135 j+k ； kk+1；/try1.k+1是（k+1)-promisinguntil （nb = 0） or （k=8）；/当前皇后找不

39、到合适的位置或try是 / 8-promising是结束。success （nb0）；64651.5.1 8后后问题v分析设p是成功的概率（一次成功） s：成功时搜索的结点的平均数。（一个皇后放好算是搜索树上的一个结点）e：失败时搜索的结点的平均数。显然s=q（空向量try算在内）p和e理论上难于计算，但实验用计算机可以计算出：p=0.1293e=6.971在重复上述算法，直至成功时(相当于obstinate的时间），所搜索的平均结点数：大大优于回溯法，回溯法约为114个结点才能求出一个解。Ex.证明：当放置（k+1)th皇后时，若有多个位置是开放的,则算法QueensLV选中其中任一位置的概

40、率相等。65661.5.1 8后后问题v改进上述LV算法过于消极：一旦失败，从头再来而回溯法又过于乐观：一旦放置某个皇后，就进行系统回退一步的策略，而这一步往往不一定有效。 折中的方法会更好吗？一般情况下为此。先用LV方法随机地放置前若干个结点，例如k个。然后使用回溯法放置后若干个结点，但不考虑重放前k个结点。若前面的随机选择位置不好，可能使得后面的位置不成功，如若前两个皇后的位置是1、3。随机放置的皇后越多，则后续回溯阶段的平均时间就越少，失败的概率也就越大。66671.5.1 8后后问题折中算法只需将QueensLV的最后两行改为：until nb = 0 or k = stopVegas

41、；if （nb0)then backtrace (k, col, diag45, diag135,success);else success false；stopVegas控制随机放置皇后的个数。 67681.5.1 8后后问题改进后算法的实验室结果：纯回溯时间：40msstepVegas=2 or 3：10ms（平均）纯贪心LV：23ms（平均）结论：一半略少的皇后随机放置较好。StepVegaspset011141141139.6339.6320.87522.5339.6728.230.493113.4815.129.0140.261810.318.7935.150.16249.337.2

42、946.9260.13579.056.9853.570.129396.9755.9380.129396.9753.9368691.5.1 8后后问题-问题1：为什么仅随机放一个皇后，其效果就会大大优于纯回溯方法？-问题2：预先随机选几个皇后放置为好？由于解缺乏规律性（至少在皇后数不等于4k+2，k为某整数时），故求出stepVegas的最优值较难，但是找到一个较好（不一定是最优）的stepVegas还是可以的。12皇后： 69701.5.1 8后后问题在Apple II机器上，20个皇后：确定性的回溯算法：找到第一个解的时间大于2个小时。概率算法，随机地放置前10个皇后：5分半钟找到36个不同

43、的解。后者找一个接比前者大约快1000倍！Ex. 写一算法，求n=1220时最优的StepVegas值。-Obstinate算法在何时无限循环？当问题不存在解时。对于n皇后，要求n=4，即问题至少有一个解存在时，Obstinate算法才有可能结束。 70711.5.2 模模p平方根平方根1.定义1：设p是一个奇素数，若整数x1,p-1且存在一个整数y，使则x称为模p的二次剩余（quadratic residue），若y 1,p-1，则y称为x模p的平方根。v例：63是55模103的平方根，55是模103的二次剩余。2.定义2：若整数 ，且z不是模p的二次剩余，则z是模p的非二次剩余。 7172

44、1.5.2 模模p平方根平方根3.定理1：任何一个模p的二次剩余至少有两个不同的平方根。pf：设x是模p的二次剩余，y是x模p的平方根。因为故只要证 且 就可证明p-y是不同于y的x模p的另一个平方根。p是奇数， ，否则p是偶数。另一方面，72731.5.2 模模p平方根平方根4.定理2：任一模p的二次剩余至多有两个不同的平方根pf：设 a和b是x模p的平方根。即 成立。若k=0，则a=b若k0，则ab不妨设ab. 又 由Th31.7知即 即 ， 也就是说任意两个不同的平方根，均只有b和(p-b)两种不同形式。73741.5.2 模模p平方根平方根5.定理3：1到p-1之间的整数恰有一半是模p

45、的二次剩余（余数）。pf：由定理1和定理2知，任一模p的二次剩余恰有两个不同的平方根，即任取二次剩余 ，只有y和p-y这两个不同的平方根 ，在1,p-1中恰有(p-1)/2对不同的平方根，每对平方根对应的模p的余数必定在1,p-1中，即此区间上恰有(p-1)/2个模p的二次剩余6.定理4：对 ，p是任一奇素数，有且x是模p的二次剩余当且仅当pf：略（可用费马定理）74751.5.2 模模p平方根平方根7.判定x是否为模p的二次剩余？只要利用定理4和计算方幂模 即可。8.已知p是奇素数，x是模p的二次剩余，如何计算x模p的两个平方根？n当 时，两平方根易求，分别是n当 时，没有有效的确定性算法，

46、只能借助与Las Vegas算法。9.Las Vegas算法。用 表示x的两个平方根中较小的一个。nDef：模p乘法（类似于复数乘法），a，b，c，d0,p-175761.5.2 模模p平方根平方根v例：设由定理4可知，7是模53的二次剩余，求7模53的平方根。当省略模53符号是， 计算过程如下：76771.5.2 模模p平方根平方根注：上例中， ， 由定理4知， 是模53的二次非剩余。 同样可知 亦是摸53的二次非剩余。77781.5.2 模模p平方根平方根n若计算知当 时，已知 和 中有一个是模p的二次剩余，而另一个不是二次剩余，会怎样呢？例如，假定 两等式相加得： 两式相减的： 7879

47、1.5.2 模模p平方根平方根n例：通过计算可知为了获得7的一个平方根，需要找唯一的一个证书y使得 ， 。这可使用一个Euclid算法解决n算法：设x是模p的二次剩余，p是素数且 79801.5.2 模模p平方根平方根rootLV(x, p, y, success)/计算ya uniform(1.p-1);/我们并不知道a应取多少if then /可能性很小 success true； y a；else 计算e，d使得 if d=0 then success false；/无法求出 else/c=0 success true； 计算y使得 /算法成功的概率0.5,接近0.5。故平均调用两次即可

48、求得x的平方根。80811.5.3 整数的因数分解整数的因数分解设n是一个大于1的整数，因数分解问题是找到n的一个唯一分解：这里 是正整数，且 均为素数。若n是合数，则至少有一个非平凡的因数(不是1和n本身).n的因数分解问题，即为找n的非平凡因数(设n是一个合数),它由两部分构成：prime(n)判定n是否为素数，可由Monte Carlo算法确定。split(n)当n为分数时，找n的一个非平凡的因数。81821.5.3 整数的因数分解整数的因数分解1.朴素的split算法split(n)/若n是素数,返回1，否则返回找到的n的最小非平凡因数for i2 to do if (n mod i)

49、=0 then return i; /i2 return 1; /返回平凡因数82831.5.3 整数的因数分解整数的因数分解n性能分析： 最坏情况。当n是一个中等规模的整数（如大约50位十进制整数）时，最坏情况的计算时间亦不可接受。n的位数 ，当m=50时，上述算法的时间约为无论是确定性的还是概率的，没有算法能够在多项式时间O(p(m)内分解n。Dixom的概率算法分解n的时间为Note：无论k和b是何正常数，均有：83841.5.3 整数的因数分解整数的因数分解2.合数的二次剩余（模素数到模合数的推广）设n是任一正整数，整数 。若x和n互素，且存在一整数 使 ，则x称为是模n的二次剩余，y

50、称为是模n的平方根。一个模p的二次剩余，当p为素数时，恰有两个不同的平方根，但p为合数，且至少有两个奇素数因子时，不再为真。例： ,注意29应与35互素，才有可能是模35的二次剩余。n定理：若n=pq，p、q是两个互不相同的素数，则每一个模n的二次剩余恰有4个平方根。84851.5.3 整数的因数分解整数的因数分解 上节的测试x是否是模p的二次剩余及找x的平方根的方法是一个有效的算法（指rootLV），当n是一个合数，且n的因子分解给定时，同样存在有效的算法。但n的因数分解未给定时，目前还没有有效算法测试x是否为二次剩余及找x的平方根。3.Dixon因数分解算法。 基本思想，找两个与n互素的整

51、数a和b，使 但 蕴含着 即 假定 ，则n的某一非平凡因子x满足： . n和a+b的最大公因子是n的一个非平凡因子。 例如： 85861.5.3 整数的因数分解整数的因数分解Dixon (n, x, success)/找合数n的某一非平凡因子xif n是偶数 then x2；success true；else for i 2 to do if 是整数 thenx ; success true;return; /n是合数且为奇数，现在知道它至少有两个不同的奇素数因子a，b 两个使得 的整数if then success false；elsex gcd (a+b,n); success true;

52、86871.5.3 整数的因数分解整数的因数分解4.如何确定a和b使 ，来对n因数分解。nDef. k-平滑： 若一个整数x的所有素因子均在前k个素数之中，则x称为k-平滑的。n例如： 是3-平滑的 35=57不是3-平滑的， 7是第四个素数它是4-平滑的，也是5-平滑的当k较小时，k-平滑的整数可用朴素的split算法进行有效的因数分解。Dixom算法可以分为3步确定a和b。87881.5.3 整数的因数分解整数的因数分解Step1：在1n-1之间随机选择xi)若x碰23不与n互素，则已找到n的一个非平凡因子(即为x)ii)否则设 ，若y是k-平滑，则将x和y的因数分解保存在表里。此过程重复

53、直至选择了k+1个互不相同的整数，并且这些整数的平方模n的因数已分解(当k较小时，用split(n)分解）例1：设n=2537，k=7.前7个整数为：2，3，5，7，11，13，17若随机选取x=1769，1240不是7-平滑的88891.5.3 整数的因数分解整数的因数分解下述8个x的平方模n是7-平滑的：89901.5.3 整数的因数分解整数的因数分解Step2：在k+1个等式之中找一个非空子集，使相应的因数分解的积中前k个素数的指数均为偶数(包含0)例2：在上例的8个等式中，有7个积符合要求：n可以证明，在k+1个等式中，至少存在这样一个解，如何找到一个解？构造一个0-1矩阵A：(k+1

54、) k矩阵的行对应k+1个yi，列对应前k个素数。90911.5.3 整数的因数分解整数的因数分解矩阵的行数大于列数。在模2意义下，矩阵的行之间不可能均是相互独立的。例如在例2中，第一个解就是线性相关的：使用Gauss-Jordan消去法可找到线性相关的行。Step3：在step2中找到线性相关的行后：1）令a为相应xi的乘积2）令b是yi的乘积开平方若 ，则只需求a+b和n的最大公因子即可获得n的非平凡因子。91921.5.3 整数的因数分解整数的因数分解例3：对于例2中的第1个解有： a+b=3139和n=2537的最大公因子是43，它是n的一个非平凡因子，对于例2中的第2个解有： 此解不

55、能求因子。实际上 的概率至少为1/292931.5.3 整数的因数分解整数的因数分解5.时间分析如何选择k.1)k越大， 是k-平滑的可能性越大(x是随机选取的)2)k越小，测试k-平滑及因数分解yi的时间越小，确定yi是否线性相关的时间也越少，但 不是k-平滑的概率也就越小。设通常的，当 时较好，此时Dixom算法分裂n的期望时间为 ，成功的概率至少为1/2.93941.6 Monte Carlo算法算法存在某些问题，无论是确定的还是概率的，均找不到有效的算法获得正确的答案。Monte Carlo算法偶然会犯错，但它无论对何实例均能以高概率找到正确解。当算法出错时，没有警告信息。1.基本概念

56、nDef1：设p是一个实数，且1/2p1.若一个MC算法以不小于p的概率返回一个正确的解，则该MC算法称为p-正确，算法的优势（advantage）是p-1/2.nDef2：若一个MC算法对同一实例决不给出两个不同的正确解，则该算法称是相容的（consistent）或一致的。94951.6 Monte Carlo算法算法某些MC算法的参数不仅包括被解的实例，还包括错误概率的上界。因此，这样算法的时间被表示为实例大小及相关可接受的错误概率的函数。n基本思想：为了增加一个一致的，p-正确算法成功的概率，只需多次调用同一算法，然后选择出现次数最多的解。例：设MC(x)是一个一致、75%-correc

57、t的MC算法，考虑下述算法：MC3(x) tMC(x); uMC(x); vMC(x); if t=u or t=v then return t; else return v;95961.6 Monte Carlo算法算法该算法是一致的和27/32-correct的(约84%)pf:相容性（一致性）易证。t、u、v正确的概率为75%=3/4=p(MC是一致的， t、u、v均正确时t=u=v)却为概率为q=1/4.1)若t、u、v均正确，则MC3返回的t正确，此时t=u=v.此概率为：(3/4)32)若t、u、v恰有两个正确则MC3返回的 此概率为：3)若t、u、v恰有一个正确，若v正确，则MC

58、3返回正确答案，此概率为：96971.6 Monte Carlo算法算法严格的说，当v正确，且错误的t和v不相等时，才有可能成功，因此MC3成功的概率为： 多运行2次（共3次）nTheorem：设+0是多小，均可通过反复调用来扩大其优势，使得最终的算法具有可接受的错误概率，使之任意小（选定的）。pf：设 是调用MC(x)的次数。当重复调用MC(x)算法n次时，若正确解至少出现m次，则可认为新算法找到了正确解，因此其出错概率至多为：98991.6 Monte Carlo算法算法991001.6 Monte Carlo算法算法由此可知，重复MC(x) n次成功的概率至少为1-。n例：假定有一个一致

59、的5%赢面的MC算法，若希望获得一个错误概率小于5%的算法，则相当于将55%-correct的算法改造成95%-correct的算法。上述定理告诉我们：大约要调用MC算法600次才能达到相应的程度（在同一实例上）。上述证明太过粗略，更精确的证明表示：如果重复调用一个一致的，(1/2+)-correct的MC算法m-1次，则可得到一个(1-)-correct的最终算法，其中：1001011.6 Monte Carlo算法算法重复一个算法几百次来获得较小的出错概率是没有吸引力的，幸运的，大多数MC算法实际上随着重复次数的增加，正确概率增长会更快。nDef：(偏真算法)为简单起见，设MC(x)是解某

60、个判定问题，对任何x，若当MC(x)返回true时解总是正确的，仅当它返回false时才有可能产生错误的解，则称此算法为偏真的(true-biased)。显然，在偏真的MC算法里，返回频数最高的解是愚蠢的，因为一次true超过任何次数的false.对于偏真的MC算法，重复调用4次，就可将55%-正确的算法改进到95%正确。6次重复就可得到99%正确的算法，且对p1/2的要求可以放宽到p0即可。1011021.6 Monte Carlo算法算法Def：(偏y0算法)更一般的(不在限定是判定问题)，一个MC是偏y0的(y0是某个特定解)，如果存在问题实例的子集X使得：若被解实例 ，则算法MC(x)

61、返回的解总是正确的(无论返回y0还是非y0)若 ，正确解是y0 ，但MC并非对所有这样的实例x都返回正确解。显然， y0是必须知道的，但无需测试x是否是X的成员，洗面解释若算法返回y0时，它总是正确的。即算法返回y0时总是正确的，返回非y0时以p为概率正确。1021031.6 Monte Carlo算法算法设MC是一个一致的、p-correct和偏y0的蒙特卡洛算法，x是一个实例，y是MC(x)返回的解，可分为如下2种情形讨论：case1：n若 ，则算法MC总是返回正确解，因此y0确实是正确的。n若 ，算法返回的正确解必定是y0这两种情况均可得到结论： y0是一个正确解。case2：n若 ，则

62、y是正确解。n若 ，因为正确解是y0 ，故y是错误解，此出错概率不超过1-p。1031041.6 Monte Carlo算法算法若调用MC(x)k次所返回解依次是 ，则： (1) 若存在i使 ，则前面的讨论已知，它是一个正确解(yi是正确解).(2) 若存在 使 ，由于MC是一致的，故必有 。因此正确解仍是y0 。(3) 若对所有的i均有 ，但 ，则y0仍有可能是正确解。实际上，若 ，则y0是正确解，此时y是错误的，其错误概率不超过 。由上面的讨论可知，重复调用一个一致的，p-正确的，偏y0的MC算法n次，可得到一个 -正确的算法(对偏真算法亦适合).1041051.6.1 主元素主元素问题D

63、ef：设T1.n是n个元素的数组，若T中等于x的元素个数大于n/2(即 )，则称x是数组T的主元素。(Note：若存在，则只可能有1个主元素)1.判T是否有主元素maj(T)/测试随机元素 是否为T的主元素 iuniform(1.n); xT i ; k0; for j1 to n do if T j =x then kk+1; return (kn/2);1051061.6.1 主元素主元素问题n若算法返回true，则T含有主元素，所选择的元素即为主元素，算法一定正确。n若算法返回false，则T仍有可能含有主元素，只是所选元素x不是T的主元素而已。n若T确实包含一个主元素，则随机选择到一个

64、非主元的概率小于1/2，这是因为主元素占T的一半以上。n算法是一个偏真的1/2正确的算法：1061071.6.1 主元素主元素问题若maj返回true，则T必有主元素，解一定正确。因为随机选中主元素的概率大于1/2，故改算法是1/2-correct.若maj返回false，则T可能没有主元素。当然，若T没有主元素，则必返回false。 实际使用时，50%的错误概率是不可容忍的。而对有偏算法，可以通过重复调用技术来使错误概率降低到任何值。maj2(T) if maj(T) then return true; /1次成功 else return maj(T); /调用2次 1071081.6.1

65、主元素主元素问题2.分析： 1)若T无主元素，则maj每次均返回false，maj2亦肯定返回false。 2)若T有主元素，则：第一次调用maj返回真的概率是p1/2，此时maj2亦返回真。第一次调用maj返回fasle的概率为1-p，第2次调用maj仍以概率p返回true，此时maj2亦返回真，此时的概率为:(1-p)p.总结：当T有主元是，maj返回真的概率是：p+(1-p)p =1-(1-p)23/4.即：maj2是一个偏真的3/4正确的MC算法。1081091.6.1 主元素主元素问题1.算法改进错误的概率能够迅速减小，主要是因为重复调用maj的结果是相互独立的，即：对同一实例T，某

66、次maj返回fasle，并不会影响继续调用返回true的概率。因此，当T含有主元素时，k次重复调用maj均返回false的概率小于2-k。另一方面，在k次调用中，只要有一次maj返回真，即可判定T有主元素。1091101.6.1 主元素主元素问题n当需要控制算法出错概率小于0时，相应算法调用maj的次数为： majMC (T, ) k ; for i 1 to k do if maj (T) then return true; /成功 return false; /失败，可能错误该算法的时间为 。注意，这里只是用此问题来说明MC算法，实际上对于判定主元素问题存在O(n)的确定性算法。11011

67、11.6.2 素数素数测定定(数的素性数的素性测定定)判定一个给定的整数是否为素数，到目前为止尚未找到有效的确定性活LasVegas算法。1.简单的概率算法。prime(n) d uniform(2. );return n若返回false，则算法幸运地找到了n的一个非平凡因子，n为合数。n若返回true，则未必是素数。实际上，当n是合数是，prime亦以高概率返回true。1111121.6.2 素数素数测定定(数的素性数的素性测定定)例如：prime在251内随机选一整数d，只有d=43(概率为2%)时算法返回false(结果正确).当d43，算法返回true(概率为98%)(结果错误)当n

68、增大时，情况更差。2.Fermat小定理若n是素数，则对所有1an-1的整数a，有n变换命题：若整数n和a满足1an-1，且 ，则n不是素数。1121131.6.2 素数素数测定定(数的素性数的素性测定定)n素性测定算法：Fermat(n) a uniform(1.n-1); if then return true; /未必正确 else return false；/正确，一定是合数 nFermat定理的逆命题成立吗？当n为合数，对1an-1，有 吗？若成立，则只要n是合数， 均有 ，否则n为素数。1131141.6.2 素数素数测定定(数的素性数的素性测定定)显然不成立：若是 时呢？设n=1

69、5(合数)，3.素性伪证据一个满足2an-2且 的整数a称为合数n的素性伪证据。若将Fermat测试改为从2n-2之间随机选a，则只有选到一个伪证据时，对合数的测试失败(返回true).1141151.6.2 素数素数测定定(数的素性数的素性测定定)n伪证据有多少？总体情况是伪证据相当少。1000之内的奇合数测试误差概率99.9965%一般地，对 ，存在无穷多个合数，使得Fermat测试都不是p-正确的。以前将Fermat测试重复固定次数，并不能将误差降到任意小的内。1151161.6.2 素数素数测定定(数的素性数的素性测定定)4.Fermat测试改进n强伪素数设n是一个大于4的奇整数，s和

70、t是使得 的正整数，其中t为奇数，设B(n)是如下定义的整数集合： 当且仅当2an-2且 当n为素数时， ，均有当n为合数时，若 ，则称n为一个以a为底(基)的强伪素数，称a为n素性的强伪证据。n为素数，说明它对所有底均为强伪素数。1161171.6.2 素数素数测定定(数的素性数的素性测定定)Btest(a，n)/n为奇数 ，返回 。即返回真说明n是强伪素数s0； t n-1； /t开始为偶数 repeat s+；t t2；until t mod 2 = 1； /n-1=2st t为奇数 x at mod n；if x=1 or x=n-1 then return true； /满足or。f

71、or i 1 to s-1 do x x2 mod n； if x=n-1 then return true； /满足，return false；1171181.6.2 素数素数测定定(数的素性数的素性测定定)例：计算执行for循环4次(只要3次)。1181191.6.2 素数素数测定定(数的素性数的素性测定定)n强伪证据数目比伪证据数目少很多。强伪证据是伪证据，但反之不然。例：4是15的素性的伪证据但它不是一个强伪证据561有318个伪证据，但只有8个是强伪证据。小于1000的奇合数中，随机选到一个强伪证据的概率小于1%更重要的是，对任一奇合数，强伪证据比例都很小。1191201.6.2 素

72、数素数测定定(数的素性数的素性测定定)nTh1.设n是任一大于4的奇素数。若n是素数，则若n是合数，则即，当n为合数是，强伪证据数目3/4。(正确的概率75%)当n为素数时，Btest总返回真。nMiller-Rabin测试MillRab(n) /奇n4，返回真时表示素数，假表示合数auniform(2.n-2);return Btest(a,n); /测试n是否为强伪素数/该算法是3/4-正确，偏假的。1201211.6.2 素数素数测定定(数的素性数的素性测定定)说明：返回真时，它可能是伪素数，但是随机选到的强伪素数概率1/4，出错概率1/4返回假时，它必正确。若n是素数，有定理1知，它必

73、定返回真，任何n必定是一个合数。RepeatMillRob(n,k) for i 1 to k doif MillRob(n) =false thenreturn false; /一定是合数return true；1211221.6.2 素数素数测定定(数的素性数的素性测定定)-重复调用k次返回true，若错误表示连续k次碰到强伪证据，概率(1/4)k。只要取k=10，错误概率 ABC，必正确。若算法返回true，偏假的，1/2-correct.1291301.6.3 矩矩阵乘法乘法验证n改进RepeatGoodProduct( A, B, C, n, k) for i1 to k do /重复k次if GoodProduct(A, B, C, n) = false thenreturn false;/偏假的，有一次假即可返回return true;/此方法是偏假的(1-2-k)-correct的当k=10，0.99-正确。k=20，出错概率60)，它远远快与确定行算法。1311321.6.3 矩矩阵乘法乘法验证n习题PrintPrimes /打印1万以内的素数 print 2，3； n 5； repeatif RepeatMillRab(n, ) then print n;n n+2; until n=10000;与确定性算法相比较，并给出10010000以内错误的比例。132