user

1
2
3
4
5
6
7
8
9
10
11
12
等待对子
一副标准的52张扑克牌由四个花色各13个点数的牌组成。对子是指两张点数相同的牌。

从一副洗好的扑克牌中无放回地抽牌，目标是连续抽出的两张牌组成对子。例如，前两次抽牌就恰好抽出对子的概率是1/17。

持续抽牌直到抽出对子或所有的牌都已抽完，在后一种情况下抽牌数记为52。

求停止抽牌时抽牌数的期望值，并四舍五入保留八位小数作为你的答案。

我的思路:对于一个数字只有抽到0 1 2 3 4这五个状态,所以可以用 dp[53][14][14][14][14] 表示所有的状态(尽管有一堆状态肯定用不上,不过我们不优化内存),用前面几个状态相减求出最后的状态.
然后直接枚举转移即可,请给我cpp代码实现,记得开long double
这些数字乘起来大概是2e6不会爆内存的

deepseek v4思考

以下是 C++ 代码实现。程序使用概率动态规划，状态记录每种已抽张数的点数种类数以及最后一张牌的点数类别，计算停止抽牌时的期望抽牌数，并输出四舍五入保留八位小数的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <iomanip>

int main() {
    // dp[c1][c2][c3][c4][s] - 概率
    // c1..c4: 已抽出 1,2,3,4 张的点数种类数
    // s: 最后一张牌属于已抽出 s 张的类别 (1 <= s <= 4)
    long double dp[14][14][14][14][5] = {};
    
    // 初始状态：抽完第 1 张牌，此时该点数已抽 1 张
    dp[1][0][0][0][1] = 1.0L;
    
    long double E = 2.0L;  // P(X>0) + P(X>1)
    
    // 递推生成第 2 到第 51 张的无对子概率
    for (int t = 1; t <= 50; ++t) {
        long double ndp[14][14][14][14][5] = {};
        long double Pt_plus_1 = 0.0L;
        int R = 52 - t;  // 剩余牌数
        
        for (int c1 = 0; c1 <= 13; ++c1) {
            for (int c2 = 0; c2 <= 13 - c1; ++c2) {
                for (int c3 = 0; c3 <= 13 - c1 - c2; ++c3) {
                    for (int c4 = 0; c4 <= 13 - c1 - c2 - c3; ++c4) {
                        if (c1 + 2*c2 + 3*c3 + 4*c4 != t) continue;
                        int c0 = 13 - c1 - c2 - c3 - c4;
                        
                        for (int s = 1; s <= 4; ++s) {
                            long double val = dp[c1][c2][c3][c4][s];
                            if (val == 0.0L) continue;
                            
                            // 1. 从未出现的点数中抽取
                            if (c0 > 0) {
                                int ways = c0 * 4;
                                ndp[c1+1][c2][c3][c4][1] += val * (ways / (long double)R);
                            }
                            // 2. 从已抽 1 张的类别中抽取（排除最后一张如果 s=1）
                            int cnt1 = c1 - (s == 1 ? 1 : 0);
                            if (cnt1 > 0) {
                                int ways = cnt1 * 3;
                                ndp[c1-1][c2+1][c3][c4][2] += val * (ways / (long double)R);
                            }
                            // 3. 从已抽 2 张的类别中抽取
                            int cnt2 = c2 - (s == 2 ? 1 : 0);
                            if (cnt2 > 0) {
                                int ways = cnt2 * 2;
                                ndp[c1][c2-1][c3+1][c4][3] += val * (ways / (long double)R);
                            }
                            // 4. 从已抽 3 张的类别中抽取
                            int cnt3 = c3 - (s == 3 ? 1 : 0);
                            if (cnt3 > 0) {
                                int ways = cnt3 * 1;
                                ndp[c1][c2][c3-1][c4+1][4] += val * (ways / (long double)R);
                            }
                        }
                    }
                }
            }
        }
        
        // 累加长度为 t+1 的无对子概率
        for (int c1 = 0; c1 <= 13; ++c1)
            for (int c2 = 0; c2 <= 13 - c1; ++c2)
                for (int c3 = 0; c3 <= 13 - c1 - c2; ++c3)
                    for (int c4 = 0; c4 <= 13 - c1 - c2 - c3; ++c4)
                        for (int s = 1; s <= 4; ++s)
                            Pt_plus_1 += ndp[c1][c2][c3][c4][s];
        
        E += Pt_plus_1;
        
        // 更新 dp
        for (int c1 = 0; c1 <= 13; ++c1)
            for (int c2 = 0; c2 <= 13 - c1; ++c2)
                for (int c3 = 0; c3 <= 13 - c1 - c2; ++c3)
                    for (int c4 = 0; c4 <= 13 - c1 - c2 - c3; ++c4)
                        for (int s = 1; s <= 4; ++s)
                            dp[c1][c2][c3][c4][s] = ndp[c1][c2][c3][c4][s];
    }
    
    std::cout << std::fixed << std::setprecision(8) << E << std::endl;
    return 0;
}

