每日算法 — 使用java实现牛牛：子集枚举与模10同余最优组牌判定

牛牛（又称牛牛、斗牛、Niuniu）是华南地区最流行的扑克牌博弈之一，规则简单到一句话能说完：五张牌，取其中任意三张，若点数和能被 10 整除，就称”有牛”，剩余两张的点数和取模 10 即为牛几，牛牛（余数为 0）最大。虽然规则短，但它的牌型判定是一个很有意思的组合问题：从 5 张牌中选 3 张的组合只有 C(5,3)=10 种，因此可以做到 O(1) 精确判定。

但真正让牛牛成为算法题的，是”手牌评估 + 最优组牌 + 概率期望”这条链路：给定一张手牌，怎么最快判断牛几？给定发牌规则，怎么估计拿到牛牛的概率？给定多家玩家，怎么算自己的胜率？本文用 Java 完整实现从单张牌型判定到多人胜率评估的全套逻辑，核心是子集枚举和模 10 同余两个基本工具。

一、规则拆解与形式化

1.1 牌面与点数映射

注意 10、J、Q、K 的点数都是 10（取模 10 后都是 0），这个细节非常重要：它们对”三张凑 10 的倍数”的贡献是 0，但它们在剩余两张里决定了牛几。

1.2 牛几的定义

设五张牌的点数（模 10 后）为 a[0..4]。若存在三张 i,j,k 使 (a[i]+a[j]+a[k]) % 10 == 0，则牛几 = (a - a[i] - a[j] - a[k]) % 10（即剩余两张点数和模 10）。

• 余数 0 → 牛牛（最大）
• 余数 1~9 → 牛一到牛九（余数越大越强，牛九 > 牛八 > … > 牛一）
• 不存在这样的三张 → 无牛（最小）

1.3 关键数学观察

为什么”取模 10 后相加”是安全的？因为整数模运算对加法同态：(x + y) % 10 = ((x % 10) + (y % 10)) % 10。所以我们可以先把每张牌的点数取模 10（A=1, 10/J/Q/K=0），后续所有运算都在 Z_10 环里进行。

这带来一个极强的化简：五张牌点数模 10 的和是固定的。设总和 S = Σ a[i]，若三张之和 T % 10 == 0，则剩余两张之和 (S - T) % 10 == S % 10。也就是说——牛几其实等于 S % 10，与具体选哪三张无关！

等一下，这句话只对了前半段：只要存在”有牛”的三张组合，那么无论选哪个合法组合，剩余两张的和模 10 都等于 S % 10。所以：

牛几 = S % 10（当且仅当存在三张之和 ≡ 0 mod 10）

这就是牛牛判定能压到 O(1) 的核心定理。我们只需要判断”是否存在三张之和模 10 为 0″，牛几立刻确定。

二、算法设计：从 O(10) 到 O(1) 的三种解法

2.1 解法一：组合枚举（最直白）

C(5,3) = 10，直接三重循环：

for (i = 0; i < 5; i++)
  for (j = i+1; j < 5; j++)
    for (k = j+1; k < 5; k++)
      if ((a[i]+a[j]+a[k]) % 10 == 0) return sum % 10;

优点：正确性显然，代码六行。缺点：牌数扩展到 7 张（如变体玩法）时组合数 C(7,3)=35，扩展到 N 张时变 O(N³)。

2.2 解法二：模 10 计数表（O(N)）

注意到关键信息只有”每个余数出现了几次”。维护一个长度 10 的计数数组 cnt[r]，然后枚举三种余数的组合（r1 ≤ r2 ≤ r3，只需要 C(10+3-1, 3) = 220 种，但实际有效的远少于这个），检查 (r1+r2+r3) % 10 == 0 且计数足够。

对固定 5 张牌，这反而是”更慢”的常数算法；但对 N 张牌的变体（如 7 张选 5 张），它是正解。

2.3 解法三：位运算 + 前缀和（竞赛级）

用一个 10 bit 的位掩码记录”出现了哪些余数”，再用一个 10×10 的布尔表记录”出现了哪些有序对”。检查方案：枚举第一个余数 r1，查表看是否存在 r2 使 (r1+r2) % 10 的补数也出现。这是 O(10) 的固定开销，且完全无分支预测失败，是高性能实现的首选。

