44 lines
1.3 KiB
Python
44 lines
1.3 KiB
Python
import time
|
||
|
||
|
||
def timer(func):
|
||
def wrapper(*args, **kwargs):
|
||
start_time = time.time()
|
||
result = func(*args, **kwargs)
|
||
end_time = time.time()
|
||
elapsed_time = end_time - start_time
|
||
print(f"{func.__name__} time: {elapsed_time:.6f} seconds")
|
||
return result
|
||
|
||
return wrapper
|
||
|
||
|
||
@timer
|
||
def count_combinations_above_million(limit_n=100, threshold=1_000_000):
|
||
"""
|
||
对于 1 ≤ n ≤ limit_n，统计组合数 C(n, r) 大于 threshold 的个数。
|
||
利用递推 C(n, r) = C(n, r-1) * (n - r + 1) / r 以及对称性 C(n, r) = C(n, n-r)。
|
||
"""
|
||
count = 0
|
||
|
||
for n in range(1, limit_n + 1):
|
||
comb = 1 # C(n, 0)
|
||
# 只需检查 r 从 1 到 n//2
|
||
for r in range(1, n // 2 + 1):
|
||
# 递推更新组合数
|
||
comb = comb * (n - r + 1) // r
|
||
|
||
if comb > threshold:
|
||
# 一旦找到最小的 r 使得 C(n, r) > threshold，
|
||
# 则 r 到 n-r 之间的所有值都满足条件。
|
||
# 符合条件的个数 = (n - r) - r + 1 = n - 2*r + 1
|
||
count += n - 2 * r + 1
|
||
break # 该 n 的剩余情况不必再检查
|
||
|
||
return count
|
||
|
||
|
||
if __name__ == "__main__":
|
||
result = count_combinations_above_million()
|
||
print(result)
|