下载文档原格式
详解各种随机算法之前将的算法都是确定的，即对于相同的输⼊总对应着相同的输出。
但实际中也常常⽤到不确定的算法，⽐如随机数⽣成算法，算法的结果是不确定的，我们称这种算法为（随机）概率算法，分为如下四类：1、数值概率算法⽤于数值问题的求解，通常是近似解2、蒙特卡洛算法Monte Carlo能得到问题的⼀个解，但不⼀定是正确解，正确的概率依赖于算法运⾏的时间，算法所⽤的时间越多，正确的概率也越⾼。
求问题的准确解；3、拉斯维加斯算法 Las Vegas不断调⽤随机算法求解，直到求得正确解或调⽤次数达到某个阈值。
所以，如果能得到解，⼀定是正确解。
4、舍伍德算法 Sherwood利⽤随机算法改造已有算法，使得算法的性能尽量与输⼊数据⽆关，即平滑算法的性能。
它总能求得问题的⼀个解，且求得的解总是正确的。
随机数概述计算机产⽣的随机数都是伪随机数，通过线性同余法得到。
⽅法：产⽣随机序列d称为种⼦；m取值越⼤越好；m，b互质，常取b为质数；案例伪随机数在实际编程中，我们使⽤rand()函数来产⽣随机数，rand()函数返回0到⼀个最⼤值之间的⼀个随机数。
#include#include#include//产⽣[0,100)的随机数void GenerateRandomNumber(){for(int i=0;i10;i++){printf('%-4d',rand()%100);//产⽣[0,m)的随机数}printf('\n');}int main(){GenerateRandomNumber();return 0;}运⾏代码，输出：41 67 34 0 69 24 78 58 62 64如果我们重复运⾏代码就会发现，每次的输出结果都是这个序列。
这就是因为rand产⽣的随机序列是伪随机序列。
解决⽅法是：使⽤当前的时间作为随机种⼦。
时间作为随机种⼦在GenerateRandomNumber()函数开头加⼊下⾯⼀条语句。
算法设计的方法算法设计是计算机科学和软件工程领域的一项重要任务，它涉及为解决特定问题而创建高效、正确和可行的计算步骤。
算法设计方法是一套策略、技巧和方法，帮助程序员和研究人员开发有效的算法。
以下是一些常用的算法设计方法：1. 暴力法（Brute Force）：尝试所有可能的解决方案，直到找到最优解。
这种方法通常适用于问题规模较小的情况。
2. 贪心法（Greedy Algorithm）：每一步都选择局部最优解，期望最终获得全局最优解。
贪心法容易实现，但并不总是能够得到最优解。
3. 分治法（Divide and Conquer）：将问题分解为若干个较小的子问题，然后递归地解决子问题，并将子问题的解合并为原问题的解。
分治法适用于具有自相似结构的问题。
4. 动态规划（Dynamic Programming）：将问题分解为重叠子问题，并通过自底向上或自顶向下的方式逐一解决子问题，将已解决子问题的解存储起来，避免重复计算。
动态规划适用于具有最优子结构和重叠子问题的问题。
5. 回溯法（Backtracking）：通过递归搜索问题的解空间树，根据约束条件剪枝，回溯到上一层尝试其他解。
回溯法适用于约束满足性问题，如八皇后问题、图的着色问题等。
6. 分支界限法（Branch and Bound）：在搜索解空间树时，通过计算上界和下界来剪枝。
分支界限法适用于求解整数规划和组合优化问题。
7. 随机化算法（Randomized Algorithm）：通过随机选择解空间中的元素来寻找解决方案。
随机化算法的优点是简单、易于实现，但可能需要多次运行才能获得最优解。
8. 近似算法（Approximation Algorithm）：在问题的最优解难以找到或计算代价过高时，提供一个接近最优解的解。
近似算法可以提供一个性能保证，即解的质量与最优解之间的差距不会超过某个阈值。
9. 并行和分布式算法（Parallel and Distributed Algorithm）：将问题的计算分布到多个处理器或计算机上，以提高计算速度和效率。
盲盒程序概率设计算法需要考虑以下几个因素：
基础概率：每个盲盒中包含的物品的数量和价值是不同的。
在算法中，可以根据每个物品的价值和数量，设定一个基础概率，即每个盲盒中包含该物品的概率。
稀有度：对于一些特别稀有的物品，可以设置一个更高的概率，以增加用户获得该物品的难度。
购买行为分析：算法还可以根据用户的购买行为进行分析，例如用户更倾向于购买哪种类型的盲盒，或者用户在购买盲盒时更倾向于选择哪些物品，这些都可以作为调整概率的依据。
抽奖机制：在抽奖机制方面，可以设计成每次抽奖都有一定的概率获得不同的物品。
同时，为了保证公平性，可以设定每个用户在一段时间内只能参加一次抽奖。
奖品兑换算法：当用户中奖后，需要兑换奖品时，奖品兑换算法可以根据用户中奖的情况，自动计算出用户应该获得的奖品和相应的兑换码等信息，并提示用户进行兑换。
该算法的实现需要考虑到奖品的库存情况和中奖的数量，以确保兑换过程的准确性和及时性。
随机算法：随机算法是盲盒小程序的核心算法之一，它能够根据用户的需求，从预设的奖品列表中随机选取一个或多个奖品，并分配给用户。
随机算法的实现需要考虑到用户中奖的概率和奖品的概率分布，以保证抽奖过程的公平性和随机性。
抽奖结果展示算法：当用户完成抽奖后，需要将中奖信息展示给用户。
该算法的实现需要考虑到展示的效果和用户体验，以增强用户的参与感和满意度。
以上是盲盒程序概率设计算法的主要步骤，当然在实际应用中还需要根据具体情况进行调整和完善。
随机化均匀设计遗传算法随机化均匀设计遗传算法是一种模拟自然选择与遗传进化的数学优化算法，常用于解决复杂难以求解的多变量非线性问题。
其主要应用领域包括机器学习、数据挖掘、智能优化等领域。
下面，就随机化均匀设计遗传算法的几个方面来进行详细的介绍。
一、背景与原理随机化均匀设计遗传算法是在传统的遗传算法的基础上，通过引入均匀设计策略和随机化思想，来提高算法的效率和精度。
该算法原理和基本流程如下：1. 初始化种群：随机产生一批个体，用于初始化种群。
2. 计算适应度：根据适应度函数，对每个个体进行评估。
3. 选择：通过轮盘赌选择、竞赛选择等方法，选出适应度高的个体。
4. 交叉：将选出的个体进行交叉操作，产生新的个体。
5. 变异：对新个体进行突变操作，引入随机性，使种群多样性增加。
6. 更新种群：用新的个体替换掉原来的个体，形成新的种群。
7. 迭代：重复执行2-6步，直至满足停止条件。
二、应用领域随机化均匀设计遗传算法主要应用领域包括：1. 机器学习：通过随机化均匀设计遗传算法，可以对机器学习算法参数进行优化，以提高机器学习的准确性和效率。
2. 数据挖掘：通过随机化均匀设计遗传算法，可以对数据挖掘中的特征选择、分类、聚类等问题进行求解，以提高数据挖掘的效果。
3. 智能优化：随机化均匀设计遗传算法具有全局搜索优化能力，可以应用于各种优化问题，如函数优化、组合优化等。
三、优点与缺点优点：1. 全局搜索能力强：随机化均匀设计遗传算法可以进行全局搜索，避免局部最优解。
2. 自适应性好：由于遗传算法引入了变异和交叉操作，可以使种群自适应性更强，能够在搜索过程中自我调整。
3. 并行计算能力强：随机化均匀设计遗传算法的并行计算能力强，可以应用于高性能计算。
缺点：1. 迭代次数不易确定：由于随机化均匀设计遗传算法的迭代次数取决于停止条件的设置，因此其收敛速度不易预测。
2. 取决于编码方式：随机化均匀设计遗传算法的算法效果与编码方式密切相关，因此需要根据具体问题选择合适的编码方式。
计算机算法的设计与分析计算机算法是计算机科学中非常重要的概念，它是解决问题和完成任务的步骤和规则。
在计算机科学领域，算法的设计与分析被广泛应用于各种领域，如数据结构、人工智能、图像处理等。
本文将重点探讨计算机算法的设计与分析，并介绍一些常见的算法。
一、算法的定义和特点算法是指解决问题的有限步骤序列，其中每个步骤具有明确的目标和执行顺序。
算法的设计与分析是通过选择和组合适当的数据结构和算法，以解决实际问题和优化计算性能。
合理设计的算法应具备以下特点：1. 正确性：算法能够解决问题，并给出正确的结果。
2. 可读性：算法的结构和步骤清晰易懂，容易被其他人理解和阅读。
3. 高效性：算法的执行时间和所需资源尽可能少，以提高计算效率。
4. 通用性：算法能够适用于不同规模和类型的问题，并具有良好的扩展性。
二、算法的设计方法在设计算法时，可以采用不同的方法和策略。
下面介绍几种常见的算法设计方法：1. 分治法：将大问题划分成若干个相同或类似的小问题，逐个解决小问题，最后将结果合并。
2. 动态规划：将复杂问题划分成一系列相互联系的子问题，通过解决子问题来求解原问题。
3. 贪心算法：每次选择当前看起来最优的策略来解决问题，不考虑后续可能产生的影响。
4. 回溯法：采用试错的思想，尝试所有可能的答案，当发现不满足条件时，进行回溯重新尝试。
5. 随机算法：通过随机选择的方式求解问题，时间复杂度通常较高。
三、算法的复杂性分析算法的复杂性分析是评估算法的执行时间和所需资源的一种方法。
一般来说，常用的复杂性分析有时间复杂性和空间复杂性。
1. 时间复杂性：衡量算法执行所需的时间。
常见的时间复杂性表示方法有大O记法，表示算法执行时间的上限。
2. 空间复杂性：衡量算法执行所需的额外内存空间。
常见的空间复杂性表示方法也是大O记法，表示算法所需额外内存空间的上限。
通过复杂性分析，可以选择适当的算法来解决特定问题，并评估算法的性能。
四、常见的算法以下是几种常见的计算机算法：1. 排序算法：包括冒泡排序、选择排序、插入排序、快速排序等，用于按照一定规则对数据进行排序。
随机化算法（4）—拉斯维加斯（LasVegas）算法已出连载：正⽂：悟性不够，这⼀章看代码看了快⼀个上午，才理解。
上⼀章讲过《》，但是他的有点是计算时间复杂性对所有实例⽽⾔相对均匀，⽽其平均时间复杂性没有改变。
⽽拉斯维加斯算法怎么显著改进了算法的有效性。
的⼀个显著特征是它所作的随机性决策有可能导致算法找不到所需的解。
因此通常⽤⼀个bool型函数表⽰拉斯维加斯算法。
void Obstinate(InputType x, OutputType &y){// 反复调⽤拉斯维加斯算法LV(x, y)，直到找到问题的⼀个解bool success= false;while (!success)success = LV(x,y);}考虑⽤拉斯维加斯算法解决：对于n后问题的任何⼀个解⽽⾔，每⼀个皇后在棋盘上的位置⽆任何规律，不具有系统性，⽽更象是随机放置的。
由此容易想到下⾯的拉斯维加斯算法。
在棋盘上相继的各⾏中随机地放置皇后，并注意使新放置的皇后与已放置的皇后互不攻击，直⾄n个皇后已相容地放置好，或已没有下⼀个皇后的可放置位置时为⽌。
注意这⾥解决的是找到其中⼀个⽅法，求不是求出N皇后的全部解。
这⾥提前说明⼀下，否则不好理解。
接下来的这个⽤Las Vegas算法解决N皇后问题，我们采⽤的是随机放置位置策略和回溯法相结合，具体就是⽐如⼋皇后中，前⼏⾏选择⽤随机法放置皇后，剩下的选择⽤回溯法解决。
这个程序不是很好理解，有的地⽅我特别说明了是理解程序的关键，⼤家看时⼀定要认真了，另外，王晓东的书上先是⽤单纯的随机法解决，⼤家可以先去理解书上这个例⼦。
然后再来分析我这个程序。
不过那本书上关于这⼀块错误⽐较多，⼤家看时要注意哪些地⽅他写错了。
拉斯维加斯算法解决N皇后代码：依然⽤到了RandomNumber.h头⽂件，⼤家可以去看下，我就不贴出来了。
剩下部分的代码：注意QueensLV()函数是这个程序的精髓所在。
基于随机游走算法的推荐系统设计随着互联网的迅速发展，推荐系统成为了互联网行业中不可或缺的一部分。
推荐系统的主要作用是根据用户的历史行为数据，或者是与用户兴趣相关的信息，向用户推荐他们可能感兴趣的内容或商品。
推荐系统的优秀设计可以提升用户体验，增加转化率，从而为企业带来收益。
而随机游走算法则是目前比较流行的一种推荐算法。
一、推荐系统的现状与方法目前，推荐系统被广泛应用于各个领域，比如电商、视频网站、社交媒体等。
推荐系统可以又分为基于内容的推荐、协同过滤推荐、基于深度学习的推荐等等。
其中，协同过滤推荐是比较主流的一种方法，它将用户与物品之间的关系建模为一个矩阵，然后通过相似度计算或者矩阵分解等方法来推荐物品。
但是协同过滤推荐也有其不足之处，比如冷启动问题、数据稀疏性等。
二、随机游走算法的基本原理随机游走算法是一种基于图的推荐算法。
它的基本思想是在图中进行随机游走，利用节点之间的连接关系来推荐节点。
在随机游走中，每个节点都有一定的概率被访问到，而这个概率正是节点的重要性或者叫做影响力。
可以将所有节点的影响力计算出来，从而得到一个代表节点重要性的向量，用于推荐。
随机游走算法可以分为基于无权图的Random Walk、基于权图的Personalized PageRank等。
三、基于随机游走算法的推荐系统设计在基于随机游走算法的推荐系统设计中，主要包括以下几个步骤：1. 数据预处理：对用户行为数据进行清洗和去噪，构建用户行为图。
2. 建图：将用户行为图转化为有向图，每个用户和物品都是一个节点。
如果用户A购买了商品B，那么在图上就可以建立从用户A到商品B的一条边。
3. 随机游走：利用随机游走算法计算节点的影响力，并将影响力作为节点的权重。
4. 排序：根据节点的影响力进行排序，从而推荐出用户可能感兴趣的物品。
5. 评估与优化：根据用户的反馈进行系统评估和算法优化，从而提高推荐准确率和用户体验。
四、随机游走算法的优点和不足优点：1. 具有良好的可解释性。
数学中的随机算法设计与分析随机算法是指在算法的执行过程中引入随机性的一种计算方法。
随机算法在计算机科学和数学领域中广泛应用，它能够解决许多与随机性相关的问题，如概率、统计、优化等。
本文将介绍数学中的随机算法设计与分析，并探讨其应用领域和挑战。
一、随机算法的定义和基本思想随机算法是一种通过引入随机性来解决问题的计算方法。
它与确定性算法不同，其执行结果在相同的输入情况下可能会有不同的输出。
随机算法的基本思想是利用随机数生成器生成一系列的随机数，并根据这些随机数进行计算和决策。
随机算法通常包括以下几个步骤：1. 随机数生成：通过随机数生成器生成随机数序列。
2. 初始化：对算法进行初始化，使其获得一个合理的起始状态。
3. 迭代计算：根据生成的随机数和当前状态进行计算，得到新的状态。
4. 终止条件判断：判断是否满足终止条件，如果满足则停止计算，否则返回步骤3。
二、蒙特卡罗方法蒙特卡罗方法是一种以随机采样的方式来解决问题的数值计算方法。
其基本思想是通过随机采样产生问题的一个随机样本，并利用这个样本的统计特征来估计问题的解。
蒙特卡罗方法的应用领域非常广泛，如计算机图形学中的光线跟踪算法、金融工程中的期权定价、物理学中的数值模拟等等。
该方法的优势在于能够处理复杂的数学模型和实际问题，但也存在着计算复杂度高、采样误差等问题。
三、马尔可夫链马尔可夫链是一种随机过程，具有马尔可夫性质。
它的基本思想是当前状态只与前一时刻的状态相关，与之前所有的状态无关。
在随机算法中，马尔可夫链常用于模拟和优化问题。
通过构建一个马尔可夫链模型，可以利用其平稳分布进行采样和估计。
马尔可夫链蒙特卡罗方法以及马尔可夫链蒙特卡罗近似算法是利用马尔可夫链进行随机采样和近似计算的重要技术。
四、遗传算法遗传算法是一种基于生物进化原理的优化算法。
其基本思想是通过模拟生物进化过程中的选择、交叉和变异等操作来搜索最优解。
遗传算法在解决复杂优化问题方面具有很大的优势。
随机算法与素数测试实验1.实验要求（1）分别用KMP、Monte Carlo和Las Vegas算法编制3个程序，并随机生成不小于5000对、长度很长、且长度不等的01串X和Y（三个程序处理相同的串），然后统计算法的执行时间、Monte Carlo算法的出错率，并根据运行结果对三种算法进行深入的比较。
（2）利用素数判断法产生一定数量的随机素数（长度比Y串至少少4位且数值不超过200万），并把这些素数用数组保存起来，执行子串匹配随机算法时，每次随机从中取一个素数后再运行子串匹配随机算法，三个程序都要记录对给定字符串的算法运行时间。
2.算法分析与设计（1）综述：本次实验首先对KMP、Monte Carlo和Las Vegas三种随机算法理解思想和设计思路，完成对应的算法设计和代码实现（开始时素数是任意指定来对算法进行判断）。
而后实现Miller-Rabin素数判断法，进而在三种随机算法运行比较前利用Miller-Rabin算法随机产生一定量（这里取6000对）对素数存在数组里面。
最后随机生成指定长度的两个字符串，从素数存储数组里面取出素数对三种随机算法进行测试和比较。
（2）Monte Carlo算法、Las Vegas算法以及Miller-Rabin素数判断算法思路和设计同课件。
（3）KMP算法设计思路:KMP算法是在简单直接匹配算法的基础上改进的。
假设两个字符串主串S和模式串T的比较，成功的情况下返回匹配成功的下标，不成功的情况下则要确定下一次匹配开始的位置（这个位置主要有一个数组next[j]来确定，next[j]数组的值表示字符串T[0，1，，，j-1]中最长后缀的长度等于相同字符序列的前缀，KMP算法中求出next[j]数组是关键），匹配不成功的情况下，若next[j]>=0,则将模式串T的指针移动到next[j]处进行比较；若next[j]=-1则将S串指针右移一位并且T串指针置为0继续进行比较。
算法之中next[j]数组的求值是个关键的地方。
可以根据递归的思想来求解，思路是：首先next[0]=-1，然后如果T[j]=T[k]，则有T[0...k]=T[j-k...j]即有next[j+1]=next[j]+1=k+1，再有T[j]!=T[k]，k=next[k]。
如此可以求出next[j]数组的所有值。
求出之后就可以利用其执行KMP算法。
3.算法流程图由于其他算法课件或教材中已有，这里只给出KMP 算法的流程图。
YNYNYNN开始 初始化并获取next[]数组值 记录型变量i,j 置0，index 置1 判断S[i] 和T[j]是否结束？ 判断S[i] =T[j]？ i++,j++ index = index +j -next[j] next[j] != -1 ? i++,j++ ++i,j=0 T[j]是否结束？ 返回-1 返回index 下标 结束4.实验结果与分析（1）首先，随机生成20万与30万之间、30万与40万之间、40万与50万之间、100万与200万之间的随机素数各十个。
程序结果如下：（2）然后，三种随机算法运行的结果分析和全方位的比较：情况1：随机产生素数的范围：（2*n*n，2*n*n*m）主串长度子串长度KMP MonteCarlo LasVegas 错误率程序截屏50 10 0.01 0.007 0.008 0.05% 01.jpg 50 30 0.015 0.01 0.01 0.15% 02.jpg 50 50 0.018 0.013 0.013 0.016% 03.jpg 500 50 0.075 0.078 0.075 0.05% 04.jpg 500 100 0.08 0.079 0.082 0.05% 05.jpg 500 300 0.117 0.101 0.102 0.066% 06.jpg 500 500 0.151 0.123 0.123 0% 07.jpg 5000 100 0.612 0.671 0.688 0.033% 08.jpg 5000 500 0.688 0.711 0.737 0% 09.jpg 5000 1000 0.786 0.76 0.779 0% 10.jpg 5000 2500 1.032 0.926 0.931 0% 11.jpg50000 1000 6.449 7.094 7.258 0.01% 12.jpg 50000 5000 7.3 7.901 7.765 0% 13.jpg 50000 10000 8.021 8.384 8.282 0% 14.jpg 50000 30000 12.388 11.085 11.803 0% 15.jpg情况2：随机产生的素数范围：（2，2*n*n*m）主串长度子串长度KMP MonteCarl LasVegas 错误率程序截屏50 10 0.01 0.007 0.00 0.38% 16.jpg 50 30 0.014 0.012 0.011 0.43% 17.jpg 50 50 0.025 0.014 0.014 0.05% 18.jpg 500 50 0.069 0.072 0.072 6.98% 19.jpg 500 100 0.079 0.078 0.078 6.02% 20.jpg 500 300 0.114 0.101 0.101 3.25% 21.jpg 500 500 0.149 0.124 0.125 0.07% 22.jpg 5000 100 0.6 0.555 0.678 34.52% 23.jpg 5000 500 0.663 0.611 0.719 33.7% 24.jpg 5000 1000 0.751 0.702 0.78 32.27% 25.jpg 5000 2500 1.048 0.92 0.977 23.32% 26.jpg 50000 1000 6.042 2.352 6.895 92.38% 27.jpg 50000 5000 6.685 3.24 7.381 91.45% 28.jpg 50000 10000 7.451 4.421 7.819 88.9% 29.jpg 50000 30000 11.085 8.814 10.021 77.57% 30.jpg结果分析：○1首先从素数的选取上Monte Carlo的错误率有很大的差距，当随机出的素数较小时，Monte Carlo的错误率明显过高；当随机出的素数越大，Monte Carlo 的错误率可以接近于0。
这说明素数的选择对Monte Carlo的错误率有很大的影响。
○2从运行时间上来看，KMP算法的时间一般高于Monte Carlo和Las Vegas 算法的运行时间，而Las Vegas 算法由于在Monte Carlo算法判定匹配成功情况下要去验证是否真的匹配成功，故Las Vegas算法时间比Monte Carlo算法时间略高一点。
○3从字符串长度的角度来看，字符串越长每个算法时间运行时间越长；此外，在素数选择较大的情况下，随着字符串的长度增加，Monte Carlo算法错误率也相应的降低；在素数选择小的情况下，随着字符串长度的增加，Monte Carlo算法错误率反而越来越高。
5.附录#include <iostream>#include <time.h>#include <math.h>#include <iomanip>#define SIZE 6000using namespace std;bool isPrime(int n); //判断是否为素数函数bool strcmpos(char*,char*,int,int);//判断字符串是否相等int Expmod(int,int,int); //求am(mod n)函数bool Witness2(int a,int n,int q,int m);//证据判断函数bool Miller_Rabin(int n); //Miller-Rabin素数判断函数int PrimeRand(int m); //随机生成一个小于m的素数int PrimeRand(int min,int max); //随机生成一个min和max之间的素数char *StrRand(char*,int length); //随机生成一个0-1串函数void getNext(const char*,int*); //KMP算法求串的模式值next[]数组的函数int KMP(const char*,const char*);//KMP算法匹配函数int getIP(char *,int,int); //MonteCarlo算法取指纹函数int MonteCarlo(char*,char*,int); //MonteCarlo算法实现函数int LasVegas(char*,char*,int); //LasVegas算法实现函数int main(){int i,j,miscount=0;int re_kmp[SIZE],re_mon[SIZE],re_las[SIZE];srand(time(NULL)); //当前时间产生随机数clock_t time_s,time_e;//声明两个变量分别记录算法的开始和结束时间int len_pri,len_sub; //声明两个变量分别记录主串和子串的长度//随机生成组主串和子串cout<<"please input the length of primary string : ";cin>>len_pri;cout<<"please input the length of substring : ";cin>>len_sub;char **str_pri = new char*[SIZE];char **str_sub = new char*[SIZE];for(i =0;i < SIZE;i++){str_pri[i] = new char[len_pri+1];str_sub[i] = new char[len_sub+1];StrRand(str_pri[i],len_pri);StrRand(str_sub[i],len_sub);// cout<<str_pri[i]<<endl;// cout<<str_sub[i]<<endl;}//随机生成素数int *prime = new int[SIZE];for (i = 0;i < SIZE;i++){prime[i] = PrimeRand(2,2*len_pri*len_pri*len_sub);// cout<<"素数："<<prime[i]<<endl;}//KMP方法time_s = clock();for (j = 0;j < SIZE;j++){re_kmp[j] = KMP(str_pri[j],str_sub[j]);// cout<<"the result of KMP : "<<re_kmp[j]<<endl;}time_e = clock();cout<<"the runtime of KMP : "<<(double)(time_e-time_s)/CLOCKS_PER_SEC<<"s"<<endl;//MonteCarlo方法time_s = clock();for (j = 0;j < SIZE;j++){re_mon[j] = MonteCarlo(str_pri[j],str_sub[j],prime[j]);// cout<<"the result of MonteCarlo :"<<re_mon[j]<<endl;}time_e = clock();cout<<"the runtime of MonteCarlo :"<<(double)(time_e-time_s)/CLOCKS_PER_SEC<<"s"<<endl;//LasVegas方法time_s = clock();for (j = 0;j < SIZE;j++){re_las[j] = LasVegas(str_pri[j],str_sub[j],prime[j]);// cout<<"the result of LasVegas :"<<re_las[j]<<endl;}time_e = clock();cout<<"the runtime of LasVegas : "<<(double)(time_e-time_s)/CLOCKS_PER_SEC<<"s"<<endl;//失败率计算for (j = 0;j < SIZE;j++){if(re_mon[j] != re_las[j]) miscount++;}double failure = (double) miscount/SIZE;cout<<"the error rate of MonteCarlo :"<<failure*100<<"%"<<endl;//随机产生20万与30万之间、30万与40万之间、40万与50万之间、100万与200万之间的随机素数各十个。