2.4 三种解法的适用边界

三、完整 Java 实现

3.1 项目结构

niuniu/
├── src/main/java/com/example/niuniu/
│   ├── Card.java        牌与点数映射
│   ├── Hand.java        一手牌（评估 + 排序）
│   ├── Evaluator.java   三种牛牛判定实现 + 一致性测试
│   ├── Simulator.java   蒙特卡洛胜率模拟
│   └── Main.java        演示与基准测试
└── pom.xml

3.2 Card.java — 牌面建模

package com.example.niuniu;

/**
 * 一张牌。rank: 1(A), 2..10, 11(J), 12(Q), 13(K)。
 * suit: 0 黑桃, 1 红心, 2 梅花, 3 方块。
 * 牛牛的点数映射：A=1，2~9 为面值，10/J/Q/K=10（模 10 后全为 0）。
 */
public final class Card implements Comparable<Card> {

    public final int rank;   // 1..13
    public final int suit;   // 0..3

    public Card(int rank, int suit) {
        if (rank < 1 || rank > 13) throw new IllegalArgumentException("rank 越界: " + rank);
        if (suit < 0 || suit > 3)  throw new IllegalArgumentException("suit 越界: " + suit);
        this.rank = rank;
        this.suit = suit;
    }

    /** 牛牛点数：A=1，2~10 为面值，J/Q/K=10 */
    public int point() {
        if (rank == 1) return 1;
        if (rank >= 11) return 10;
        return rank;
    }

    /** 模 10 点数：用于"凑 10 倍数"判定，10/J/Q/K 全部为 0 */
    public int pointMod10() { return point() % 10; }

    /** 排序用：先按点数降序，再按花色 */
    @Override public int compareTo(Card o) {
        if (this.point() != o.point()) return Integer.compare(o.point(), this.point());
        return Integer.compare(this.suit, o.suit);
    }

    @Override public String toString() {
        String[] suits = {"♠", "♥", "♣", "♦"};
        String r;
        if (rank == 1) r = "A";
        else if (rank == 11) r = "J";
        else if (rank == 12) r = "Q";
        else if (rank == 13) r = "K";
        else r = String.valueOf(rank);
        return suits[suit] + r;
    }
}

3.3 Hand.java — 手牌与评估结果

package com.example.niuniu;

import java.util.List;

/**
 * 一手牌（5 张）的评估结果。
 * level：-1 表示无牛；0 表示牛牛（最高）；1..9 表示牛一到牛九。
 */
public final class Hand {

    public final Card[] cards;
    public final int level;        // -1 无牛，0 牛牛，1..9 牛几
    public final int[] bullTriple; // 凑成 10 倍数的那三张的下标（无牛时为 null）

    Hand(Card[] cards, int level, int[] bullTriple) {
        this.cards = cards;
        this.level = level;
        this.bullTriple = bullTriple;
    }

    public boolean hasBull() { return level >= 0; }

    /** 用于比较大小的强度值：牛牛=100，牛九=99 ... 牛一=91，无牛=0 */
    public int strength() {
        if (level < 0) return 0;
        if (level == 0) return 100;
        return 90 + level;
    }

    @Override public String toString() {
        StringBuilder sb = new StringBuilder();
        for (Card c : cards) sb.append(c).append(' ');
        sb.append(" => ").append(levelName());
        return sb.toString();
    }

    public String levelName() {
        if (level < 0) return "无牛";
        if (level == 0) return "牛牛";
        return "牛" + level;
    }

    static Hand of(List<Card> list, int level, int[] triple) {
        return new Hand(list.toArray(new Card[0]), level, triple);
    }
}

3.4 Evaluator.java — 三种判定实现

package com.example.niuniu;

import java.util.ArrayList;
import java.util.List;

/**
 * 牛牛判定的三种实现，全部基于同一条核心定理：
 *   若存在三张牌点数之和 ≡ 0 (mod 10)，则牛几 = 五张牌总点数 mod 10。
 * 因为"剩余两张之和" = 总和 - 三张之和 ≡ 总和 (mod 10)，与选哪三张无关。
 */
public final class Evaluator {

    private Evaluator() {}

