随机数算法满足算法确定性（随机数算法基本思路）
我们都知道我们平常的学的算法都是很基础的，很简单的，他们的特点有一点就是确定性。实际中也常常用到不确定的算法，比如随机数生成算法，算法的结果是不确定的，我们称这种算法为（随机）概率算法，分为如下四类：
1、数值概率算法
用于数值问题的求解，通常是近似解
2、蒙特卡洛算法Monte Carlo
能得到问题的一个解，但不一定是正确解，正确的概率依赖于算法运行的时间，算法所用的时间越多，正确的概率也越高。求问题的准确解；
3、拉斯维加斯算法 Las Vegas
不断调用随机算法求解，直到求得正确解或调用次数达到某个阈值。所以，如果能得到解，一定是正确解。
4、舍伍德算法 Sherwood
利用随机算法改造已有算法，使得算法的性能尽量与输入数据无关，即平滑算法的性能。它总能求得问题的一个解，且求得的解总是正确的。
随机数
概述
计算机产生的随机数都是伪随机数，通过线性同余法得到。
方法：产生随机序列
d称为种子；m取值越大越好；m，b互质，常取b为质数；
案例
伪随机数
在实际编程中，我们使用rand随机投点法计算π
（2）计算定积分
（3）解非线性方程组
1. 随机投点法计算π
如下图，正方形及其内切圆，圆半径为r。现向正方形中随机投n个点，所投点均匀分布，则点落入圆内概率为
。
考虑第一象限即可，取r=1，投n个点，落入圆中k个点，当n趋近无穷时，k/n 趋近于。
#include
#include
#include
#include
floatCalculatePI算法
一个算法，对于不同的输入数据，其算法的性能是不一样的。比如快排算法，每次选择第一个元素作为基准，对序列从小到大排序：
平均情况：如果待排序列无序，则算法时间复杂度为O，则算法时间复杂度为O。
可见舍伍德算法就是一种利用随机算法改造确定性算法，使得算法的性能和输入数据尽量无关。
拉斯维加斯（Las Vegas）算法
算法思想就是不断调用随机算法求解，直到求得正确解或者达到设定的步数。
【理解为：不断掷骰子，直到得到某个值，或掷累了】
如下面的代码：
success=false;steps=0;
while算法
拉斯维加斯算法是：不一定能给出解，给出则必正确
蒙特卡罗算法是：一定能给出解，但不一定正确
蒙特卡罗算法在一般情况下能够保证对问题的所有实例都以高概率给出正确解。但是，通常无法判断一个具体解是否正确。
一个蒙特卡罗算法得到正确解的概率为p，如果0.5 < p < 1，则称算法是正确的。p-0.5称为算法的优势。
对于用一个实例，如果蒙特卡罗算法不会给出两个不同的正确解，则称算法是一致的。
想学习更多？不如关注一下我试试？返回搜狐，查看更多