当前位置: 首页 > news >正文

【算法】【算法杂谈】已知[1,m]的等概率函数,求[1,n]的等概率函数

目录

  • 前言
  • 问题介绍
  • 解决方案
  • 代码编写
    • 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,5,10,15,20,只有这样才能将0-4插入到空隙中形成等概率的0-24,之后通过mod来缩小范围即可
2、补充问题主要讲述了如何通过非等概率获取等概率的方法,那就是通过两次的组合发现等概率的事件来制造等概率函数
3、最后一道题看似是原问题的拓展版本,其实实现方式反而是另一种角度来看这类问题了,进阶问题其实讲述了该类问题可以通过进制方式来解决,首先将目标变成m进制,之后用0-m-1的随机来生成进制的每一位,并不断判断是否越界,直到没有越界生成一个符合的数之后返回这个数,整体上还是有序的。

写在最后

方案和代码仅提供学习和思考使用,切勿随意滥用!如有错误和不合理的地方,务必批评指正~
如果需要git源码可邮件给2260755767@qq.com
再次感谢左大神对我算法的指点迷津!

相关文章:

【算法】【算法杂谈】已知[1,m]的等概率函数,求[1,n]的等概率函数

目录 前言问题介绍解决方案代码编写java语言版本c语言版本c语言版本 思考感悟写在最后 前言 当前所有算法都使用测试用例运行过&#xff0c;但是不保证100%的测试用例&#xff0c;如果存在问题务必联系批评指正~ 在此感谢左大神让我对算法有了新的感悟认识&#xff01; 问题介…...

【Python】Python中的列表,元组,字典

文章目录 列表创建列表获取元素修改元素添加元素查找元素删除元素列表拼接遍历列表切片操作 元组创建元组元组中的操作 字典创建字典添加/修改元素删除元素查找字典的遍历合法的key类型 列表 列表是一种批量保存数据的方式&#xff0c;列表使用[]表示 创建列表 创建两个空列…...

分布式系统概念和设计-分布式对象和远程调用

分布式系统概念和设计 分布式对象和远程调用 能够接收远程方法调用的对象称为远程对象&#xff0c;远程对象实现一个远程接口。 调用者和被调用对象分别存在不同的失败可能性&#xff0c;RMI和本地调用有不同的语义。 中间件 在进程和消息传递等基本构造模块之上提供编程模型的…...

11-FastDFS

一 为什么要使用分布式文件系统 单机时代 初创时期由于时间紧迫&#xff0c;在各种资源有限的情况下&#xff0c;通常就直接在项目目录下建立静态文件夹&#xff0c;用于用户存放项目中的文件资源。如果按不同类型再细分&#xff0c;可以在项目目录下再建立不同的子目录来区分…...

Word这样用,提高效率不加班

Word这样用&#xff0c;提高效率不加班 今天给大家分享23条Word文档的应用小技巧。对于大家来说&#xff0c;掌握些技巧能够效率百倍&#xff0c;何乐不为&#xff1f; 这些技巧是本人通过整理一直在用并且使用频率较高的&#xff0c;也希望能帮到大家。有兴趣的小伙伴可以自己…...

【Linux】调试器---gdb的使用

文章目录 一.背景知识二.安装gdb三.gdb的用法使用须知gdb的常用指令1.进入调试2.退出调试操作3.显示源代码4.设置断点breakPoint5.查看断点信息/禁用断点/开启断点/删除断点6.运行程序&#xff0c;开始调试run7.查看变量8.其它重要命令 一.背景知识 程序的发布方式有两种&…...

MySQL数据库之表的增删改查(进阶)

目录 1. 数据库约束1.1 约束类型1.2 NULL约束1.3 UNIQUE&#xff1a;唯一约束1.4 DEFAULT&#xff1a;默认值约束1.5 PRIMARY KEY&#xff1a;主键约束1.6 FOREIGN KEY&#xff1a;外键约束1.7 CHECK约束 2 表之间的关系2.1 一对一2.2 一对多2.3 多对多 3 新增4 查询4.1 聚合查…...

Nginx从开始到结束,简单到小白都能懂哦

绪论 大家好&#xff0c;很高兴能够为大家带来这篇关于Nginx配置的新手指南。在这篇博客中&#xff0c;我们将通过简单明了的图文教程&#xff0c;帮助大家快速上手Nginx配置&#xff0c;解锁Nginx的各种神奇功能&#xff01; 一、Nginx简介 Nginx是一款功能强大的web服务器…...

Qt——Qt控件之按钮-QDialogButtonBox对话框按钮盒子控件的使用总结(例程:自定义按钮)

【系列专栏】:博主结合工作实践输出的,解决实际问题的专栏,朋友们看过来! 《项目案例分享》 《极客DIY开源分享》 《嵌入式通用开发实战》 《C++语言开发基础总结》 《从0到1学习嵌入式Linux开发》 《QT开发实战》 《Android开发实战》...

数据库学习-常用的SQL语句