    // ============ 实现一：组合枚举 O(C(5,3)) = 10 次 ============

    /**
     * 最直白的实现：枚举 10 种三张牌组合。
     * 正确性最容易验证，作为其他实现的黄金基准（golden reference）。
     */
    public static Hand evaluateByEnumeration(List<Card> hand) {
        if (hand.size() != 5) throw new IllegalArgumentException("牛牛必须是 5 张牌");
        int[] a = new int[5];
        int sum = 0;
        for (int i = 0; i < 5; i++) { a[i] = hand.get(i).pointMod10(); sum += a[i]; }

        for (int i = 0; i < 5; i++) {
            for (int j = i + 1; j < 5; j++) {
                for (int k = j + 1; k < 5; k++) {
                    if ((a[i] + a[j] + a[k]) % 10 == 0) {
                        // 找到一组即可：牛几 = 总和 mod 10（与选哪三张无关）
                        return Hand.of(hand, sum % 10, new int[]{i, j, k});
                    }
                }
            }
        }
        return Hand.of(hand, -1, null);   // 无牛
    }

    // ============ 实现二：模 10 计数表，支持 N 张选 5 张变体 ============

    /**
     * 通用版本：适用于 N 张牌（N ≥ 3）的"取 3 张凑 10"判定。
     * 维护余数计数数组 cnt[0..9]，枚举三种余数的有序组合（r1 ≤ r2 ≤ r3）。
     * 复杂度 O(N + 220)，对 7 张牌的变体玩法优势明显。
     */
    public static int[] findBullTripleGeneric(int[] points) {
        int n = points.length;
        int[] cnt = new int[10];
        for (int p : points) cnt[p % 10]++;
        int sum = 0;
        for (int p : points) sum += p % 10;

        for (int r1 = 0; r1 < 10; r1++) {
            if (cnt[r1] == 0) continue;
            for (int r2 = r1; r2 < 10; r2++) {
                if (cnt[r2] == 0) continue;
                if (r1 == r2 && cnt[r2] < 2) continue;
                int need = (10 - (r1 + r2) % 10) % 10;   // 第三张需要的余数
                if (need < r2) continue;                  // 保证 r1 ≤ r2 ≤ r3，避免重复枚举
                if (cnt[need] == 0) continue;
                // 还要检查"需要的张数"是否充足（r1/r2/need 可能重叠）
                if (need == r1 && need == r2 && cnt[need] < 3) continue;
                if (need == r2 && r1 != r2 && cnt[need] < 2) continue;
                if (need == r1 && r1 != r2 && cnt[need] < 2) continue;
                // 返回三个余数（调用方自行找具体下标）
                return new int[]{r1, r2, need};
            }
        }
        return null;
    }

    // ============ 实现三：位掩码 O(10) 常数 ============

    /**
     * 位掩码版本：mask 的第 r 位表示"余数 r 至少出现一次"。
     * 三重余数组合的检查用位运算表达：存在性判定不关心具体张数（除三张同余的情况）。
     *
     * 关键技巧：把"是否存在 r1, r2, r3 使和为 10 的倍数"改写为
     *   for r1 in 0..9:  target = (10 - r1) % 10
     *                    检查 mask 中是否存在 r2 使得 (r2 + target) % 10 也在 mask 里
     * 配合一个预计算的 PAIR_TABLE[r2] = 与 r2 相加能和为 10 的倍数的余数集合
     */
    private static final int[] COMPLEMENT_OF = new int[10];
    static {
        for (int r = 0; r < 10; r++) COMPLEMENT_OF[r] = (10 - r) % 10;
    }

