分汤
题目描述1
题目讲解
讲解示例2
结果: 当 n=100 时，结果为 0.71875.
分析：𝑃 = Pr(𝐴先空)+ $\frac{1}{2}$Pr(𝐴,𝐵同时空)。
- 初始状态是 (𝐴,𝐵) = (100,100)。
- 第一次选操作 1 (倒 100A, 0B)
- 立刻 A 先空，贡献得分 1 .
- 加权贡献：0.25 × 1 = 0.25.
- 第一次选操作 2（倒 75A, 25B）→ 新状态 (25A, 75B)
从 (25A, 75B) 再进行一次操作，四种等概率结果的“得分”（A 先空记 1，同时空记 0.5，B 先空记 0）：
- 操作 1：A 先空 → 1
- 操作 2：A 先空 → 1
- 操作 3：A 先空 → 1
- 操作 4：同时空 → 0.5
- 期望得分：$\frac{1}{4}$(1+1+1+0.5) = 0.875.
- 加权贡献：0.25 × 0.875 = 0.21875.
- 第一次选操作 3（倒 50A, 50B）→ 新状态 (50A,50B)
从 (50A,50B) 再进行一次操作的得分：
- 操作 1：A 先空 → 1
- 操作 2：A 先空 → 1
- 操作 3：同时空 → 0.5
- 操作 4：B 先空 → 0
- 期望得分：$\frac{1}{4}$(1+1+0.5+0) = 0.625.
- 加权贡献：0.25 × 0.625 = 0.15625.
- 第一次选操作 4（倒 25A, 75B）→ 新状态 (75A,25B)
从 (75A, 25B) 再进行一次操作的得分：
- 操作 1：A 先空 → 1
- 操作 2：同时空 → 0.5
- 操作 3：B 先空 → 0
- 操作 4：B 先空 → 0
- 期望得分：$\frac{1}{4}$(1+0.5+0+0)=0.375.
- 加权贡献：0.25 × 0.375 = 0.09375.
- 汇总 𝑃 = 0.25 + 0.21875 + 0.15625 + 0.09375 = 0.71875.
代码
c
java
python
#include<iostream>
#include <functional>
using namespace std;
// c++23 写法：
// class Solution {
// public:
// double soupServings(int n) {
// // 备忘录数组 f，存储状态 f[i][j] 的答案，初始化为 0
// // 把 n 缩成单位份数,𝑚=⌈𝑛/25⌉,且对大于 4800 的 n 直接返回 1,最大会用到的索引为 ⌈4800/25⌉=192,小于 200.
// double f[200][200] = {0.0};
// // this auto&& dfs: C++23 的语法扩展，this-capture for lambdas with recursion.
// auto dfs = [&](this auto&& dfs, int i, int j) -> double {
// if (i <= 0 && j <= 0) return 0.5;
// if (i <= 0) return 1;
// if (j <= 0) return 0;
// // 记忆化：若已算过直接返回
// if (f[i][j] > 0) return f[i][j];
// double ans = 0.25 * (dfs[i-4][j] + dfs[i-3][j-1] + dfs[i-2][j-2] + dfs[i-1][j-3]);
// f[i][j] = ans;
// return ans;
// };
// return n > 4800 ? 1 : dfs(dfs, (n + 24) / 25, (n + 4) / 25);
// }
// };
class Solution {
public:
double soupServings(int n) {
if (n > 4800) return 1.0; // 剪枝：大数近似为 1
double f[200][200] = {0.0}; // 备忘录，零初始化
std::function<double(int,int)> dfs;
dfs = [&](int i, int j) -> double {
if (i <= 0 && j <= 0) return 0.5;
if (i <= 0) return 1.0;
if (j <= 0) return 0.0;
if (f[i][j] > 0) return f[i][j];
double ans = 0.25 * (
dfs(i - 4, j) +
dfs(i - 3, j - 1) +
dfs(i - 2, j - 2) +
dfs(i - 1, j - 3)
);
f[i][j] = ans;
return ans;
};
int m = (n + 24) / 25; // 上取整归一化到“份”
return dfs(m, m);
}
};
int main() {
Solution s;
double result = s.soupServings(100);
std::cout << result << std::endl;
}