算法案例 03：购票排队找零组合算法求解#

本报告探讨球赛购票找零问题的组合数学模型（卡特兰数 / 路径计数）与 C++ 算法实现。

---

一、 题目描述#

球票每张 50 元。现有 30 人排队，其中 20 人手持 50 元面值，10 人手持 100 元面值。

售票处初始无零钱。求使售票处不出现找不开钱局面时的不同排队种数（相同面值之间不区分人）。

---

二、 组合数学建模（网格路径 / 卡特兰数扩展）#

将手持 50 元视为在二维网格中向右走一步 $(+1, 0)$，手持 100 元视为向上走一步 $(0, +1)$。

• 总人数为 $m + n = 20 + 10 = 30$；
• 初始在原点 $(0,0)$，目标到达 $(20, 10)$；
• 找零不出现中断的充要条件为：在任意时刻，已收到的 50 元张数不少于 100 元张数，即网格路径不能穿过直线 $y = x$（满足 $x \ge y$）。

由折线法（Reflection Method），合法的排队路径数 $C$ 为： $C = \binom{m+n}{n} - \binom{m+n}{n-1} = \binom{30}{10} - \binom{30}{9}$

---

三、 C++ 算法实现#

#include <iostream>
using namespace std;

// 计算组合数 C(n, k)
long long nCr(int n, int k) {
    if (k < 0 || k > n) return 0;
    if (k == 0 || k == n) return 1;
    if (k > n / 2) k = n - k;
    long long res = 1;
    for (int i = 1; i <= k; i++) {
        res = res * (n - i + 1) / i;
    }
    return res;
}

int main() {
    int m = 20; // 50元人数
    int n = 10; // 100元人数

    long long total_combinations = nCr(m + n, n);
    long long invalid_combinations = nCr(m + n, n - 1);
    long long valid_ways = total_combinations - invalid_combinations;

    cout << "总排队组合数: " << total_combinations << endl;
    cout << "不合法排队数: " << invalid_combinations << endl;
    cout << "合法排队种数: " << valid_ways << endl;

    return 0;
}

---

四、 求解结果#

• $\binom{30}{10} = 30,045,015$
• $\binom{30}{9} = 14,307,150$
• 合法排队种数为：$30,045,015 - 14,307,150 =$ 15,737,865 种。