文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 计算机软件及应用 > MillerRabin算法和Las Vegas,Monte Carlo以及KMP算法
侵权投诉

MillerRabin算法和Las Vegas,Monte Carlo以及KMP算法

随机算法实验,子串匹配问题,使用三种方法Las Vegas,Monte Carlo以及KMP算法实现并且比较优缺点;随机算法中用到的素数判定MillerRabin算法也是非常经典的。

随机算法实验

1 问题分析

实验共实现Las Vegas,Monte Carlo和KMP算法判定字串匹配问题,并进行大量实验,统计所用时间和Monte Carlo算法的出错率。实验所用的素数由Miller Rabin素数判定算法来完成。其他问题同课件。

2 算法设计思路

由于课件给出了Las Vegas,Monte Carlo和Miller Rabin算法的描述以及教材上给出的KMP算法的实现。因此,基本同课件和教材,这里不再赘述。

本实验涉及到如何利用Miller Rabin素数判定算法随机生成指定范围的素数。由于C++中随机生成的最大随机数是32767,故必须进行转换才能生出指定的范围。这里采用的是先移位再求或。例如需要生成200000到300000之间的随机数,可以这样实现:rand( )<<5|rand() % 100000+200000。

本实验测试三个字串匹配问题时,根据所测串的长度随机生成适合的素数即满足p小于2*m*n2。Las Vegas,Monte Carlo算法如果只测试一次,则Monte Carlo出错率很大;但是测试k次时,误匹配的概率小于1/nk。所以当k取5时,几乎很少出错。故这里凸显出错率,k一般取1。

3 算法流程图

这里给出KMP算法的流程图

MillerRabin算法和Las Vegas,Monte Carlo以及KMP算法

第1页

热门文档

相关文档

  • 算法总结

    对于前面提到的寻找第 K 小元素的 问题可以采用随机算法,只不过是将原来的中位数用随机数生成而 已,体现了随机算法的优点。用 Las Vegas,Monte Carlo,KMP 算法 ...

  • 三种模式匹配算法的比较和分析

    实现并比较三种模式匹配算法:KMP,MonteCarlo,LasVegas #include "random.h" #... MillerRabin算法和Las V... 8页 免费 入侵检测系统中模式匹配... 4页 免费...

  • 算法设计-随机算法

    随机算法与素数测试实验 1.实验要求(1)分别用 KMP、Monte Carlo 和 Las Vegas 算法编制 3 个程序,并随机生 成不小于 5000 对、长度很长、且长度不等的 01 ...

  • 算法设计与分析学习报告

    在这部分内容中, 我学到了 3 个重要的随机算法: KMP、 Monte Carlo 和 Las Vegas 算法的评价和比较。 这也是作为作业研究过的。 也学习的素数 判定随机算法。...

  • 算法学习报告

    重点实现了 KMP、Monte Carlo、Las Vegas 三种模式匹配算法以及根据运行 结果对三种算法进行全面的性能分析。 最后是素数测试问题, 学习了在 Fermat 小定理和其推论...

  • 一个字符串是否为另一个的子串

    判定子串算法比较一、问题描述本文主要讨论分别用 Las Vegas,Monte Carlo,KMP 算法判断某个字符串是不是另一个 字符串的子串。同时,分别统计出这三种算法的时间...

  • 算法导论学习报告

    对于同一个问题,往往都有好几种不同的算法,就像要求分别运用 3 KMP、Monte Carlo、Las Vegas 算法解决同一个问题的实验二一样。每种算法都 有各自的优缺点,...

  • 算法导论学习报告

    对于同一个问题,往往都有好几种不同的算法,就像要求分别运用 3 KMP、Monte Carlo、Las Vegas 算法解决同一个问题的实验二一样。每种算法都 有各自的优缺点,...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email