从麦乐鸡到赌徒破产：我用Python复现了5道经典量化面试题（附完整代码）

从麦乐鸡到赌徒破产我用Python复现了5道经典量化面试题附完整代码在量化金融领域面试官常常会通过一些看似简单的数学概率题来考察候选人的逻辑思维和编程能力。这些题目往往蕴含着深刻的数学原理而用代码实现它们不仅能验证理论更能培养量化从业者必备的计算思维。本文将带你用Python复现5道经典面试题从麦乐鸡组合问题到赌徒破产理论每道题都配有完整代码和详细解析。1. 麦乐鸡问题数论与动态规划的完美结合麦当劳的麦乐鸡块通常以6、9、20块为单位出售。这道经典题目问无法用这些包装组合得到的最大数量是多少数学上这被称为货币问题或邮票问题。1.1 数学解法分析首先我们需要理解题目背后的数论原理。由于6和9都是3的倍数任何大于等于6的3的倍数都可以用6和9组合得到。而20除以3余2所以通过组合20和6、9我们可以得到20 6 26 (余2)20 9 29 (余2)40 6 46 (余1)40 9 49 (余1)通过这种模式我们可以证明43之后的所有数字都能被表示。1.2 Python实现我们可以用动态规划来验证这个结论def max_non_mcnugget_number(): sizes [6, 9, 20] max_check 200 # 足够大的检查范围 dp [False] * (max_check 1) dp[0] True for i in range(max_check 1): if dp[i]: for size in sizes: if i size max_check: dp[i size] True max_non -1 for i in range(max_check 1): if not dp[i]: max_non i return max_non print(f无法组合的最大麦乐鸡数量是: {max_non_mcnugget_number()})运行这段代码会输出43验证了我们的数学推导。动态规划在这里创建了一个布尔数组dp其中dp[i]为True表示i可以用给定包装组合得到。2. 赌徒破产问题概率论的生动案例赌徒破产问题是概率论中的经典案例也是量化金融中风险管理的理论基础之一。题目描述一个赌徒初始有i元每次赌博有p概率赢1元(1-p)概率输1元。当他资产达到n元或0元时停止。求他带着n元离开的概率。2.1 数学建模这是一个典型的马尔可夫过程可以用差分方程来建模。设u(i)为从i元开始最终达到n元的概率则有u(i) p*u(i1) (1-p)*u(i-1)边界条件为u(0)0u(n)1。2.2 Python模拟与解析解我们可以同时用蒙特卡洛模拟和解析解来验证import numpy as np def gamblers_ruin_simulation(i, n, p, trials10000): successes 0 for _ in range(trials): current i while current 0 and current n: if np.random.random() p: current 1 else: current - 1 if current n: successes 1 return successes / trials def gamblers_ruin_analytic(i, n, p): if p 0.5: return i / n else: return (1 - ((1-p)/p)**i) / (1 - ((1-p)/p)**n) # 示例初始10元目标20元赢的概率0.4 i, n, p 10, 20, 0.4 sim_prob gamblers_ruin_simulation(i, n, p) ana_prob gamblers_ruin_analytic(i, n, p) print(f模拟概率: {sim_prob:.4f}) print(f解析解: {ana_prob:.4f})这个例子展示了如何将概率理论转化为可运行的代码。当p≠0.5时解析解涉及指数函数当p0.5时退化为线性函数。3. 糖果罐问题组合概率的实际应用糖果罐里有10红、20蓝、30绿糖果不放回地抽取求在取完所有红糖果时至少剩下1蓝和1绿的概率。3.1 概率分析这个问题可以转化为考察红色糖果在蓝色和绿色糖果中的排列位置。我们需要计算在所有红色糖果被取出前蓝色和绿色糖果都未被取完的概率。3.2 Python实现我们可以用排列组合和蒙特卡洛两种方法解决from itertools import permutations from math import factorial from random import sample def candy_jar_analytic(): total 60 red 10 blue 20 green 30 # 计算蓝色和绿色都晚于红色的概率 # 使用对称性只考虑红色、蓝色和绿色的最后出现顺序 # 我们需要红色是第一个被取完的即最后一个是蓝色或绿色 # 且在红色取完前蓝色和绿色都至少剩一个 # 更精确的计算方法 def prob_last(color): # 计算指定颜色最后出现的概率 return color / (red color) # 使用容斥原理计算 prob 1 - prob_last(blue) - prob_last(green) prob_last(blue green) return prob def candy_jar_simulation(trials100000): red, blue, green 10, 20, 30 success 0 for _ in range(trials): jar [R]*red [B]*blue [G]*green remaining {R: red, B: blue, G: green} while True: # 随机抽取一个 pick np.random.choice(jar) jar.remove(pick) remaining[pick] - 1 # 检查终止条件 if remaining[R] 0: if remaining[B] 0 and remaining[G] 0: success 1 break elif remaining[B] 0 or remaining[G] 0: break return success / trials print(f解析解概率: {candy_jar_analytic():.4f}) print(f模拟概率: {candy_jar_simulation():.4f})4. 木棍三角形问题几何概率的编程验证将长度为1的木棍随机折成三段求这三段能构成三角形的概率。4.1 数学分析设两个断点为x和y0xy1则三段长度为x, y-x, 1-y。要构成三角形必须满足三角不等式x (y-x) 1-y ⇒ y 0.5x (1-y) y-x ⇒ y x 0.5(y-x) (1-y) x ⇒ x 0.54.2 Python实现我们可以用数值积分和蒙特卡洛两种方法def triangle_analytic(): # 满足条件的区域面积 # 使用对称性只计算xy的情况然后乘以2 from scipy.integrate import dblquad def integrand(y, x): return 1 if (y 0.5 and y x 0.5 and x 0.5) else 0 # 积分区域x从0到1y从x到1 integral, _ dblquad(integrand, 0, 1, lambda x: x, lambda x: 1) return integral def triangle_simulation(trials100000): count 0 for _ in range(trials): x, y sorted([np.random.random(), np.random.random()]) a, b, c x, y - x, 1 - y if a b c and a c b and b c a: count 1 return count / trials print(f解析解概率: {triangle_analytic():.4f}) print(f模拟概率: {triangle_simulation():.4f})5. 酒鬼行走问题随机游走的量化视角酒鬼站在桥上每次随机向左或向右走1米直到掉下桥。求在两侧下桥的概率及期望步数。5.1 理论分析这是一个有吸收壁的随机游走问题。设酒鬼初始位置距离左侧a米右侧b米。在左侧下桥的概率为b/(ab)右侧为a/(ab)。期望时间为ab。5.2 Python模拟def drunkard_walk(a, b, trials10000): left_exits 0 total_steps 0 for _ in range(trials): position a steps 0 while True: steps 1 # 随机向左或向右移动 position np.random.choice([-1, 1]) # 检查是否掉下桥 if position 0: left_exits 1 break elif position a b: break total_steps steps prob_left left_exits / trials avg_steps total_steps / trials return prob_left, avg_steps a, b 3, 7 # 举例距离左侧3米右侧7米 sim_prob, sim_steps drunkard_walk(a, b) theory_prob b / (a b) theory_steps a * b print(f模拟左侧概率: {sim_prob:.4f} (理论: {theory_prob:.4f})) print(f模拟平均步数: {sim_steps:.2f} (理论: {theory_steps}))代码优化与量化应用在实际量化面试中仅仅实现功能是不够的还需要考虑代码的效率和优化。例如在赌徒破产问题的蒙特卡洛模拟中我们可以使用向量化操作来提高速度def vectorized_gamblers_ruin(i, n, p, trials100000): current np.full(trials, i) while True: mask (current 0) (current n) if not mask.any(): break steps np.sum(mask) current[mask] np.where(np.random.random(steps) p, 1, -1) return np.mean(current n)这种向量化实现比循环快10倍以上在处理大规模模拟时优势明显。在量化金融中这种优化技巧对于高频交易策略的回测至关重要。