实现整数拆分算法：将整数拆分为1、5、10的合规分组

问题定义 #

输入整数n，将其拆分为仅包含1、5、10的数值集合，需满足：

1. 拆分后的元素数量尽可能少；
2. 元素数量至少为3个（若n<3，因无法凑出3个正整数和等于n，直接返回n个1）。

算法思路 #

分三步处理，核心是先通过贪心算法得到无数量限制的最优拆分，再根据元素数是否达标调整：

1. 边界处理：若n<3，直接返回n个1；
2. 贪心最优拆分：优先使用大数值（10→5→1），计算各数值的数量及总元素数：
   • count_10 = n // 10，剩余值rem = n % 10；
   • count_5 = rem // 5，剩余值rem = rem % 5；
   • count_1 = rem；
   • 总元素数total = count_10 + count_5 + count_1；
3. 调整拆分（若元素数不足3）：
   • 若total≥3：直接返回贪心拆分结果；
   • 若total=1（仅n=5或n=10）：
     • n=5：拆分为5个1；
     • n=10：拆分为5 + 5个1（元素数6，是满足条件的最少方案）；
   • 若total=2：
     • 拆分列表含10：将一个10拆为两个5，元素数变为3（最优）；
     • 拆分列表仅含5和1（仅n=6）：将5拆为5个1，得到6个1。

代码实现（Python） #

def split_number(n):
    if n < 3:
        return ', '.join(['1'] * n)
    
    # 贪心计算各数值数量
    count_10 = n // 10
    rem = n % 10
    count_5 = rem // 5
    rem = rem % 5
    count_1 = rem
    
    parts = []
    parts.extend([10] * count_10)
    parts.extend([5] * count_5)
    parts.extend([1] * count_1)
    total = len(parts)
    
    if total >= 3:
        return ', '.join(map(str, parts))
    
    # 处理元素数不足3的情况
    if total == 1:
        if n == 5:
            return ', '.join(['1'] * 5)
        elif n == 10:
            return ', '.join(['5'] + ['1'] * 5)
    elif total == 2:
        if 10 in parts:
            # 将一个10拆为两个5
            parts.remove(10)
            parts.extend([5, 5])
            return ', '.join(map(str, parts))
        else:
            # 将5拆为5个1
            parts.remove(5)
            parts.extend(['1'] * 5)
            return ', '.join(map(str, parts))

测试验证 #

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