    /**
     * 位掩码判定。返回牛几（-1 表示无牛）。
     * 注意：仅凭"出现过"的掩码会漏掉"三张同余需要至少 3 张"的边界，
     * 因此额外维护 repeatMask（出现过 ≥2 次的余数）来处理退化情形。
     */
    public static int evaluateByBitmask(List<Card> hand) {
        if (hand.size() != 5) throw new IllegalArgumentException("牛牛必须是 5 张牌");
        int mask = 0, repeatMask = 0, sum = 0;
        int[] cnt = new int[10];
        for (Card c : hand) {
            int r = c.pointMod10();
            sum += r;
            cnt[r]++;
            mask |= (1 << r);
            if (cnt[r] >= 2) repeatMask |= (1 << r);
        }

        boolean found = false;
        for (int r1 = 0; r1 < 10 && !found; r1++) {
            if ((mask & (1 << r1)) == 0) continue;
            // 情况 A：三张余数各不相同 —— 两两不同的 r2, r3 同时出现即可
            for (int r2 = 0; r2 < 10; r2++) {
                if (r2 == r1) continue;
                if ((mask & (1 << r2)) == 0) continue;
                int r3 = (10 - (r1 + r2) % 10) % 10;
                if (r3 == r1 || r3 == r2) continue;       // 交给后面的退化分支
                if ((mask & (1 << r3)) != 0) { found = true; break; }
            }
            if (found) break;

            // 情况 B：r1 出现两次 + 另一个 r2，满足 (2*r1 + r2) % 10 == 0
            if ((repeatMask & (1 << r1)) != 0) {
                int r2 = (10 - (2 * r1) % 10) % 10;
                if (r2 != r1 && (mask & (1 << r2)) != 0) { found = true; break; }
            }
            // 情况 C：三张全是 r1，需 3*r1 % 10 == 0 且 r1 出现 ≥3 次
            if (cnt[r1] >= 3 && (3 * r1) % 10 == 0) { found = true; break; }
        }
        return found ? sum % 10 : -1;
    }

    /** 统一入口：默认用枚举版（正确性优先） */
    public static Hand evaluate(List<Card> hand) {
        return evaluateByEnumeration(hand);
    }
}

3.5 Simulator.java — 蒙特卡洛胜率

package com.example.niuniu;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

/**
 * 蒙特卡洛模拟：估计"单家手牌"强弱分布，以及"多家对局中某一家胜率"。
 *
 * 关键点：牛牛是"比大小"游戏，同 level 时需要比最大单牌与花色，
 * 这里简化为主牌比较（牛几 + 最大牌点数），足够说明算法结构。
 */
public final class Simulator {

    /** 从 52 张牌中随机发 n 张（不放回），用 Fisher-Yates 洗牌 */
    static List<Card> deal(Random rnd, int n) {
        List<Card> deck = new ArrayList<>(52);
        for (int suit = 0; suit < 4; suit++)
            for (int rank = 1; rank <= 13; rank++)
                deck.add(new Card(rank, suit));
        Collections.shuffle(deck, rnd);
        return new ArrayList<>(deck.subList(0, n));
    }

    /** 统计"拿到牛牛"的概率（理论值需用精确组合计数，这里用模拟对照） */
    public static double probNiuNiu(int trials, long seed) {
        Random rnd = new Random(seed);
        int hit = 0;
        for (int i = 0; i < trials; i++) {
            Hand h = Evaluator.evaluate(deal(rnd, 5));
            if (h.level == 0) hit++;
        }
        return (double) hit / trials;
    }

    /** 统计牛几的分布：返回长度 11 的数组，索引 0 = 牛牛，1..9 = 牛几，10 = 无牛 */
    public static int[] levelDistribution(int trials, long seed) {
        Random rnd = new Random(seed);
        int[] dist = new int[11];
        for (int i = 0; i < trials; i++) {
            Hand h = Evaluator.evaluate(deal(rnd, 5));
            if (h.level < 0) dist[10]++;
            else dist[h.level]++;
        }
        return dist;
    }

    /** 估计某手牌在 k 家对局中的胜率（其他家用同样算法评估，同 level 比最大牌） */
    public static double winRate(List<Card> myHand, int players, int trials, long seed) {
        Random rnd = new Random(seed);
        int wins = 0;
        for (int t = 0; t < trials; t++) {
            // 从剩余 47 张里洗牌，其他人各发 5 张
            List<Card> deck = new ArrayList<>(52);
            for (int suit = 0; suit < 4; suit++)
                for (int rank = 1; rank <= 13; rank++) {
                    Card c = new Card(rank, suit);
                    boolean used = false;
                    for (Card m : myHand) if (m.rank == c.rank && m.suit == c.suit) used = true;
                    if (!used) deck.add(c);
                }
            Collections.shuffle(deck, rnd);

            int myStrength = Evaluator.evaluate(myHand).strength();
            int myTopPoint = topPoint(myHand);
            boolean allLost = false;
            for (int p = 0; p < players - 1; p++) {
                List<Card> other = new ArrayList<>(deck.subList(p * 5, p * 5 + 5));
                int s = Evaluator.evaluate(other).strength();
                int op = topPoint(other);
                // 同 level 时比最大单牌点数
                if (s > myStrength || (s == myStrength && op > myTopPoint)) { allLost = true; break; }
            }
            if (!allLost) wins++;
        }
        return (double) wins / trials;
    }

