Long Luo's Life Notes Long Luo's Life Notes 每一天都是奇迹首页作品关于标签分类归档友链搜索 文章目录站点概览Long LuoA Curious Engineer 351 日志 28 分类 344 标签 GitHub ZhiHu LinkedIn E-Mail 链接My CSDN 扔几个骰子，怎么算出期望？——拼多多校招笔试算法题的数学故事 发表于 2025-02-01 更新于 2025-10-22 分类于 Data Structures and Algorithms 阅读次数： Waline： 阅读次数： 本文字数： 3.9k 阅读时长 ≈ 4 分钟 By Long Luo在上一篇文章我们剖析了 拼多多 2020 年校招笔试算法题中第一题: 多多的魔术盒子 ，今天来挑战下其中的第 4 题：骰子期望 1 ，题目如下：骰子期望扔 \(n\) 个骰子，第 \(i\) 个骰子有可能投掷出 \(X_i\) 种等概率的不同的结果，数字从 \(1\) 到 \(X_i\) 。所有骰子的结果的最大值将作为最终结果。求最终结果的期望。输入描述: 第一行一个整数 \(n\) ，表示有 \(n\) 个骰子。( \(1 \le n \le 50\) )第二行 \(n\) 个整数，表示每个骰子的结果数 \(X_i\) 。( \(2 \le X_i \le 50\) )输出描述: 输出最终结果的期望，保留两位小数。输入例子 \(1\) : 22 2输出例子 \(1\) : 1.75要解答这道题，我们需要先从脑海里把中学数学知识捡起来，弄清楚什么是期望 2？在概率论和统计学中，一个离散性随机变量的数学期望是试验中每次可能的结果乘以其结果概率的总和：\[ \operatorname {E} [X] = \sum _{i=1}^{\infty }x_{i}\,p_{i} ag{1} \label{1} \]具体到这道题示例 \(1\) ，很明显 \(2\) 个骰子只能取到 \(1\) 或者 \(2\) 个值：假设这 \(2\) 个骰子取到的最大值为 \(1\) ，那么这 \(2\) 个骰子都只能选择 \(1\) ，概率为： \(\dfrac {1}{2} imes \dfrac {1}{2} = \dfrac {1}{4}\) ；假设这 \(2\) 个骰子取到的最大值为 \(2\) ，那么存在 \(2\) 种可能，要么都取 \(2\) 或者 \(2\) 个骰子中有一个骰子投出了 \(2\) ，其概率为： \(\dfrac {1}{2} imes \dfrac {1}{2} + \dfrac {1}{2} imes 1 = \dfrac {3}{4}\) 。那么期望为： \(\dfrac {1}{4} imes 1 + \dfrac {3}{4} imes 2 = 1.75\) 。对于骰子数少的时候还可以枚举，如果骰子数量很多呢？用上述方法就会遇到困难，比如有 \(N\) 个骰子，最大值为 \(M\) ，那么骰子结果为 \([1, 2, \dots, M]\) ，如何计算每个结果的概率值呢？直接算当然是可行的，但是如果骰子数量很多的话，计算会非常繁琐，所以有没有更简单的方法呢？ 阅读全文 » 拼多多校招笔试算法题：一行公式搞定“多多的魔术盒子” 发表于 2025-01-26 更新于 2025-10-15 分类于 Data Structures and Algorithms 阅读次数： Waline： 阅读次数： 本文字数： 3.4k 阅读时长 ≈ 3 分钟 By Long Luo众多IT大厂中拼多多虽然工作强度很大，但在给钱方面非常大方。大厂给的钱多，但要求也高。下面就来挑战拼多多 2020 年校招笔试算法题 1 中第一题：多多的魔术盒子 2 ，看看难度如何。多多的魔术盒子多多鸡有 \(N\) 个魔术盒子(编号 \(1 \sim N\) )，其中编号为 \(i\) 的盒子里有 \(i\) 个球。多多鸡让皮皮虾每次选择一个数字 \(X\) ( \(1 \le X \le N\) )，多多鸡就会把球数量大于等于 \(X\) 个的盒子里的球减少 \(X\) 个。 通过观察，皮皮虾已经掌握了其中的奥秘，并且发现只要通过一定的操作顺序，可以用最少的次数将所有盒子里的球变没。那么请问聪明的你，是否已经知道了应该如何操作呢？时间限制： C/C++ 1秒，其他语言 2 秒空间限制： C/C++ 256M，其他语言 512M输入描述: 第一行，有 \(1\) 个整数 \(T\) ，表示测试用例的组数。 ( \(1 \le T \le 100\) )接下来 \(T\) 行，每行 \(1\) 个整数 \(N\) ，表示有 \(N\) 个魔术盒子。 ( \(1 \le N \le 1,000,000,000\) )输出描述: 共 \(T\) 行，每行 \(1\) 个整数，表示要将所有盒子的球变没，最少需要进行多少次操作。输入例子 1 : 12343125输出例子 1 : 123123最少的操作次数该怎么做？根据题意，我们关键是要找到最少次数这个方法，那如何操作才能使用最少次数呢？当面对复杂问题时，我们需要从简单情况入手，分析其中规律，找到突破口。\(N = 1\) 时，显然选择 \(X = 1\) ，需要 \(1\) 次操作；\(N = 2\) 时，可以先选择 \(X = 1\) ，再选择 \(X = 2\) ，需要 \(2\) 次操作；\(N = 3\) 时，只有先选择 \(X = 2\) ，再选择 \(X = 1\) ，最少需要 \(2\) 次操作；\(N = 4\) 时，可以先选择 \(X = 2\) 或者 \(X = 3\) ，最少需要 \(3\) 次操作；通过分析发现，每次操作之后，球的数量都会动态变化。如果每次都选择中间的数字，这样每次操作之后，如果 \(N\) 为奇数的话，可以变成 \(2\) 个对称相同的数组， \(N\) 为偶数的话，则 \(2\) 个数组中元素值会相差 \(1\) ，再选择元素值更多的数组进行消除，这样可以实现操作次数最少。实现代码如下：12345678910111213private static int leastTimes_power(int n) { int ans = 1; for (int i = 0; i
