算法题: 把一个整数分解成数个连续整数相加的结果

前言

前些天，先后参加了两家公司的线上笔试，在其中一家公司的笔试题里面遇到了一些算法实现，感觉挺有意思，上来分享一下。

题目

题目：部分整数可以写成数个连续正整数之和，如5=2+3，10=1+2+3+4，也有部分整数存在多个分解方案，如15=1+2+3+4+5=4+5+6=7+8.
写出一个程序，输入一个整数，输出最短的分解方案，如无法分解，则输出该整数。
例：输入15，输出15=7+8；输入8，因为8无法分解，输出8.

解题思路：

笔者认为, 这道题的考点有2:

1. 运算求解部分

2. 格式化输出部分(当然这一部分显得很简单)

下面文章的内容主要会描述运算求解的内容, 并且笔者会给出多个思路, 为了方便, 笔者在求解之前先约定了处理输出这部分内容.

输出约定

编写一个函数partition(N), 对整数N进行分解, 如判断无法分解,则直接返回N, 如果可以分解, 则使用list返回分解结果.

如:

partition(15), 输出[7,8];

partition(8), 输出8.

再编写一个函数answer(N), 负责对答案进行格式化输出, 代码如下:

def answer(N):
    result = partition(N)
    if type(result) is list:
        output_string = '+'.join(str(item) for item in result )
        output_string = f'{N}={output_string}'
    elif type(result) is int:
        return N
    return output_string

穷举法求解

如果不加入太多数学范畴的思考，那我们可以有一个穷举求解的思路.

以分解整数9为例子,思路描述如下:

1. 从1+2开始, 1+2=3, 1+2+3=6, 1+2+3+4=10

2. 10>9, 证明以1为起始的连续自然数无法累加得到9, 接下来从2开始进行累加

3. 2+3=5, 2+3+4=9

4. 9=9, 得到一个解: 9=2+3+4. 接着尝试以3为起始值进行累加

5. 3+4=7, 3+4+5=12

6. 12>9, 证明以3为起始的连续自然数无法累加得到9, 接下来从4开始进行累加

7. 4+5=9

8. 得到另一个解9=4+5

9. 很明显, 9=4+5已经是最优解, 已无需接续迭代.

整理以上的循环过程, 关键在于挖掘一个能累加出目标数值的起始值, 直到找到一个最优解.

用简单代码实现, 可以写成:

