c++算法求助(魔法操作:石子游戏)
小明和小亮在玩一个石子游戏。刚开始,小明有n堆石子,小亮有m堆石子。且两人每一堆石子所包含的石子个数均不超过6。
现在,小明需要执行d次魔法操作。每次魔法操作会从当前还剩余的几堆石子中随机选择一堆(选择每一堆的概率相同),并从这一堆中去掉一个石子。
如果某一堆经过一次魔法操作后不再有任何石子,那么在下次魔法操作执行时则不会再考虑这一堆。
现在小明想知道,在经过d次魔法操作之后,小亮一堆石子都不剩的概率是多少?
【输入形式】
输入的第一行包含三个整数n,m和d(1 ≤ n, m ≤ 5; 1 ≤ d ≤ 100)。
接下来一行包含n个整数,表示小明每堆石子的初始石子数。
第三行包含m个整数,表示小亮每堆石子的初始石子数。所有石子数都在1到6之间(包括1和6)。
【输出形式】
输出经过d次魔法操作后,小亮一堆石子都不剩的概率。结果保留四位小数。 whu??
这是一道概率问题,可以使用动态规划来解决。具体地,设 $f_{i,j,k}$ 表示经过 $k$ 次魔法操作后,小明还剩下 $i$ 堆石子,小亮还剩下 $j$ 堆石子,且小亮的每一堆石子都不剩余的概率。则所求的答案为 $f_{n,m,d}$。
初始时,$f_{i,j,0}=1$,表示还没有进行任何魔法操作,小亮一堆石子都不剩余的概率为1。
接下来考虑如何进行状态转移。每次魔法操作会随机选择一堆石子,并将其中一个石子拿走。因此,对于当前的状态 $f_{i,j,k}$,可以考虑从中选择一堆石子,将其中一个石子拿走,然后转移到下一个状态 $f_{i-1,j,k+1}$ 或 $f_{i,j-1,k+1}$。需要注意的是,如果选择的石子已经没有剩余的石子了,则不能再进行魔法操作。
根据上述状态转移方程,可以使用动态规划求解出所有状态,最终得到 $f_{n,m,d}$ 即可。时间复杂度为 $O(n^3md)$。
以下是 C++ 的代码实现:
#include <iostream>
#include <cstring>
#include <iomanip>
using namespace std;
const int N = 6, M = 105;
double f;
int n, m, d;
int a, b;
int main()
{
cin >> n >> m >> d;
for (int i = 1; i <= n; i++) cin >> a;
for (int i = 1; i <= m; i++) cin >> b;
memset(f, 0, sizeof(f));
f = 1;// 初始状态
for (int k = 1; k <= d; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
double p = 1.0 / (n + m - k + 1);
if (a >= k && i <= n) f += f * p;
if (b >= k && j <= m) f += f * p;
}
}
}
cout << fixed << setprecision(4) << f << endl;
return 0;
}
其中,$p$ 表示随机选择一堆石子的概率,为 $\frac{1}{n+m-k+1}$。为了便于处理,数组下标从 1 开始计算。注意,由于小明和小亮的每一堆石子所包含的石子个数均不超过6,因此可以使用一个 6 维数组来存储状态,但是这样会占用过多的空间,不太实际,因此可以将数组的第三维缩小到 $d+1$。
最后输出的结果需要保留四位小数,可以使用 fixed 和 setprecision 函数来实现。 不二猫猫 发表于 2023-3-11 17:01
const int N = 6, M = 105;
定义常量 N 和 M,用于表示两个数组 a 和 b 的长度,以及矩阵 f 的维度。
double f;
定义一个三维数组 f,用于记录状态转移方程中的子问题的解。
int n, m, d;
定义三个变量 n、m 和 d,分别表示两个数组 a 和 b 的长度,以及状态转移的最大天数。
int a, b;
定义两个数组 a 和 b,用于表示两个人对于每天的动作限制。
cin >> n >> m >> d;
从标准输入流中读入三个变量 n、m 和 d。
for (int i = 1; i <= n; i++) cin >> a;
从标准输入流中读入数组 a。
for (int i = 1; i <= m; i++) cin >> b;
从标准输入流中读入数组 b。
memset(f, 0, sizeof(f));
初始化数组 f 中的所有元素为 0。
f = 1;
将 f 的值设置为 1,表示初始状态。
for (int k = 1; k <= d; k++) {
从第 1 天到第 d 天,对每一天进行状态转移。
for (int i = 1; i <= n; i++) {
对数组 a 中的每个元素进行遍历。
for (int j = 1; j <= m; j++) {
对数组 b 中的每个元素进行遍历。
double p = 1.0 / (n + m - k + 1);
计算概率 p,其中 n 和 m 分别表示数组 a 和 b 的长度,k 表示当前天数。
if (a >= k && i <= n) f += f * p;
判断当前天数是否符合数组 a 中第 i 个元素的要求,如果符合,则将 f 的值加上 f * p。
if (b >= k && j <= m) f += f * p;
判断当前天数是否符合数组 b 中第 j 个元素的要求,如果符合,则将 f 的值加上 f * p。
cout << fixed << setprecision(4) << f << endl;
输出 f 的值,表示最终状态的解。
总的来说,这段代码的作用是求解一个动态规划问题。该问题的状态转移方程比较简单,主要是根据数组 a 和 b 中的限制条件来计算概率,然后根据概率计算子问题的解。最终,将所有子问题的解进行合并,就可以得到最终的解。 不二猫猫 发表于 2023-3-11 17:01
const int N = 6, M = 105;
定义常量 N 和 M,用于表示两个数组 a 和 b 的长度,以及矩阵 f 的维度。
double f;
定义一个三维数组 f,用于记录状态转移方程中的子问题的解。
int n, m, d;
定义三个变量 n、m 和 d,分别表示两个数组 a 和 b 的长度,以及状态转移的最大天数。
int a, b;
定义两个数组 a 和 b,用于表示两个人对于每天的动作限制。
cin >> n >> m >> d;
从标准输入流中读入三个变量 n、m 和 d。
for (int i = 1; i <= n; i++) cin >> a;
从标准输入流中读入数组 a。
for (int i = 1; i <= m; i++) cin >> b;
从标准输入流中读入数组 b。
memset(f, 0, sizeof(f));
初始化数组 f 中的所有元素为 0。
f = 1;
将 f 的值设置为 1,表示初始状态。
for (int k = 1; k <= d; k++) {
从第 1 天到第 d 天,对每一天进行状态转移。
for (int i = 1; i <= n; i++) {
对数组 a 中的每个元素进行遍历。
for (int j = 1; j <= m; j++) {
对数组 b 中的每个元素进行遍历。
double p = 1.0 / (n + m - k + 1);
计算概率 p,其中 n 和 m 分别表示数组 a 和 b 的长度,k 表示当前天数。
if (a >= k && i <= n) f += f * p;
判断当前天数是否符合数组 a 中第 i 个元素的要求,如果符合,则将 f 的值加上 f * p。
if (b >= k && j <= m) f += f * p;
判断当前天数是否符合数组 b 中第 j 个元素的要求,如果符合,则将 f 的值加上 f * p。
cout << fixed << setprecision(4) << f << endl;
输出 f 的值,表示最终状态的解。
总的来说,这段代码的作用是求解一个动态规划问题。该问题的状态转移方程比较简单,主要是根据数组 a 和 b 中的限制条件来计算概率,然后根据概率计算子问题的解。最终,将所有子问题的解进行合并,就可以得到最终的解。
页:
[1]