说明：

  • 状态 c1,c2,c3,c4 分别表示已抽出 1、2、3、4 张的点数种类数，c0 = 13 - c1 - c2 - c3 - c4 为未出现的点数种类数。最后一张牌所属的类别由 s 记录。
  • 转移时只能从不同于最后一张牌的其他点数中抽取，权重为可选种数 × 该种类剩余牌数，除以剩余总牌数得到条件概率。
  • 期望公式：E[X] = Σ_{k=0}^{51} P(X > k) = 2 + Σ_{t=2}^{51} P(前 t 张无对子)，代码中累加这些概率得到最终结果。
  • 使用 long double 保证精度，输出格式已设置为保留八位小数。

user

1
炸栈了,把你的dp和ndp提出来变成全局变量,然后改成在你原先定义的位置清零

deepseek v4快速

好的，把大数组放到全局区避免栈溢出，并在循环开头用 memset 清零。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <iomanip>
#include <cstring>

// 全局变量，避免栈溢出
long double dp[14][14][14][14][5];
long double ndp[14][14][14][14][5];

int main() {
    std::memset(dp, 0, sizeof(dp));
    
    // 初始状态：抽完第 1 张牌，此时该点数已抽 1 张
    dp[1][0][0][0][1] = 1.0L;
    
    long double E = 2.0L;  // P(X>0) + P(X>1)
    
    // 递推生成第 2 到第 51 张的无对子概率
    for (int t = 1; t <= 50; ++t) {
        std::memset(ndp, 0, sizeof(ndp));
        long double Pt_plus_1 = 0.0L;
        int R = 52 - t;  // 剩余牌数
        
        for (int c1 = 0; c1 <= 13; ++c1) {
            for (int c2 = 0; c2 <= 13 - c1; ++c2) {
                for (int c3 = 0; c3 <= 13 - c1 - c2; ++c3) {
                    for (int c4 = 0; c4 <= 13 - c1 - c2 - c3; ++c4) {
                        if (c1 + 2*c2 + 3*c3 + 4*c4 != t) continue;
                        int c0 = 13 - c1 - c2 - c3 - c4;
                        
                        for (int s = 1; s <= 4; ++s) {
                            long double val = dp[c1][c2][c3][c4][s];
                            if (val == 0.0L) continue;
                            
                            // 1. 从未出现的点数中抽取
                            if (c0 > 0) {
                                int ways = c0 * 4;
                                ndp[c1+1][c2][c3][c4][1] += val * (ways / (long double)R);
                            }
                            // 2. 从已抽 1 张的类别中抽取（排除最后一张如果 s=1）
                            int cnt1 = c1 - (s == 1 ? 1 : 0);
                            if (cnt1 > 0) {
                                int ways = cnt1 * 3;
                                ndp[c1-1][c2+1][c3][c4][2] += val * (ways / (long double)R);
                            }
                            // 3. 从已抽 2 张的类别中抽取
                            int cnt2 = c2 - (s == 2 ? 1 : 0);
                            if (cnt2 > 0) {
                                int ways = cnt2 * 2;
                                ndp[c1][c2-1][c3+1][c4][3] += val * (ways / (long double)R);
                            }
                            // 4. 从已抽 3 张的类别中抽取
                            int cnt3 = c3 - (s == 3 ? 1 : 0);
                            if (cnt3 > 0) {
                                int ways = cnt3 * 1;
                                ndp[c1][c2][c3-1][c4+1][4] += val * (ways / (long double)R);
                            }
                        }
                    }
                }
            }
        }
        
        // 累加长度为 t+1 的无对子概率
        for (int c1 = 0; c1 <= 13; ++c1)
            for (int c2 = 0; c2 <= 13 - c1; ++c2)
                for (int c3 = 0; c3 <= 13 - c1 - c2; ++c3)
                    for (int c4 = 0; c4 <= 13 - c1 - c2 - c3; ++c4)
                        for (int s = 1; s <= 4; ++s)
                            Pt_plus_1 += ndp[c1][c2][c3][c4][s];
        
        E += Pt_plus_1;
        
        // 将 ndp 复制到 dp
        std::memcpy(dp, ndp, sizeof(dp));
    }
    
    std::cout << std::fixed << std::setprecision(8) << E << std::endl;
    return 0;
}

改动说明：

  • dp 和 ndp 移到全局区，大小约 14^4 * 5 * 16 ≈ 3MB，完全没问题。
  • 每个 t 循环开始时用 memset(ndp, 0, sizeof(ndp)) 清零。
  • 循环末尾用 memcpy 把 ndp 复制到 dp，避免逐元素赋值。
  • 注意头文件是 <cstring>（C++风格），不是 <string.h>。

fun fact

修改之后一发过了,正常倒是.
原先dp写假了,因为当前抽了多少牌也能算出来的,而且需要记录最后的牌的状态.