Python实战：用递归算法解决麻将和牌问题（附完整代码解析）

Python实战：用递归算法解决麻将和牌问题（附完整代码解析）

麻将作为中国传统博弈游戏的精髓，其和牌规则的算法实现一直是编程面试中的经典题型。本文将带您从零开始构建一个能够自动判断麻将和牌状态的递归算法，不仅适用于面试准备，更能帮助理解递归思想在复杂规则系统中的灵活应用。

1. 麻将和牌规则解析

麻将和牌的基本规则可以拆解为两个核心条件：

1. 雀头（将头）：14张牌中必须包含且仅包含一对相同的牌（如两张9万）
2. 面子组合：剩余的12张牌需要组成4个顺子（连续三张）或刻子（相同三张）

以实际牌型为例：

1 1 1 2 2 2 6 6 6 7 7 7 9 9

• 雀头：9万
• 面子：111（刻子）、222（刻子）、666（刻子）、777（刻子）

1 1 1 1 2 2 3 3 5 6 7 7 8 9

• 雀头：1万
• 面子：123（顺子）、123（顺子）、567（顺子）、789（顺子）

关键点：每种数字牌最多出现4次，当手牌为13张时，需要计算补哪张牌能满足和牌条件。

2. 递归算法设计框架

递归解决和牌问题的核心思路是逐步消减牌型直到空牌：

def is_win(tiles): if not tiles: # 基线条件：牌已全部匹配 return True # 检查三种可能的匹配方式 return (check_pair(tiles) or check_triplet(tiles) or check_sequence(tiles))

2.1 雀头检查实现

雀头检查需要满足：

• 当前牌的数量≥2
• 移除雀头后剩余牌数能被3整除（因为面子都是3张一组）

def check_pair(tiles): if len(tiles) % 3 != 0: # 只有牌数=2,5,8,11,14时需要检查雀头 first = tiles[0] if tiles.count(first) >= 2: new_tiles = tiles.copy() new_tiles.remove(first) new_tiles.remove(first) return is_win(new_tiles) return False

2.2 刻子检查实现

刻子检查相对简单，只需确认当前牌是否≥3张：

def check_triplet(tiles): first = tiles[0] if tiles.count(first) >= 3: new_tiles = tiles.copy() new_tiles.remove(first) new_tiles.remove(first) new_tiles.remove(first) return is_win(new_tiles) return False

2.3 顺子检查实现

顺子检查需要当前牌及其+1、+2的牌都存在：

def check_sequence(tiles): first = tiles[0] if (first+1 in tiles) and (first+2 in tiles): new_tiles = tiles.copy() new_tiles.remove(first) new_tiles.remove(first+1) new_tiles.remove(first+2) return is_win(new_tiles) return False

3. 完整解决方案实现

结合上述模块，完整的和牌判断程序如下：

def is_win(tiles): if not tiles: return True # 雀头检查 if len(tiles) % 3 != 0: first = tiles[0] if tiles.count(first) >= 2: new_tiles = tiles[2:] if is_win(new_tiles): return True # 刻子检查 first = tiles[0] if tiles.count(first) >= 3: new_tiles = tiles[3:] if is_win(new_tiles): return True # 顺子检查 if (first+1 in tiles) and (first+2 in tiles): new_tiles = tiles.copy() new_tiles.remove(first) new_tiles.remove(first+1) new_tiles.remove(first+2) if is_win(new_tiles): return True return False def find_winning_tiles(hand): result = [] for tile in range(1, 10): if hand.count(tile) >= 4: # 每种牌最多4张 continue test_hand = sorted(hand + [tile]) if is_win(test_hand): result.append(tile) return result if result else [0] if __name__ == '__main__': hand = list(map(int, input().split())) print(' '.join(map(str, find_winning_tiles(hand))))

4. 算法优化与调试技巧

4.1 剪枝策略优化

原始递归存在大量重复计算，可以通过以下方式优化：

1. 排序预处理：确保牌始终按升序排列
2. 字典计数：改用字典记录各牌数量
3. 记忆化存储：缓存已计算过的牌型

优化后的计数版实现：

from collections import defaultdict def is_win_memo(counts): total = sum(counts.values()) if total == 0: return True # 尝试作为雀头 if total % 3 == 2: for num in counts: if counts[num] >= 2: new_counts = defaultdict(int, counts) new_counts[num] -= 2 if is_win_memo(new_counts): return True # 尝试作为刻子 for num in counts: if counts[num] >= 3: new_counts = defaultdict(int, counts) new_counts[num] -= 3 if is_win_memo(new_counts): return True # 尝试作为顺子 for num in counts: if counts[num] >=1 and counts.get(num+1,0) >=1 and counts.get(num+2,0) >=1: new_counts = defaultdict(int, counts) new_counts[num] -= 1 new_counts[num+1] -= 1 new_counts[num+2] -= 1 if is_win_memo(new_counts): return True return False

4.2 测试用例设计

有效的测试用例应覆盖各种边界情况：

调试提示：在递归调用前打印当前牌型，可以清晰观察算法执行路径

5. 工程化扩展建议

实际应用中可考虑以下增强功能：

1. 性能监控：添加执行时间统计装饰器
2. 日志记录：详细记录递归过程
3. 可视化工具：生成牌型分析图表
4. 多规则支持：扩展支持七对子、十三幺等特殊牌型

import time from functools import wraps def timeit(func): @wraps(func) def wrapper(*args, **kwargs): start = time.time() result = func(*args, **kwargs) print(f"{func.__name__} executed in {time.time()-start:.4f}s") return result return wrapper @timeit def find_winning_tiles(hand): # ...原有实现...

在字节跳动等公司的算法面试中，这类问题不仅考察编码能力，更关注对递归思想的理解和优化意识。建议读者可以尝试将解决方案从递归改写为迭代方式，比较两种实现的性能差异