Python编程解构古代数学：从鸡兔同笼到中国剩余定理

1. 项目概述当古算题遇上现代编程最近在整理资料时翻到一些中国古代的数学典籍像《九章算术》、《孙子算经》这些里面记载的题目真是精妙。比如“鸡兔同笼”、“百钱买百鸡”这些题目不仅考验逻辑更蕴含着古人解决问题的智慧。我就在想这些流传了千百年的问题如果放到今天用我们最熟悉的Python来求解会是一种怎样的体验这不仅仅是把古文翻译成代码更像是一场跨越时空的对话用现代的计算思维去重新解构古人的智慧。对于正在学习Python的朋友来说这更是一个绝佳的练手机会算法逻辑清晰场景生动有趣还能顺便了解点历史文化一举多得。所以我决定动手把几个经典的古算题用Python实现一遍。这个过程远比想象中有趣你不仅是在写代码更像是在扮演一位古代的“筹算家”只不过你的算筹变成了键盘和解释器。无论是想巩固Python基础语法、练习循环与条件判断还是对算法逻辑感兴趣亦或是单纯想找点有文化味的编程题目这个“中国古代数学问题Python实现”的项目都值得一试。接下来我会带你一起从最基础的“鸡兔同笼”开始逐步深入到更复杂的“物不知数”中国剩余定理看看Python如何优雅地解开这些千年谜题。2. 核心思路与算法选型面对一个古算题直接埋头写代码往往事倍功半。我的习惯是先拆解题目明确背后的数学模型再选择最合适的Python实现方式。古算题大多属于“构造性数学”或“枚举算法”的范畴核心是找到满足一系列条件的所有可能解。2.1 问题抽象与数学建模这是最关键的一步。我们需要暂时忘掉“鸡”、“兔”、“钱”这些具体事物把它们抽象成变量和方程。以最著名的“鸡兔同笼”为例出自《孙子算经》今有雉兔同笼上有三十五头下有九十四足。问雉兔各几何抽象设鸡雉有x只兔有y只。建模根据题意可列出二元一次方程组x y 35头的总数2*x 4*y 94足的总数你看一个生动的场景立刻变成了清晰的数学问题。对于“百钱买百鸡”出自《张邱建算经》鸡翁一值钱五鸡母一值钱三鸡雏三值钱一。凡百钱买百鸡。问鸡翁、母、雏各几何抽象设公鸡、母鸡、小鸡的数量分别为a,b,c。建模条件转化为a b c 100鸡的总数5*a 3*b c/3 100钱的总数隐含条件a, b, c均为非负整数且c必须是3的倍数因为小鸡三只值一钱。建模完成后解题策略就清晰了。2.2 算法策略选择暴力枚举 vs. 数学解析对于古算题Python实现主要有两种思路1. 暴力枚举法穷举法这是最直观、最适合编程初学者的方法。其核心思想是在合理的范围内列举所有可能的变量组合然后逐一验证是否满足所有条件。适用场景问题规模不大变量的可能取值范围明确且有限。例如“百钱买百鸡”公鸡最多买20只因为100钱全买公鸡母鸡最多买33只这个枚举量对计算机来说微不足道。Python优势利用for循环可以非常简洁地实现多层嵌套枚举代码可读性强。思考要点枚举范围需要根据题意手动优化尽可能缩小循环次数这是提升代码效率的关键。2. 数学解析法方程求解对于像“鸡兔同笼”这类能转化为线性方程组的问题我们可以直接用代数方法求解然后将求解过程用代码表达。适用场景问题可被精确建模为线性方程组且有唯一解或有限解。Python优势代码极其简洁几乎是对数学公式的直接翻译性能最优。思考要点需要一定的数学推导能力但一旦推导出公式代码将非常高效。在实际项目中我通常会先尝试数学解析法如果问题复杂如不定方程再辅以枚举法。对于教学和展示而言两种方法都实现一遍对比之下对算法思维的理解会深刻得多。注意选择算法时一定要考虑“整数解”的约束。古算题的解几乎都是正整数或非负整数这是建模和编程验证时必须加入的条件否则会得到不符合实际如半只鸡的数学解。3. 经典问题Python实现详解下面我们挑选三个最具代表性的问题分别用不同的方法实现并附上详细的代码注释和思路讲解。3.1 鸡兔同笼二元一次方程的直接求解这个问题是线性方程组的典型应用最适合用解析法。def chicken_rabbit(total_heads, total_legs): 解决鸡兔同笼问题 :param total_heads: 总头数 :param total_legs: 总脚数 :return: (鸡的数量兔的数量) 如果无解返回None # 数学推导 # 设鸡为c兔为r # c r total_heads - (1) # 2*c 4*r total_legs - (2) # 将(1)式乘以2: 2*c 2*r 2*total_heads - (3) # (2)式减去(3)式: 2*r total_legs - 2*total_heads # 因此r (total_legs - 2 * total_heads) / 2 # 再由(1)式c total_heads - r # 计算兔子的数量 rabbit (total_legs - 2 * total_heads) / 2 # 计算鸡的数量 chicken total_heads - rabbit # 验证解是否为非负整数 if rabbit 0 and chicken 0 and rabbit.is_integer() and chicken.is_integer(): return int(chicken), int(rabbit) else: return None # 测试《孙子算经》原题 heads 35 legs 94 result chicken_rabbit(heads, legs) if result: print(f鸡有{result[0]}只兔有{result[1]}只) else: print(无解题目数据可能有误)代码解读与心得核心是数学代码的核心是那两行计算公式它们直接来源于对方程组的推导。在写代码前在草稿纸上完成推导至关重要。验证环节不可少即使数学上rabbit和chicken是整数我们也必须验证它们是否非负。因为如果输入的总脚数过少比如头35脚50公式会算出负数的兔子这显然不合理。is_integer()方法用于检查是否为整数因为除法可能产生浮点数。函数化设计将功能封装成函数参数是头数和脚数这样就能轻松求解任何同类问题而不仅仅是原题。这是写出复用性高代码的好习惯。3.2 百钱买百鸡三重循环枚举与优化这是一个典型的不定方程问题存在多组解非常适合用枚举法。def hundred_chickens(): 百钱买百鸡问题求解 solutions [] # 最直接的枚举法三重循环 print(方法一三重循环枚举) for cock in range(0, 101): # 公鸡数量从0到100 for hen in range(0, 101): # 母鸡数量从0到100 for chick in range(0, 101): # 小鸡数量从0到100 if (cock hen chick 100) and \ (5*cock 3*hen chick/3 100): # 注意小鸡数量必须是3的倍数 if chick % 3 0: solutions.append((cock, hen, chick)) print(f找到 {len(solutions)} 组解{solutions}) # 优化后的枚举法减少循环层数和范围 print(\n方法二优化后的枚举) solutions_optimized [] for cock in range(0, 21): # 公鸡最多买20只 (100/5) for hen in range(0, 34): # 母鸡最多买33只 (100/3 取整) chick 100 - cock - hen # 利用总数约束直接计算小鸡数 if chick 0 and chick % 3 0: # 小鸡数必须非负且是3的倍数 if 5*cock 3*hen chick/3 100: solutions_optimized.append((cock, hen, chick)) print(f找到 {len(solutions_optimized)} 组解{solutions_optimized}) return solutions_optimized # 执行 hundred_chickens()代码解读与心得从暴力到优化方法一展示了最朴素的思路但它的循环次数是101101101 ≈ 100万次虽然对现代计算机不算什么但思维上不够经济。方法二进行了关键优化缩小枚举范围根据价格限制公鸡不会超过20只母鸡不会超过33只。这直接将外层循环次数从100降到了20和33。减少循环层数利用cock hen chick 100这个条件当我们确定了公鸡和母鸡的数量后小鸡的数量可以直接算出来 (chick 100 - cock - hen)从而省去了最内层的循环。这是“消元”思想在枚举法中的应用。提前判断在计算总价前先判断小鸡数是否为非负整数且是3的倍数不满足则直接跳过避免不必要的计算。浮点数陷阱注意在判断总价时我们使用了chick/3。在Python 3中这是浮点数除法。虽然这里chick是3的倍数结果是精确的但更严谨的写法是使用整数除法chick // 3或者将方程两边乘以3以避免除法15*cock 9*hen chick 300。我在实际编码中更喜欢后一种方式完全在整数域内运算避免任何浮点数精度可能带来的问题。结果验证运行代码后我们会得到四组解(0,25,75), (4,18,78), (8,11,81), (12,4,84)。可以代入原题验证完全正确。3.3 物不知数中国剩余定理模运算的优雅应用这个问题出自《孙子算经》有物不知其数三三数之剩二五五数之剩三七七数之剩二。问物几何 这是一个同余方程组问题是“中国剩余定理”的起源。我们可以用枚举法也可以用定理的公式解法。def find_number_enumeration(remainders): 使用枚举法求解物不知数问题通用版 :param remainders: 一个列表格式为 [(除数1, 余数1), (除数2, 余数2), ...] :return: 满足条件的最小正整数解 # 找出所有除数中最大的一个作为搜索的起始步长优化技巧 divisors [d for d, _ in remainders] max_divisor max(divisors) # 从最大除数开始搜索可以减少无用的检查次数 n max_divisor 1 # 解至少比最大除数大 while True: # 使用 all() 函数检查是否满足所有同余条件代码更简洁 if all(n % d r for d, r in remainders): return n n 1 def find_number_crt(remainders): 使用中国剩余定理CRT公式求解物不知数问题针对两两互质的除数 :param remainders: 同余方程组除数需两两互质 :return: 满足条件的最小正整数解 # 计算所有除数的乘积 N divisors [d for d, _ in remainders] N 1 for d in divisors: N * d result 0 for d, r in remainders: # 计算 Ni N / ni Ni N // d # 计算 Ni 在模 ni 下的乘法逆元 Mi (即 Mi * Ni ≡ 1 (mod ni)) # 这里使用简单的遍历法求逆元因为除数很小 Mi 1 while (Mi * Ni) % d ! 1: Mi 1 # 累加 ai * Mi * Ni result r * Mi * Ni # 返回模 N 下的最小正整数解 return result % N # 求解《孙子算经》原题 problem [(3, 2), (5, 3), (7, 2)] print(问题一个数除以3余2除以5余3除以7余2求这个数。) print(f同余式: {problem}) # 方法一枚举法 solution_enum find_number_enumeration(problem) print(f\n枚举法求得的最小解为: {solution_enum}) # 方法二中国剩余定理公式法 solution_crt find_number_crt(problem) print(f中国剩余定理求得的最小解为: {solution_crt}) # 验证 print(f\n验证) for d, r in problem: print(f {solution_crt} % {d} {solution_crt % d} (期望余数 {r}))代码解读与心得枚举法的优化在find_number_enumeration函数中我没有从1开始逐个尝试而是从最大除数加1开始。因为解至少要比任何一个除数大否则余数不可能等于除数-1。这是一个很小的优化但在除数很大时能节省时间。更重要的是我使用了all()这个内置函数让条件判断的代码非常清晰易读。中国剩余定理的实现find_number_crt函数实现了标准的中国剩余定理求解步骤。关键在于求乘法逆元Mi。这里我用了最简单的while循环遍历因为题目中的除数3,5,7很小。如果除数很大就需要用扩展欧几里得算法来高效求逆元这是一个可以深入优化的点。通用性设计我将两个函数都设计成接收一个remainders列表这样就可以求解任何同类型的“物不知数”问题而不仅仅是原题。例如输入[(2,1), (3,2), (5,4)]也能求解。数学与编程的结合这个例子完美展示了如何将深奥的数学定理中国剩余定理转化为清晰的算法步骤和简洁的代码。理解定理的每一步计算N、Ni、Mi、累加、取模是写出正确代码的前提。4. 扩展实践与算法思维提升掌握了几个经典问题的解法后我们可以尝试一些变体或更复杂的问题这能极大锻炼算法思维和代码抽象能力。4.1 韩信点兵大规模枚举的效率挑战“韩信点兵”问题可以看作是“物不知数”的推广但通常数字更大。例如士兵每排3人余2每排5人余3每排7人余4问至少有多少兵 我们依然可以用枚举法但当解可能很大时从1开始线性搜索会非常慢。这时我们可以用“步进式枚举”进行优化。def hanxin_soldier(remainders): 优化版韩信点兵求解步进式枚举 # 按除数从大到小排序用大除数确定搜索步长能更快逼近解 remainders_sorted sorted(remainders, keylambda x: x[0], reverseTrue) largest_div, largest_rem remainders_sorted[0] # 从满足最大除数的条件开始搜索并以该除数为步长 n largest_rem while n % largest_div ! largest_rem: # 确保起始点满足第一个条件虽然已满足但保留逻辑 n 1 # 核心优化每次增加 largest_div而不是1 # 因为解在满足“除以largest_div余largest_rem”的数中它们之间的差是largest_div的倍数 while True: if all(n % d r for d, r in remainders_sorted): return n n largest_div # 关键步进 # 测试 problem [(3, 2), (5, 3), (7, 4)] print(f求解韩信点兵问题: {problem}) result hanxin_soldier(problem) print(f最小士兵数为: {result}) print(f验证: 除以3余{result%3}, 除以5余{result%5}, 除以7余{result%7})心得这个优化将搜索次数从线性级O(N)降低到了接近常数级。其原理是一旦找到一个数n满足对最大除数d_large的余数条件那么下一个可能满足该条件的数至少是n d_large。我们以d_large为步长跳跃式搜索跳过了大量绝对不满足第一个条件的数字效率提升巨大。这是解决大规模枚举问题的经典思路。4.2 打造一个古算题求解器面向对象封装为了让代码更有组织性也为了能方便地添加新问题我们可以设计一个简单的求解器框架。class AncientMathSolver: 古算题求解器基类 def solve(self): 求解方法子类必须实现 raise NotImplementedError(子类必须实现solve方法) def explain(self): 输出解题思路 print(f问题{self.description}) print(解题思路与过程...) class ChickenRabbitSolver(AncientMathSolver): 鸡兔同笼问题求解器 def __init__(self, heads, legs): self.description f鸡兔同笼共{heads}头{legs}足。 self.heads heads self.legs legs def solve(self): 使用解析法求解 # 解方程 rabbit (legs - 2*heads)/2 rabbit (self.legs - 2 * self.heads) / 2 chicken self.heads - rabbit if rabbit 0 and chicken 0 and rabbit.is_integer() and chicken.is_integer(): return int(chicken), int(rabbit) return None def explain(self): super().explain() print( 设鸡有x只兔有y只。) print(f 根据题意可得方程组) print(f x y {self.heads} (1)) print(f 2x 4y {self.legs} (2)) print( 由(1)得 x 头数 - y代入(2)式求解...) class HundredChickensSolver(AncientMathSolver): 百钱买百鸡问题求解器 def __init__(self): self.description 百钱买百鸡公鸡5文/只母鸡3文/只小鸡1文/3只。 def solve(self): 使用优化枚举法求解 solutions [] for cock in range(0, 21): for hen in range(0, 34): chick 100 - cock - hen if chick % 3 0 and 5*cock 3*hen chick//3 100: solutions.append((cock, hen, chick)) return solutions # 使用求解器 print( 古算题求解器演示 ) cr_solver ChickenRabbitSolver(35, 94) cr_solver.explain() result cr_solver.solve() print(f 解得鸡{result[0]}只兔{result[1]}只\n) hc_solver HundredChickensSolver() hc_solver.explain() solutions hc_solver.solve() print(f 找到{len(solutions)}组解) for i, sol in enumerate(solutions, 1): print(f 第{i}组公鸡{sol[0]}母鸡{sol[1]}小鸡{sol[2]})心得使用面向对象的方式将每个问题封装成一个类好处非常明显高内聚每个问题的数据如头数、脚数和方法求解、解释都封装在一起结构清晰。易扩展要新增一个古算题比如“李白沽酒”、“三女归宁”只需要新建一个类继承AncientMathSolver并实现solve和explain方法即可无需修改其他代码。易使用对于使用者来说只需要创建对应的求解器对象调用solve()方法就能得到答案调用explain()就能看到思路交互友好。这种设计模式特别适合管理一系列类似但又有差异的问题是工程化思维的体现。5. 常见问题、调试技巧与性能考量在实际编码和教学过程中我遇到过不少共性问题这里总结一下希望能帮你少走弯路。5.1 浮点数精度与整数运算这是数学编程中最常见的坑。看这段代码# 有风险的写法 if chick / 3 some_value: # chick是整数但chick/3是浮点数 ... # 推荐的写法 if chick * 3 some_value * 3: # 等式两边同时乘以3保持整数运算 # 或者 if chick // 3 some_value: # 使用整数除法我的经验在处理古算题这类纯整数问题时尽量将方程变形使所有运算都在整数域内进行。比较浮点数是否相等时应使用abs(a - b) 1e-10这样的容差比较而不是直接a b。5.2 枚举范围的确定与优化不假思索地使用range(0, 101)进行三重循环虽然对百钱百鸡问题可行但是一种思维上的懒惰。优化枚举范围是算法竞赛和实际编程中的基本功。优化思路根据约束条件推导上限如百钱百鸡公鸡上限是总钱数 / 公鸡单价。利用等式消元如已知总数枚举其中两个变量第三个可以直接算出。调整枚举顺序先枚举变化范围小的变量可以减少内层循环的判断次数。使用步进跳跃如韩信点兵中的“步进式枚举”。5.3 多解处理与解的验证对于存在多解的问题如百钱百鸡你的程序是否能找出所有解对于有唯一解的问题如鸡兔同笼你的程序在无解或输入非法时是否会崩溃或给出错误结果健壮性检查清单输入验证头数和脚数是否为正整数脚数是否至少是头数的2倍全是鸡且至多是头数的4倍全是兔解的存在性数学公式或枚举结束后是否判断了解的存在性如chicken_rabbit函数中的if...return...else判断。多解收集使用列表solutions []和solutions.append(...)来收集所有满足条件的解。结果验证编写一个简单的验证函数将得到的解代回原题条件进行检验。这对于复杂问题尤其重要。5.4 从具体到抽象编写通用求解函数当你熟练掌握单个问题的解法后可以挑战自己编写更通用的函数。例如能否写一个通用的“同余方程组求解器”它应该能处理任意组数、任意两两互质除数的“物不知数”问题。def solve_congruence_system(equations): 通用同余方程组求解除数需两两互质 equations: [(a1, n1), (a2, n2), ...] 表示 x ≡ a1 (mod n1), x ≡ a2 (mod n2), ... 返回满足条件的最小正整数解 # 实现中国剩余定理通用算法 # 1. 计算 N n1 * n2 * ... # 2. 对每个 i计算 Ni N / ni # 3. 对每个 i计算 Mi Ni 在模 ni 下的乘法逆元 # 4. x sum(ai * Mi * Ni) mod N # 5. 返回 x pass尝试实现这个函数你会对模运算、扩展欧几里得算法有更深的理解。这也是将具体项目经验转化为通用编程能力的关键一步。5.5 性能对比与算法选择对于小规模问题枚举法和解析法速度差异微乎其微。但建立性能意识很重要。我们可以用Python的time模块简单对比一下。import time def performance_test(): 对比枚举法和CRT定理法的性能 problem [(3, 2), (5, 3), (7, 2)] # 测试枚举法搜索到1000 start time.perf_counter() for n in range(1, 1001): if all(n % d r for d, r in problem): pass # 找到解也不停止测试搜索性能 elapsed_enum time.perf_counter() - start # 测试CRT法执行1000次 start time.perf_counter() for _ in range(1000): find_number_crt(problem) elapsed_crt time.perf_counter() - start print(f枚举法搜索前1000个数耗时: {elapsed_enum:.6f} 秒) print(fCRT定理法计算1000次耗时: {elapsed_crt:.6f} 秒) print(fCRT法速度大约是枚举法的 {elapsed_enum/elapsed_crt:.1f} 倍在此测试条件下) performance_test()你会发现对于有确定公式的算法CRT其计算时间是常数级的与解的大小无关。而枚举法的耗时则与搜索范围成正比。当搜索范围很大时这种差异会是数量级的。这直观地告诉我们好的数学建模往往能带来最优的算法效率。最后分享一点个人体会。用Python解古算题最初可能只是觉得好玩但深入下去你会发现它强迫你进行清晰的逻辑分解、严谨的边界条件思考以及对整数运算特性的细致把握。这些能力对于解决任何编程问题都是通用的。下次当你遇到一个复杂的业务逻辑时不妨也试试这种“数学建模算法选择代码实现”的思路你会发现很多问题都豁然开朗了。