B站视频地址:https://bilibili.com/video/BV1g3411i7of?p=8&spm_id_from=pageDriver
class02代码github地址:https://github.com/algorithmzuo/algorithm-primary/tree/main/src/class02
算法与数据结构新手班(class02)——随机数的原理与扩展应用
1. 利用前缀和求数组中任意区间和2. 对数器——随机数的原理及应用扩展
2.1 随机数：2.2 随机函数的测试：2.3 随机数的扩展思考
(1) U(0,1)均匀分布的分布区间扩展：(2) U(0,K)均匀分布函数返回结果从正实数转换为正整数(3) U(0,K)均匀分布的概率调整：由 x x x调整为 x 2 x^2 x2(4) U(0,K)均匀分布的概率调整：由 x x x调整为 x 3 x^3 x3 2.4 经典面试题——随机函数
(1) 从[1,5]等概率随机变为[1,7]等概率随机：
[1] 班上分步骤实现C++版：[2] 单函数完成全部功能C++版： (2) 从[3,19]等概率随机变为[17,56]等概率随机：(3) 将0或1不等概率转化为0或1等概率：
1. 利用前缀和求数组中任意区间和如果要求出一个数组中的某个区间元素之和，传统做法是从起始下标累加到末尾下标，这种最易实现，但如果涉及到数组长度很长、频繁求不同区间的话，这种方法显然效率低下。
传统求区间元素和的方法：
class RangeSumIneffect
{
public:
RangeSumIneffect(vector& nums) //构造函数
{
int n = nums.size();
for(int i = 0; i < n; i++)
{
arr.push_back(nums[i]);
}
}
int sumsRangeIneffect(int L, int R) //求某区间元素之和
{
//printArray(arr);
int sum = 0;
for(int i = L; i <= R; i++)
{
sum += arr[i];
}
return sum;
}
private:
vector arr;
};
因此，利用前缀和技巧，事先求出数组内各元素的前面之和，即新建一个数组求出从0到X的累加值。
数组前缀和方法：
class RangeSumPre
{
public:
RangeSumPre(vector& nums) //构造函数
{
int n = nums.size();
sumPre.resize(n + 1);
for(int i = 0; i < n; i++)
{
sumPre[i + 1] = sumPre[i] + nums[i];
}
}
int sumsRangePre(int L, int R) //利用前缀和数组直接获取区间和
{
//printArray(sumPre);
return sumPre[R + 1] - sumPre[L];
}
private:
vector sumPre;
};
注意：完整代码中利用了C++自带的时间函数，可以体会二者方法的时间效率差异，后面还会利用对数器产生随机不定数组更能体会之间差异。
记录程序运行时间的参考博客：C++中如何记录程序运行时间
不光是一维数组可应用前缀和技巧，二维矩阵同样可以应用前缀和，可以去看《labuladong的算法秘籍》中的《小而美的算法技巧：前缀和数组》
尾田理解的对数器概念：自己开发算法的复杂度往往是高的，通过一种具有大量样本分析的测试程序与另一种绝对正确且复杂度较低的官方算法进行比较，从而得出自研算法是否正确，这种测试程序就叫对数器。
左神阐述的对数器概念：
1. 有一个你想要测的方法a；
2. 实现一个绝对正确但是复杂度不好的方法b；
3. 实现一个随机样本产生器；
4. 实现对比算法a和b的方法；
5. 把方法a和方法b比对多次来验证方法a是否正确；
6. 如果有一个样本使得比对出错，打印样本分析是哪个方法出错；
7. 当样本数量很多时比对测试依然正确，可以确定方法a已经正确。
————————————————
对数器的实现需要使用到随机函数产生器。
在C++11版本之前，一般产生[0, 1]之间的随机浮点数是先使用rand()函数返回的整数值，经过取余将其作为分子，与精度分母作除法从而得到随机浮点数。
参考博客：C++ 产生0-1之间的随机数
#include "iostream"
#include "ctime"
#include "cstdlib"
using namespace std;
#define N 999 //精度为小数点后面3位
int main()
{
float num;
int i;
float random[10];
srand(time(NULL));//设置随机数种子，使每次产生的随机序列不同
for (int i = 0; i < 10; i++)
{
random[i] = rand() % (N + 1) / (float)(N + 1);
}
for (int i = 0; i < 10; i++)
{
cout << random[i] << endl; //输出产生的10个随机数
}
return 0;
}
当N取99，即精度为0.01时，程序运行结果：
0.12 0.52 0.35 0.16 0.17 0.54 0.36 0.29 0.94 0.91
当N取9999，即精度为0.0001时，程序运行结果：
0.9478 0.4157 0.4774 0.5131 0.1901 0.9363 0.5083 0.2954 0.0284 0.0535
结果精度达到要求，程序测试通过。
到了C++11，官方引入了random库，用于解决随机数产生问题，其精度更高、稳定性强。
参考博客：C++标准库——random
C++函数编程手册网站：http://www.cplusplus.com/reference/random/
利用random库可以产生精度更高的随机数，demo参考博客：利用c++random库产生 0到1之间的随机实数
//产生非确定性随机数（多次次运行时每次产生的随机数不一样） #include2.2 随机函数的测试：#include int main() { std::random_device e; std::uniform_real_distribution u(0, 1); //随机数分布对象 for (size_t i = 0; i < 10; ++i) //生成范围为0-1的随机浮点数序列 std::cout << u(e) << " "; std::cout << std::endl; return 0; }
测试随机函数是否是等概率，理论上样本足够大时概率应等于概率约束值。
// 利用random库获取随机实数
double getRandom(void);
int main(int args, char** argv)
{
cout << "===== 2.2 =====" << endl;
int testTimes = 100000;
int count = 0;
for(int i = 0; i < testTimes; i++)
{
if(getRandom() < 0.75) // 这里是概率约束值
{
count++;
}
}
cout << "getRandom() < 0.75: " << (double)count / (double)testTimes << endl;
return 0;
}
// 利用random库获取随机实数
double getRandom()
{
random_device e;
uniform_real_distribution u(0.0, 1.0);
return u(e);
}
程序运行结果：
===== 2.2 ===== getRandom() < 0.75: 0.750212.3 随机数的扩展思考 (1) U(0,1)均匀分布的分布区间扩展：
cout << "===== 2.3 =====" << endl;
int count = 0;
int testTimes = 100000;
for(int i = 0; i < testTimes; i++)
{
if(getRandom() * 8 < 5) // 设定概率约束值
{
count++;
}
}
cout << "(u(e) * 8 < 5): " << (double)count / (double)testTimes << endl;
cout << "5 / 8: " << (double)5 / (double)8 << endl;
程序运行结果：
===== 2.3 ===== (u(e) * 8 < 5): 0.62664 5 / 8: 0.625(2) U(0,K)均匀分布函数返回结果从正实数转换为正整数
cout << "===== 2.4 =====" << endl;
int K = 9;
int counts[9] = {0};
for(int i = 0; i < testTimes; i++)
{
int ans = (int)(getRandom() * K);
counts[ans]++;
}
for(int i = 0; i < K; i++)
{
cout << i << "这个数，出现了 " << counts[i] << " 次" << endl;
}
程序运行结果：
===== 2.4 ===== 0这个数，出现了 11175 次 1这个数，出现了 11004 次 2这个数，出现了 11145 次 3这个数，出现了 11108 次 4这个数，出现了 11052 次 5这个数，出现了 11145 次 6这个数，出现了 11154 次 7这个数，出现了 11191 次 8这个数，出现了 11026 次(3) U(0,K)均匀分布的概率调整：由 x x x调整为 x 2 x^2 x2
// 返回[0, 1)的一个小数
// 任意的x，x∈[0, 1)，[0, 1)范围上的数出现概率由原来的x调整成x平方
double xToXPower2()
{
return fmax(getRandom(), getRandom());
}
int main(int args, char** argv)
{
cout << "===== 2.5 =====" << endl;
count = 0;
double x = 0.6;
for(int i = 0; i < testTimes; i++)
{
if(xToXPower2() < x)
{
count++;
}
}
cout << "(xToXPower2() < x): " << (double)count / (double)testTimes << endl;
cout << "x ^ 2: " << powf(x, 2) << endl;
}
程序运行结果：
===== 2.5 ===== (xToXPower2() < x): 0.35907 x ^ 2: 0.36(4) U(0,K)均匀分布的概率调整：由 x x x调整为 x 3 x^3 x3
// 返回[0, 1)的一个小数
// 任意的x，x∈[0, 1)，[0, 1)范围上的数出现概率由原来的x调整成x立方
double xToXPower3()
{
return fmax(getRandom(), fmax(getRandom(), getRandom()));
}
int main(int args, char** argv)
{
cout << "===== 2.6 =====" << endl;
count = 0;
double x = 0.6;
for(int i = 0; i < testTimes; i++)
{
if(xToXPower3() < x)
{
count++;
}
}
cout << "(xToXPower3() < x): " << (double)count / (double)testTimes << endl;
cout << "x ^ 3: " << powf(x, 3) << endl;
return 0;
}
程序运行结果：
===== 2.6 ===== (xToXPower3() < x): 0.21674 x ^ 3: 0.2162.4 经典面试题——随机函数
利用随机函数当笔试考点的类型有：从一定范围内的等概率随机变换到另一范围的等概率随机、从一定范围内的不等概率随机变换到另一范围的等概率随机。
(1) 从[1,5]等概率随机变为[1,7]等概率随机：解决同类型题目的解题步骤为:
- 将题目提供的随机分布黑盒子降为成0或1状态器；0或1状态器取适当位数按位填充成[0,x]；将[0,x]按照目标范围缩短长度；根据目标范围添加偏移量。
- 模拟生成[1,5]等概率随机黑盒子
// 库函数：
// 给定返回一个特定范围概率的随机函数黑盒子，无法查阅该源码
// 这里是等概率返回[1, 5]的正整数
int staticRandom(void)
{
return (int)(getRandom() * 5) + 1;
}
测试程序：
int main(int args, char** argv)
{
int testTimes = 1000000;
cout << "===== 3.0 =====" << endl;
int K = 7;
int counts0[7] = {0};
for(int i = 0; i < testTimes; i++)
{
int ans = staticRandom();
counts0[ans]++;
}
for(int i = 0; i < K; i++)
{
cout << i << "这个数，出现了 " << counts0[i] << " 次" << endl;
}
return 0;
}
程序运行结果：
===== 3.0 ===== 0这个数，出现了 0 次 1这个数，出现了 200181 次 2这个数，出现了 200038 次 3这个数，出现了 199467 次 4这个数，出现了 199305 次 5这个数，出现了 201009 次 6这个数，出现了 0 次
- 模拟生成的黑盒子降为成0或1状态器
// 随机机制，只能用staticRandom()
// 要求：等概率返回0或1
int getZeroOrOne()
{
char ans = 0;
do{
ans = staticRandom();
}while(ans == 3); // ans只能取1、2、4、5，将3的概率平分给其他数
return ans < 3? 0 : 1; //{1, 2}返回0；{4， 5}返回1
}
测试程序：
int main(int args, char** argv)
{
int testTimes = 1000000;
cout << "===== 3.1 =====" << endl;
int count = 0;
for(int i = 0; i < testTimes; i++)
{
if(getZeroOrOne() == 1) // 这里是概率约束值
{
count++;
}
}
cout << "(getZeroOrOne() == 1): " << (double)count / (double)testTimes << endl;
return 0;
}
程序运行结果：
===== 3.1 ===== (getZeroOrOne() == 1): 0.500227
- 将0或1状态器取3位二进制位按位填充成[0,7]；
二进制位填充快速查表
// 利用 getZeroOrOne() 函数
// 等概率返回 0(000) ~ 7(111)的正整数
int getZeroToSeven()
{
return (getZeroOrOne() << 2) + (getZeroOrOne() << 1) + getZeroOrOne();
}
测试程序：
int main(int args, char** argv)
{
int testTimes = 1000000;
cout << "===== 3.2 =====" << endl;
K = 8;
int counts[8] = {0};
for(int i = 0; i < testTimes; i++)
{
int ans = getZeroToSeven();
counts[ans]++;
}
for(int i = 0; i < K; i++)
{
cout << i << "这个数，出现了 " << counts[i] << " 次" << endl;
}
return 0;
}
程序运行结果：
===== 3.2 ===== 0这个数，出现了 124573 次 1这个数，出现了 124717 次 2这个数，出现了 125339 次 3这个数，出现了 125055 次 4这个数，出现了 125674 次 5这个数，出现了 125134 次 6这个数，出现了 124739 次 7这个数，出现了 124769 次
- 将[0,7]按照目标范围[1,7]缩短长度成[0,6]；
// 利用 getZeroToSeven() 函数
// 等概率返回 0 ~ 6 的正整数
int getZeroToSix()
{
char ans = 0;
do{
ans = getZeroToSeven();
}while(ans == 7); // ans∈[0, 7]除了7
return ans;
}
测试程序：
int main(int args, char** argv)
{
int testTimes = 1000000;
cout << "===== 3.3 =====" << endl;
K = 8;
int counts2[8] = {0};
for(int i = 0; i < testTimes; i++)
{
int ans = getZeroToSix();
counts2[ans]++;
}
for(int i = 0; i < K; i++)
{
cout << i << "这个数，出现了 " << counts2[i] << " 次" << endl;
}
return 0;
}
程序运行结果：
===== 3.3 ===== 0这个数，出现了 142500 次 1这个数，出现了 143124 次 2这个数，出现了 142891 次 3这个数，出现了 142980 次 4这个数，出现了 142783 次 5这个数，出现了 142601 次 6这个数，出现了 143121 次 7这个数，出现了 0 次
- 将[0,6]按照目标范围[1,7]施加+1的偏移量；
// 利用 getZeroToSix() 函数
// 等概率返回 1 ~ 7的正整数
int getOneToSeven()
{
return getZeroToSix() + 1;
}
测试程序：
int main(int args, char** argv)
{
int testTimes = 1000000;
cout << "===== 3.4 =====" << endl;
K = 8;
int counts3[8] = {0};
for(int i = 0; i < testTimes; i++)
{
int ans = getOneToSeven();
counts3[ans]++;
}
for(int i = 0; i < K; i++)
{
cout << i << "这个数，出现了 " << counts3[i] << " 次" << endl;
}
return 0;
}
程序运行结果：
===== 3.4 ===== 0这个数，出现了 0 次 1这个数，出现了 142812 次 2这个数，出现了 142807 次 3这个数，出现了 142849 次 4这个数，出现了 143397 次 5这个数，出现了 142894 次 6这个数，出现了 142699 次 7这个数，出现了 142542 次[2] 单函数完成全部功能C++版：
由于班上的解题步骤有四步，将其解题逻辑重构为单个函数实现。
int getOneToSevenPlus()
{
char zeroOroneTemp = 0;
char zeroOrOne0 = 0;
char zeroOrOne1 = 0;
char zeroOrOne2 = 0;
int zeroToSeven = 0;
// 3. 等概率返回 0 ~ 6
do
{
// 2. 等概率返回 0(000) ~ 7(111)
for(int i = 0; i < 3; i++)
{
// 1. 等概率返回 0 或 1
do{
zeroOroneTemp = staticRandom();
}while(zeroOroneTemp == 3);
switch(i)
{
case 0:
zeroOrOne0 = zeroOroneTemp < 3? 0 : 1;
break;
case 1:
zeroOrOne1 = zeroOroneTemp < 3? 0 : 1;
break;
case 2:
zeroOrOne2 = zeroOroneTemp < 3? 0 : 1;
break;
}
}
zeroToSeven = (zeroOrOne2 << 2) + (zeroOrOne1 << 1) + zeroOrOne0;
} while (zeroToSeven == 7);
// 4. 等概率返回 1 ~ 7
return zeroToSeven + 1;
}
测试程序：
int main(int args, char** argv)
{
int testTimes = 1000000;
cout << "===== 单函数实现全部步骤(尾田C++版)： =====" << endl;
int K = 8;
int counts3[8] = {0};
for(int i = 0; i < testTimes; i++)
{
int ans = getOneToSevenPlus();
counts3[ans]++;
}
for(int i = 0; i < K; i++)
{
cout << i << "这个数，出现了 " << counts3[i] << " 次" << endl;
}
return 0;
}
程序运行结果：
===== 单函数实现全部步骤(尾田C++版)： ===== 0这个数，出现了 0 次 1这个数，出现了 142757 次 2这个数，出现了 142655 次 3这个数，出现了 142844 次 4这个数，出现了 142694 次 5这个数，出现了 142871 次 6这个数，出现了 143323 次 7这个数，出现了 142856 次(2) 从[3,19]等概率随机变为[17,56]等概率随机：
解题步骤类似上面的，直接上单函数实现版本：
int getSeventeenToFiftysix()
{
char zeroOroneTemp = 0;
char zeroOrOne0 = 0;
char zeroOrOne1 = 0;
char zeroOrOne2 = 0;
char zeroOrOne3 = 0;
char zeroOrOne4 = 0;
char zeroOrOne5 = 0;
int zeroToThirtynine = 0;
// 3. 等概率返回 0 ~ 39
do
{
// 2. 等概率返回 0(000000) ~ 63(111111)
for(int i = 0; i < 6; i++)
{
// 1. 等概率返回 0 或 1
do{
zeroOroneTemp = staticRandom();
}while(zeroOroneTemp == 11);
switch(i)
{
case 0:
zeroOrOne0 = zeroOroneTemp < 11? 0 : 1;
break;
case 1:
zeroOrOne1 = zeroOroneTemp < 11? 0 : 1;
break;
case 2:
zeroOrOne2 = zeroOroneTemp < 11? 0 : 1;
break;
case 3:
zeroOrOne3 = zeroOroneTemp < 11? 0 : 1;
break;
case 4:
zeroOrOne4 = zeroOroneTemp < 11? 0 : 1;
break;
case 5:
zeroOrOne5 = zeroOroneTemp < 11? 0 : 1;
break;
}
}
zeroToThirtynine = (zeroOrOne5 << 5) + (zeroOrOne4 << 4) + (zeroOrOne3 << 3) + (zeroOrOne2 << 2) + (zeroOrOne1 << 1) + zeroOrOne0;
} while (zeroToThirtynine > 39); // 大于39的数重新运行
// 4. 等概率返回 17 ~ 56
return zeroToThirtynine + 17;
}
测试程序：
int main(int args, char** argv)
{
int testTimes = 1000000;
cout << "===== 单函数实现[17,56](尾田C++版) =====" << endl;
int K = 40 + 17;
int counts3[63] = {0};
for(int i = 0; i < testTimes; i++)
{
int ans = getSeventeenToFiftysix();
counts3[ans]++;
}
for(int i = 16; i < 60; i++)
{
cout << i << "这个数，出现了 " << counts3[i] << " 次" << endl;
}
return 0;
}
程序运行结果：
===== 单函数实现[17,56](尾田C++版) ===== 16这个数，出现了 0 次 17这个数，出现了 24914 次 18这个数，出现了 24815 次 19这个数，出现了 24983 次 20这个数，出现了 25078 次 。。。省略。。。 51这个数，出现了 25088 次 52这个数，出现了 25023 次 53这个数，出现了 25145 次 54这个数，出现了 24846 次 55这个数，出现了 24857 次 56这个数，出现了 24848 次 57这个数，出现了 0 次 58这个数，出现了 0 次 59这个数，出现了 0 次(3) 将0或1不等概率转化为0或1等概率：
利用两个进制位，分别运行不等概率黑盒子函数，只取01和10状态，舍去00和11状态。
// 库函数：
// 给定返回一个不等概率的0或1状态器，无法查阅该源码
int unequalRandom()
{
return getRandom() < 0.84 ? 0 : 1;
}
// 将不等概率状态器转化为等概率状态器
int getEqualRandom()
{
int ans = 0;
do{
ans = unequalRandom();
}while(ans == unequalRandom());
// 第一次 | 第二次
// ans = 0 1
// ans = 1 0
return ans;
}
测试程序：
int main(int args, char** argv)
{
int testTimes = 1000000;
cout << "===== unequal To Equal Probality =====" << endl;
int count = 0;
for(int i = 0; i < testTimes; i++)
{
if(getEqualRandom() == 0) // 这里是概率约束值
{
count++;
}
}
cout << "(getEqualRandom() == 1): " << (double)count / (double)testTimes << endl;
return 0;
}
程序运行结果：
===== unequal To Equal Probality ===== (getEqualRandom() == 1): 0.5001
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）