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

Python实战用递归算法解决麻将和牌问题附完整代码解析麻将作为中国传统博弈游戏的精髓其和牌规则的算法实现一直是编程面试中的经典题型。本文将带您从零开始构建一个能够自动判断麻将和牌状态的递归算法不仅适用于面试准备更能帮助理解递归思想在复杂规则系统中的灵活应用。1. 麻将和牌规则解析麻将和牌的基本规则可以拆解为两个核心条件雀头将头14张牌中必须包含且仅包含一对相同的牌如两张9万面子组合剩余的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 False2.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 False2.3 顺子检查实现顺子检查需要当前牌及其1、2的牌都存在def check_sequence(tiles): first tiles[0] if (first1 in tiles) and (first2 in tiles): new_tiles tiles.copy() new_tiles.remove(first) new_tiles.remove(first1) new_tiles.remove(first2) return is_win(new_tiles) return False3. 完整解决方案实现结合上述模块完整的和牌判断程序如下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 (first1 in tiles) and (first2 in tiles): new_tiles tiles.copy() new_tiles.remove(first) new_tiles.remove(first1) new_tiles.remove(first2) 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 剪枝策略优化原始递归存在大量重复计算可以通过以下方式优化排序预处理确保牌始终按升序排列字典计数改用字典记录各牌数量记忆化存储缓存已计算过的牌型优化后的计数版实现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(num1,0) 1 and counts.get(num2,0) 1: new_counts defaultdict(int, counts) new_counts[num] - 1 new_counts[num1] - 1 new_counts[num2] - 1 if is_win_memo(new_counts): return True return False4.2 测试用例设计有效的测试用例应覆盖各种边界情况测试用例预期结果说明1 1 1 2 2 2 5 5 5 6 6 6 99四刻子雀头1 1 1 1 2 2 3 3 5 6 7 8 94 7两种顺子可能1 1 1 2 2 2 3 3 3 5 7 7 90无法和牌1 1 2 2 3 3 4 4 5 5 6 6 71-7七对子特殊牌型本算法不适用调试提示在递归调用前打印当前牌型可以清晰观察算法执行路径5. 工程化扩展建议实际应用中可考虑以下增强功能性能监控添加执行时间统计装饰器日志记录详细记录递归过程可视化工具生成牌型分析图表多规则支持扩展支持七对子、十三幺等特殊牌型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): # ...原有实现...在字节跳动等公司的算法面试中这类问题不仅考察编码能力更关注对递归思想的理解和优化意识。建议读者可以尝试将解决方案从递归改写为迭代方式比较两种实现的性能差异