如何在Python中缩短for循环范围以优化组合数求解代码
问题描述
我需要找到满足组合数公式 (\binom{m}{k} = n) 的最小 (m+k),为此写了一段暴力枚举的Python代码,但运行速度不足。我希望随着 (k) 的推进动态缩短循环范围,不过尝试类似动态修改循环上限的方法并未生效,寻求解决方案。
原代码
import math print("输入为要检查的最大数字$n$,即对1到n之间的所有u,代码给出满足mCk=u的最小m+k,输出格式为$(n , min (m+k : mCk=n)) $") u=int(input()) for n in range (2,u+1): C=[] stop=1 l=0 for m in range (1, n+1): s=0 if stop==-1: break for k in range(1, math.floor(m/2)+1-l): if math.comb(m,k)>n: l=l+1 break if math.comb(m,k)==n: C.insert(s,m+k ) s=s+1 if min(C)<n+1: stop=-1 break print(f"({n},{min(C)}), ")
代码初始输出
( 2, 3), ( 3, 4), ( 4, 5), ( 5, 6), **( 6, 6)**, ( 7, 8), ( 8, 9), ( 9, 10), **( 10, 7)**, ( 11, 12), ( 12, 13), ( 13, 14), ( 14, 15), **( 15, 8)**, ( 16, 17), ( 17, 18), ( 18, 19), ( 19, 20), **( 20, 9)**, **( 21, 9)**, ( 22, 23), ( 23, 24), ( 24, 25), ( 25, 26), ( 26, 27), ( 27, 28), **( 28, 10)**, ( 29, 30), ( 30, 31), ( 31, 32), ( 32, 33), ( 33, 34), ( 34, 35), **( 35, 10)**
核心问题
我尝试了以下代码,发现无法实现动态缩短循环范围的效果,但这正是我需要在自己的组合数代码中实现的功能:
k=0 for i in range (0,100-k+1): if i%2==0: k=k+1
内容的提问来源于stack exchange,提问作者pie
相关产品推荐
相关产品推荐

