如何优化将正整数分解为4个正偶数之和的Python程序？

问题描述 #

输入正整数N，统计将其分解为恰好4个正偶数之和的有序方式数（不同顺序视为不同分解，如示例中的4种情况）。现有暴力解法采用三重循环，时间复杂度为O(N³)，当N≥1000时运行明显变慢，N=10000时需耗时6分钟且CPU占用率达70%，需优化为更高效的实现方案。

示例：当N=10时，共有4种分解方式：

10 = 2 + 2 + 2 + 4
10 = 2 + 2 + 4 + 2
10 = 2 + 4 + 2 + 2
10 = 4 + 2 + 2 + 2

现有暴力解法问题 #

现有代码通过三重循环枚举a、b、c，计算d=N-a-b-c后验证是否为正偶数，时间复杂度O(N³)，当N增大时性能急剧下降：

import os
import sys

def count_way_decompose(n: int):
    count: int = 0

    for a in range(2, n - 5 + 1, 2):
        for b in range(2, n - a - 3 + 1, 2):
            for c in range(2, n - a - b - 1 + 1, 2):
                d = n - a - b - c

                if d >= 2 and d % 2 == 0:
                    count += 1

    print(f"We have {count} ways to decompose {n} into sum of four even positive integers")

if __name__ == "__main__":
    n = int(input("N = "))
    count_way_decompose(n)

数学优化方案 #

通过数学转换将问题简化为组合数计算，时间复杂度降至O(1)：

1. 变量替换：设四个正偶数为a=2x、b=2y、c=2z、d=2w，其中x、y、z、w均为正整数（因a,b,c,d≥2且为偶数）。
2. 方程转换：原等式a+b+c+d=N可转化为2(x+y+z+w)=N，即x+y+z+w = S，其中S = N/2。
3. 解的条件：
   • 若N为奇数或N<8，直接返回0（因最小的四个正偶数和为8，且N必须是偶数才能被2整除）。
   • 若N≥8且为偶数，问题转化为求方程x+y+z+w=S的正整数有序解个数，根据隔板法，该数目为组合数C(S-1, 3)，计算公式为：

     count = (S-1) * (S-2) * (S-3) // 6
     

     （注：组合数C(n,k) = n!/(k!(n-k)!)，此处n=S-1，k=3，展开后即为上述公式）

优化后的代码 #

def count_way_decompose(n: int):
    # 先判断是否有解
    if n < 8 or n % 2 != 0:
        count = 0
    else:
        s = n // 2
        # 计算组合数 C(s-1, 3)
        count = (s - 1) * (s - 2) * (s - 3) // 6
    print(f"We have {count} ways to decompose {n} into sum of four even positive integers")

if __name__ == "__main__":
    n = int(input("N = "))
    count_way_decompose(n)

验证示例 #

当N=10时，S=5，计算得(5-1)*(5-2)*(5-3)//6 = 4*3*2//6 = 24//6=4，与示例结果一致。对于N=10000，S=5000，计算(4999)*(4998)*(4997)//6可瞬间得到结果，完全解决原暴力解法的性能问题。

内容的提问来源于stack exchange，提问作者duckk404