背景&#xff1a; 汇整一下自己学习数据库过程中常见的题目及语句。 一.实例分析题 二&#xff0e;简单SQL查询&#xff1a; 1&#xff09;:统计每个部门员工的数目select dept,count(*) from employee group by dept;2&#xff09;:统计每个部门员工的数目大于一个的记录se…...

5种获取JavaScript时间戳函数的方法

5种获取JavaScript时间戳函数的方法 一、JavasCRIPT时间转时间戳方法一&#xff1a;Date.now()方法二&#xff1a;Date.parse()方法三&#xff1a;valueOf()方法四&#xff1a;getTime()方法五&#xff1a;Number 二、js时间戳转时间方法一&#xff1a;生成2022/1/18 上午10:09…...

图的宽度优先遍历

文章目录 图的宽度优先遍历程序设计程序分析图的宽度优先遍历 【问题描述】根据输入图的邻接矩阵A,给出图的宽度优先遍历序列; 【输入形式】第一行为图的结点个数n,第二行输入顶点的信息,每个顶点用一个字符表示,接下来的n行为图的邻接矩阵A。其中A[i][j]=1表示两个结点邻…...

企业AD域(域控服务器)的安装和配置详细教程

一、环境以及工具准备 软件&#xff1a;VMWare Workstation 2016 &#xff08; 下载链接&#xff1a;https://pan.baidu.com/s/1iX1VRilerYPGbGvX4pvaKw 提取码&#xff1a;75R6 &#xff09; 镜像&#xff1a;Windows Server 2016 &#xff08; 下载地址&#xff…...

面试官:一千万的数据,你是怎么查询的?

面试官&#xff1a;一千万的数据&#xff0c;你是怎么查询的&#xff1f; 1 先给结论 对于1千万的数据查询&#xff0c;主要关注分页查询过程中的性能 针对偏移量大导致查询速度慢&#xff1a; 先对查询的字段创建唯一索引 根据业务需求&#xff0c;先定位查询范围&#xff08…...

IntelliJ 上 Azure Event Hubs 全新支持来了!

大家好&#xff0c;欢迎来到 Java on Azure Tooling 的3月更新。在这次更新中&#xff0c;我们将介绍 Azure Event Hubs 支持、Azure Functions 的模板增强&#xff0c;以及在 IntelliJ IDEA 中部署 Azure Spring Apps 时的日志流改进。要使用这些新功能&#xff0c;请下载并安…...

性能测试,监控磁盘读写iostat

性能测试&#xff0c;监控磁盘读写iostat iostat是I/O statistics&#xff08;输入/输出统计&#xff09;的缩写&#xff0c;iostat工具将对系统的磁盘操作活动进行监视。它的特点是汇报磁盘活动统计情况&#xff0c;同时也会汇报出 CPU使用情况。同vmstat一样&#xff0c;ios…...

steam游戏搬砖项目怎么做?月入过万的steam搬砖项目教程拆解

steam游戏搬砖项目怎么做?月入过万的steam搬砖项目教程拆解 大家好&#xff0c;我是童话姐姐&#xff0c;今天继续来聊Steam搬砖项目。 Steam搬砖项目也叫CSGO搬砖项目&#xff0c;它并不是什么刚面世的新项目&#xff0c;是已经存在至少七八年的一个资深老牌项目。这个项目…...

协同运力、算力、存力,加速迈向智能世界

2023年4月20日&#xff0c;华为在HAS2023期间举办“迈向智能世界”主题论坛&#xff0c;吸引了来自全球的分析师、专家学者及媒体与会。会上&#xff0c;华为ICT战略与Marketing总裁彭松发表了“持续技术创新&#xff0c;加速迈向智能世界”的主题演讲。 华为ICT战略与Marketin…...

被裁员了,要求公司足额补缴全部公积金,一次补了二十多万!网友兴奋了,该怎么操作?...

被裁员后&#xff0c;能要求公司补缴公积金吗&#xff1f; 一位网友问&#xff1a; 被裁员了&#xff0c;要求公司把历史公积金全部足额缴纳&#xff0c;现在月薪2.3万&#xff0c;但公司每个月只给自己缴纳300元公积金&#xff0c;结果一次补了二十多万&#xff0c;一次性取出…...

家庭智能插座一Homekit智能

传统的灯泡是通过手动打开和关闭开关来工作。有时&#xff0c;它们可以通过声控、触控、红外等方式进行控制&#xff0c;或者带有调光开关&#xff0c;让用户调暗或调亮灯光。 智能灯泡内置有芯片和通信模块&#xff0c;可与手机、家庭智能助手、或其他智能硬件进行通信&#x…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

招商蛇口 | 执笔CID,启幕低密生活新境

作为中国城市生长的力量&#xff0c;招商蛇口以“美好生活承载者”为使命&#xff0c;深耕全球111座城市&#xff0c;以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子&#xff0c;招商蛇口始终与城市发展同频共振&#xff0c;以建筑诠释对土地与生活的…...

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...

Golang——7、包与接口详解

包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...