    private static int topPoint(List<Card> hand) {
        int mx = 0;
        for (Card c : hand) mx = Math.max(mx, c.point());
        return mx;
    }
}

3.6 Main.java — 演示与基准

package com.example.niuniu;

import java.util.*;

public final class Main {

    public static void main(String[] args) {
        // ========== ① 单张手牌判定演示 ==========
        System.out.println("===== 单张手牌判定 =====");
        List<Card> h1 = List.of(new Card(10, 0), new Card(13, 1),
                                new Card(9, 2), new Card(2, 3), new Card(7, 0));
        // 点数模 10：0, 0, 9, 2, 7；和 = 18；找三张凑 10：0+0+? 需 0 → 无；9+2+? 无
        Hand hd1 = Evaluator.evaluate(h1);
        System.out.println("  " + hd1);

        List<Card> h2 = List.of(new Card(8, 0), new Card(9, 1),
                                new Card(3, 2), new Card(10, 3), new Card(5, 0));
        // 0,9,3,0,5 → 和 17；8+? 试 0+0+... ; 3+? ; 8(8)+... 
        // 实际：0+0+? 需 0 → 只有两个 0；3+0+? 需 7 → 无；5+? 
        Hand hd2 = Evaluator.evaluate(h2);
        System.out.println("  " + hd2);

        List<Card> h3 = List.of(new Card(6, 0), new Card(4, 1),
                                new Card(10, 2), new Card(2, 3), new Card(8, 0));
        // 6,4,0,2,8 → 和 20；6+4+0=10 ✓ → 牛几 = 20%10 = 0 → 牛牛
        Hand hd3 = Evaluator.evaluate(h3);
        System.out.println("  " + hd3);

        // ========== ② 三种实现一致性交叉验证 ==========
        System.out.println("\n===== 三种实现交叉验证（随机 10 万手） =====");
        Random rnd = new Random(20261104L);
        int mismatch = 0;
        for (int t = 0; t < 100000; t++) {
            List<Card> hand = Simulator.deal(rnd, 5);
            int enumLevel  = Evaluator.evaluateByEnumeration(hand).level;
            int maskLevel  = Evaluator.evaluateByBitmask(hand);
            if (enumLevel != maskLevel) {
                mismatch++;
                if (mismatch <= 3) {
                    System.out.println("  不一致！枚举=" + enumLevel + " 掩码=" + maskLevel
                            + " 手牌=" + hand);
                }
            }
        }
        System.out.println("  不一致次数：" + mismatch + " / 100000");

        // ========== ③ 牛几分布与牛牛概率 ==========
        System.out.println("\n===== 100 万手模拟：牛几分布 =====");
        int[] dist = Simulator.levelDistribution(1000000, 7788L);
        for (int i = 0; i <= 9; i++)
            System.out.printf("  牛%-2d : %8d  (%6.3f%%)%n", i == 0 ? 0 : i, dist[i],
                    dist[i] * 100.0 / 1000000);
        System.out.printf("  无牛  : %8d  (%6.3f%%)%n", dist[10], dist[10] * 100.0 / 1000000);

        // ========== ④ 性能基准 ==========
        System.out.println("\n===== 性能基准（100 万次评估） =====");
        List<List<Card>> hands = new ArrayList<>(1000);
        Random r2 = new Random(99L);
        for (int i = 0; i < 1000; i++) hands.add(Simulator.deal(r2, 5));

        long t0 = System.nanoTime();
        int sink = 0;
        for (int i = 0; i < 1000000; i++) sink += Evaluator.evaluateByEnumeration(hands.get(i % 1000)).level;
        long t1 = System.nanoTime();
        System.out.printf("  枚举版：%.1f ms（%.3f µs/次）sink=%d%n",
                (t1 - t0) / 1e6, (t1 - t0) / 1000.0 / 1e6, sink);

        t0 = System.nanoTime(); sink = 0;
        for (int i = 0; i < 1000000; i++) sink += Evaluator.evaluateByBitmask(hands.get(i % 1000));
        t1 = System.nanoTime();
        System.out.printf("  掩码版：%.1f ms（%.3f µs/次）sink=%d%n",
                (t1 - t0) / 1e6, (t1 - t0) / 1000.0 / 1e6, sink);

        // ========== ⑤ 胜率示例 ==========
        System.out.println("\n===== 胜率模拟（4 家对局） =====");
        double wr = Simulator.winRate(h3, 4, 200000, 4242L);
        System.out.printf("  手牌 [%s] 在 4 家对局中胜率：%.2f%%%n",
                h3.toString().replace(" => 牛牛", ""), wr * 100);
    }
}

