网站建设费可以抵扣进项税吗,著名网站用什么语言做后台,crack wordpress,博客社区类网站模板目录 前言问题介绍解决方案代码编写java语言版本c语言版本c语言版本 思考感悟写在最后 前言
当前所有算法都使用测试用例运行过#xff0c;但是不保证100%的测试用例#xff0c;如果存在问题务必联系批评指正~ 在此感谢左大神让我对算法有了新的感悟认识#xff01; 问题介… 目录 前言问题介绍解决方案代码编写java语言版本c语言版本c语言版本 思考感悟写在最后 前言
当前所有算法都使用测试用例运行过但是不保证100%的测试用例如果存在问题务必联系批评指正~ 在此感谢左大神让我对算法有了新的感悟认识 问题介绍
原问题 给定一个等概率随机1-5的函数在不使用任何额外的随机函数下通过rand1To5实现rand1To7函数 补充题目 给定一个以p概率产生0,1-p概率产生1的随机函数rand01P通过该函数实现等概率的rand1To6 进阶题目 给定一个随机产生1-M的随机函数rand1ToM请依次来实现rand1ToN的随机函数
解决方案
原问题 1、首先求出等概率的0-4即rand1To5()-1 2、再求出等概率的[0,5,10,15,20],即 rand1To5()-1* 5 扩容 3、此时可以求出等概率的0-24即 rand1To5()-1* 5 rand1To5()-1 插空 4、再mod6即可得到0~6的等概率再1即可得到1-7的等概率函数了 最后公式rand1To5()-1* 5 rand1To5()-1 % 6 1 补充题目 1、首先需要获取一个能够出现等概率的函数才能解决等概率的问题 2、首先0和1无法一次调用出现等概率但是调用两次可能的结果为 00概率p^2 01概率p(1-p)10(概率p(1-p)) 11((1-p) ^2)由此发现10和01的出现概率相同利用这个即可获取一个01的等概率函数 3、如果有了等概率的01则能通过原问题中的解法就可以求的等概率的05,也就能求出等概率的1-6了 进阶题目 1、首先将n-1转化成m进制的数 2、申请一个长度为32位的int类型数组作为m进制的结果 3、从左向右进行等概率的获取0-m-1的数也就是高位先等概率生成如果中途发现整体数大于0了则直接放弃从头开始 4、最终获取到的结果再转成10进制即可
代码编写
java语言版本
原问题 方法一: /*** 随机返回1到5之间的数* return*/public static int random1to5Cp1() {return (int) (Math.random() * 5 1);}/*** 以p的概率出现0和1* param p* return*/public static int randomP01Cp1(double p) {return Math.random() p ? 0 : 1;}/*** 随机返回1到7之间的数* 要求1、仅使用random1to5实现2、必须等概率* 方法插空法、筛选法* return*/public static int random1to7Cp1() {int p 0;while ((p (random1to5Cp1() - 1) * 5 (random1to5Cp1() - 1)) 20) {p (random1to5Cp1() - 1) * 5 (random1to5Cp1() - 1);}return (int)(p%7) 1;}/*** 等概率实现1到6的随机函数* 要求1、仅使用randomP01Cp1实现2、等概率* return*/public static int random1to6Cp1() {// 0-6int p 0;while ((p get03Cp1()*2 (get01Cp1() 1)) 6) {p get03Cp1()*2 (get01Cp1() 1);}return (int)(p%6) 1;}/*** 将不等概率的变成等概率返回0和1* return*/private static int get01Cp1() {int num1 0, num2 0;while (((num1 randomP01Cp1(0.83)) ^ (num2 randomP01Cp1(0.83))) ! 1);return num1;}/*** 等概率获取0123* return*/private static int get03Cp1() {return get01Cp1() * 2 get01Cp1();}/*** 给定一个m返回1-m等概率出现* param m* return*/private static int get1ToM(int m) {return (int)(Math.random() * m) 1;}/*** 通过等概率的1-m求等概率的1-n* param m* param n* return*/private static int get1TonFromM(int m, int n) {// 首先求用m进制表示的n-1int[] mSysN getSysMNum(n-1, m);// 产生一个小于mSysN的m进制的数int[] mSys1ToN getSysM1ToN(mSysN, m);// 再转回到10进制return get10SysFromM(mSys1ToN, m) 1;}/*** 从m进制转回到10进制* param mSys1ToN* param m* return*/private static int get10SysFromM(int[] mSys1ToN, int m) {int index mSys1ToN.length-1;int res 0;while (index 0) {res Math.pow(m, (mSys1ToN.length-1) - index) * mSys1ToN[index];index--;}return res;}/*** 等概率随机获取一个小于mSysN的值* param mSysN* param m* return*/private static int[] getSysM1ToN(int[] mSysN, int m) {// 找到左边第一个不为0的int start 0;while (mSysN[start] 0) {start;}// 生成数游标int index start;int[] res new int[32];// 表示上一个值是否和mSysN相等如果相等则这波还要继续生成如果不相等说明已经大于了直接随机生成即可boolean isLastEquals true;// 从高位开始随机获取while (index ! mSysN.length) {// 先生成res[index] get1ToM(m)-1;// 判断该位置的上一个是否相等if (isLastEquals) {// 相等则该位置需要比较if (res[index] mSysN[index]) {// 说明生成的超过了归位,全部重来index start;isLastEquals true;continue;}else {isLastEquals res[index] mSysN[index];}}// 该位置不需要比较index;}return res;}/*** 用m进制表示value* param value* param m* return*/private static int[] getSysMNum(int value, int m) {int[] res new int[32];int mod value;int tem value;int index res.length-1;while (tem ! 0) {res[index--] mod % m;tem mod/m;mod mod%m;}return res;}public static void main(String[] args) {int[] ints new int[5];for (int i 0; i 100 ; i ){//System.out.println(get1TonFromM(7, 5));ints[get1TonFromM(7,5)-1] ;//System.out.println();}CommonUtils.printArr(ints);//System.out.println(String.format(%.2f, 0.0124124124));}
c语言版本
正在学习中
c语言版本
正在学习中
思考感悟
1、原问题主要讲述了一个思想就是如果用小范围的等概率扩容到大范围的等概率其中先用乘法扩容扩容不是随便扩容的扩容的大小刚还要能够让自己插空也就是说 0-4的等概率扩容必须是0,510,15,20只有这样才能将0-4插入到空隙中形成等概率的0-24之后通过mod来缩小范围即可 2、补充问题主要讲述了如何通过非等概率获取等概率的方法那就是通过两次的组合发现等概率的事件来制造等概率函数 3、最后一道题看似是原问题的拓展版本其实实现方式反而是另一种角度来看这类问题了进阶问题其实讲述了该类问题可以通过进制方式来解决首先将目标变成m进制之后用0-m-1的随机来生成进制的每一位并不断判断是否越界直到没有越界生成一个符合的数之后返回这个数整体上还是有序的。
写在最后 方案和代码仅提供学习和思考使用切勿随意滥用如有错误和不合理的地方务必批评指正~ 如果需要git源码可邮件给2260755767qq.com 再次感谢左大神对我算法的指点迷津