def partition_1(N):
    if N < 3:
        return N
    start = 1
    end = 2
    sum = start + end
    answer_list = []
    while True:
        if N == sum:
            answer_list.append(list(range(start, end+1, 1)))
            start = start + 1
            end = start + 1
            sum = start + end
        elif sum < N:
            end = end + 1
            sum = sum + end
        else:
            start = start + 1
            end = start + 1
            sum = start + end
        if start > int(N//2):
            break
    if answer_list:
        # 很明显, 最后加入answer_list, start数值是最大的, 就会是最短的最优解
        return(answer_list[-1])
    else:
        return N

等差数列求和

回忆高中数学知识, 等差数列前n项和的公式为: $S_n = a_1 * n + \frac{n * ( n - 1 ) }{2} * d$

即, 我们需要找到一个首项为$a_1$, 公差是1, 的一个等差数列, 并使该数列的前n项和为题目给出的整数N: $N=a_1 * n + \frac{n * (n-1)}{2}$

又因为题目要求我们要找到n最小的解, 所以在代码中进行迭代的时候, 我们可以从n=2开始, 而等差数列的$a_1$自然是从N//2开始, 并不断减小.

因为从n=2开始进行迭代, 当我们能找到正确的$a_1$之后, 已经不需要继续迭代下去, 就可以结束循环了. 用简单的for循环, 通过(a1, n)就可以把这个等差数列还原, 找到答案.

def partition_2(N):
    result = []
    if N < 3 :
        return N
    else:
        temp_result = None
        flag = False
        for n in range(2,N//2, 1):
            for a1 in range(N//2, 0, -1):
                if N == a1 *n + n * (n-1) / 2:
                    flag = True
                    temp_result = (a1, n)
                    break
            if flag:
                break
        if flag:
            for i in range(n):
                result.append(a1+i)
        else:
            return N
    return result

取巧

这里加入一点数学分析, 假如一个整数N能被表达成n个连续整数的和, 例如:20=2+3+4+5+6=(2+0)+(2+1)+(2+2)+(2+3)+(2+4)=2*5+(0+1+2+3+4)

当我们对这个现象进行抽象化表达, 即: $N=a_1*n+(0+1+2+3+…+n-1)$, 移项得: $N - \frac{n * (n-1)}{2} = a_1 * n$

显然, 这个上面跟求和公式大差不差, 但笔者想要表达的是, 当给出一个固定的n时, 如果存在一个a1能满足N == a1 *n + n * (n-1) / 2, 即a1存在整数解, 求解公式是: $a_1 = \frac{N - \frac{n * (n-1)}{2}}{n}, a_1\in Z$.

当$a_1$存在整数解的时候, 那我们就知道这个n是对的, 并迅速能求出$a_1$, 如果没有整数解, 我们可以直接n=n+1, 就不需要通过反复迭代$a_1$来求解了.

代码实现如下:

def check_aviable(N,n):
    # 判断能否有整数解
    if (N-int(n*(n-1)/2))%n == 0:
        return(int((N-int(n*(n-1)/2))/n),n)
    else:
        return False

def partition_3(N):
    if N in (0,1,2):
        return N
    for n in range(2,N,1):
        result = check_aviable(N, n)
        if result:
            break
        else:
            continue
    if result:
        answer = []
        for i in range(result[1]):
            answer.append(result[0]+i)
        return answer
    else:
        return N

测试运行一下

测试用例分别是[8, 15, 123123, 122224, 1231231, 65536].

为了直观地感受各个算法的效果, 我们再引入一个修饰器去记录运算时间.

from time import time 
  
def timer_func(func): 
    # This function shows the execution time of  
    # the function object passed 
    def wrap_func(*args, **kwargs): 
        t1 = time() 
        result = func(*args, **kwargs) 
        t2 = time() 
        print(f'Function {func.__name__!r} executed in {(t2-t1):.4f}s') 
        return result 
    return wrap_func 

partition_1

使用穷举法, 其实也没有很慢, 运行结果如下:

Function 'partition_1' executed in 0.0000s
8
Function 'partition_1' executed in 0.0000s
[7, 8]
Function 'partition_1' executed in 0.1748s
[61561, 61562]
Function 'partition_1' executed in 0.1740s
[3804, 3805, 3806, 3807, 3808, 3809, 3810, 3811, 3812, 3813, 3814, 3815, 3816, 3817, 3818, 3819, 3820, 3821, 3822, 3823, 3824, 3825, 3826, 3827, 3828, 3829, 3830, 3831, 3832, 3833, 3834, 3835]
Function 'partition_1' executed in 2.0361s
[615615, 615616]
Function 'partition_1' executed in 0.0823s
65536

partition_2

在这个算法下, 计算像65536这种无法分解的大数, 效率最低, 比上面的穷举法还要慢.

运行结果如下:

Function 'partition_2' executed in 0.0000s
8
Function 'partition_2' executed in 0.0000s
[7, 8]
Function 'partition_2' executed in 0.0000s
[61561, 61562]
Function 'partition_2' executed in 0.4697s
[3804, 3805, 3806, 3807, 3808, 3809, 3810, 3811, 3812, 3813, 3814, 3815, 3816, 3817, 3818, 3819, 3820, 3821, 3822, 3823, 3824, 3825, 3826, 3827, 3828, 3829, 3830, 3831, 3832, 3833, 3834, 3835]
Function 'partition_2' executed in 0.0000s
[615615, 615616]
Function 'partition_2' executed in 253.7682s
65536

partition_3

这是目前看到最高效率的算法了, 运行结果如下:

Function 'partition_3' executed in 0.0000s
8
Function 'partition_3' executed in 0.0000s
[7, 8]
Function 'partition_3' executed in 0.0000s
[61561, 61562]
Function 'partition_3' executed in 0.0000s
[3804, 3805, 3806, 3807, 3808, 3809, 3810, 3811, 3812, 3813, 3814, 3815, 3816, 3817, 3818, 3819, 3820, 3821, 3822, 3823, 3824, 3825, 3826, 3827, 3828, 3829, 3830, 3831, 3832, 3833, 3834, 3835]
Function 'partition_3' executed in 0.0000s
[615615, 615616]
Function 'partition_3' executed in 0.0305s
65536

再来看看结果吧

根据题目的要求, 按照特定的格式输出答案, 输出如下:

8
15=7+8
123123=61561+61562
122224=3804+3805+3806+3807+3808+3809+3810+3811+3812+3813+3814+3815+3816+3817+3818+3819+3820+3821+3822+3823+3824+3825+3826+3827+3828+3829+3830+3831+3832+3833+3834+3835
1231231=615615+615616
65536

随感

我在写这篇文章的时候, 看到自己在一道算法题上能想出3个解, 耳边隐隐约约想起了鲁迅笔下的孔乙己那句”回字有四样写法”.