3.7 pom.xml

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0">
  <modelVersion>4.0.0</modelVersion>
  <groupId>com.example</groupId>
  <artifactId>niuniu</artifactId>
  <version>1.0.0</version>
  <properties>
    <maven.compiler.source>17</maven.compiler.source>
    <maven.compiler.target>17</maven.compiler.target>
  </properties>
  <build>
    <plugins>
      <plugin>
        <groupId>org.apache.maven.plugins</groupId>
        <artifactId>maven-jar-plugin</artifactId>
        <configuration>
          <archive><manifest><mainClass>com.example.niuniu.Main</mainClass></manifest></archive>
        </configuration>
      </plugin>
    </plugins>
  </build>
</project>

四、复杂度分析与实测

关键性能观察：位掩码版的优势不在运算量（相差不到 3 倍），而在于没有依赖数据的嵌套循环，CPU 分支预测几乎 100% 命中。在批量模拟场景（比如做大规模 AI 训练数据生成）中，这个常数因子差异会被放大到可观测的量级。

五、易错点与边界情形

5.1 牛几与”选哪三张”无关——但前提是”有牛”

这条定理只在”存在合法三张”时成立。如果手牌无牛，sum % 10 完全无意义（比如点数 2,3,5 的手牌和是 10，但没有三张能凑 10，此时必须判无牛，不能因为 sum%10==0 就误判牛牛）。

这是新手最常犯的错误：先算总和，再看余数，忘了检查”有牛”的前提。

5.2 同余计数要处理”三张同余”

位掩码版最容易漏掉的边界是 (3 * r) % 10 == 0，即 r ∈ {0}（因为 3 与 10 互质，只有 r=0 满足）。所以”三张都是 10/J/Q/K”的牌型必须额外判断”余数 0 至少出现 3 次”。本文用 repeatMask + cnt[r1] >= 3 双重检查覆盖了这一情形。

5.3 花色与最大牌比较

牛牛同 level 时的比法在不同地区有差异（有的比最大单牌，有的比花色，有的比”牛牛里的最大牌”）。本文简化成”最大单牌点数”，实际接入业务时需要把这个比较器抽成可配置的策略接口——因为这是纯规则差异，不该硬编码在评估器里。

5.4 发牌是否放回

Simulator.deal 用的是 Fisher-Yates 不放回发牌，这是真牌桌的物理约束。如果误用”放回”发牌，牛牛的概率会显著偏高（因为同余 0 的牌可以重复出现），模拟结果就完全失真。

六、小结

牛牛的算法内核只有一个定理：有牛 → 牛几 = 总点数 mod 10。把这条定理挖出来，整个问题从”枚举组合 + 逐组验证”塌缩成”一次余数统计”。

三个可迁移的方法论：

• 模运算同态性是化简组合问题的第一把刀——先取模，再枚举，量级立刻降下来；
• 常数级问题的三种实现（枚举 / 计数 / 位掩码）各有适用边界，选型看 N 是否固定；
• 黄金基准（golden reference） 是组合类算法不可或缺的工程手段：用最笨的枚举版交叉验证高性能版 10 万手，任何边界错误都无处可逃。