个人如何制作一个网站,wordpress 爬虫,免费网站 推广网站,做服装有哪些好的网站先说说什么是拒绝采样算法#xff1a;就类似于数学上的求阴影面积的方法#xff0c;直接求求不出来#xff0c;就用大面积 - 小面积 阴影面积的办法。 所谓拒绝 和 采样 #xff1a;就像是撒豆子计个数#xff0c;计算概率问题一样#xff0c;大桶里面套小桶#xff0c… 先说说什么是拒绝采样算法就类似于数学上的求阴影面积的方法直接求求不出来就用大面积 - 小面积 阴影面积的办法。 所谓拒绝 和 采样 就像是撒豆子计个数计算概率问题一样大桶里面套小桶一把豆子撒下去每个豆子都是一个“样本”如果落在小桶外面的大桶里面去了就“拒绝”这个样本如果在小桶里就“采用”这个样本 就这样拒绝-和采用所有的豆子小桶里面的豆子数量除以所有的豆子的数量就得到啊小桶在大桶里的占比也就是豆子落在小桶里的概率……………………巴拉巴拉一些关于概率的问题就可以这样求解了。 这是力扣的两题一一举例加以解释。 读题现在有一个只能生成1、2、3、4、5、6、7这7个数字的随机函数Rand7()问你如何用这个函数实现一个可以随机生成1~10的随机函数Rand10PS:随机函数生成其中每个值的概率必须相等才行
想法想想二进制011010010111000010101010这玩意用两个Rand7()就可以生成7*749种选择我们只要10种就够了所以可以有
1和1、1和2、1和3 表示 1
1和4、1和5、1和6 表示 2
2和1、2和2、2和3 表示 3
2和4、2和5、2和6 表示 4
3和1、3和2、3和3 表示 5
3和4、3和5、3和6 表示 6
4和1、4和2、4和3 表示 7
4和4、4和5、4和6 表示 8
5和1、5和2、5和3 表示 9
5和4、5和5、5和6 表示 10
6和1、6和2、6和3 拒绝表示
6和4、6和5、6和6 拒绝表示
7和1、7和2、7和3 拒绝表示
7和4、7和5、7和6 拒绝表示
也就是第一个Rand7() 只能生成1~5中的一个数第二个Rand7()只能生成1~6中的一个数不然就拒绝采样重新生成才行。
代码优化前
class Solution {
public:int rand10() {int a,b;while(1){a rand7();if( a ! 6 a ! 7 ) break;}while(1){b rand7();if( b ! 7 ) break;}if( a 1 ){if( b 3 ) return 1;else return 2;}else if( a 2 ){if( b 3 ) return 3;else return 4;}else if( a 3 ){if( b 3 ) return 5;else return 6;}else if( a 4 ){if( b 3 ) return 7;else return 8;}else {if( b 3 ) return 9;else return 10;}}
};
代码优化后
class Solution {
public:int rand10() {while (true) {int num (rand7() - 1) * 7 rand7();if (num 40) return num % 10 1;}}
}; 不懂没关系看第二个更简单
第二题别看题目看下面读题 读题给一个半径 r0 和圆心坐标 x0, y0 ; 然后返回这个圆上或者圆内随机一点的坐标值注全是double类型而且落在每一点上的概率必须相等
官解两个随机函数呗一个随机范围是 [ x0-r0, x0r0 ] ,另一个是[ y0-r0, y0r0 ], 只要两个随机数的平方和大于了半径 r0 就统统 “拒绝”只计算 平方和小于半径的结果看图
这官解太low了 这不就是撒豆子算概率问题嘛随机生成的坐标点 x , y 就豆子的落点这个落点只能在圆内如果在圆外了就“拒绝”这个坐标给我重新生成去。
单纯是为了说明拒绝采样算法而已此题有更佳的解法
// 作者力扣官方题解
class Solution {
private:mt19937 gen{random_device{}()};uniform_real_distributiondouble dis;double xc, yc, r;public:Solution(double radius, double x_center, double y_center): dis(-radius, radius), xc(x_center), yc(y_center), r(radius) {}vectordouble randPoint() {while (true) {double x dis(gen), y dis(gen);if (x * x y * y r * r) {return {xc x, yc y};}}}
};
最有解法极坐标法 这字丑自己都不想看
代码并没有用拒绝采样算法但是效率上是它的两倍拒绝采样要170ms,但是极坐标只需要80ms
class Solution {
private:double rc,xc,yc;
public:Solution(double radius, double x_center, double y_center) {rc radius;xc x_center;yc y_center;}vectordouble randPoint() {double Rx rc * sqrt( (double)rand()/RAND_MAX );double angle 2 * M_PI * (double)rand()/RAND_MAX;return { xc Rx*cos(angle), yc Rx*sin(angle)};}
};
