a + b + c + d…= x

Question

其中a，b，c，d…是介于0-999和x之间的任意整数是固定整数

给出了一个答案，可以使用python对其进行全面有效地计算。

但是，对于很大的数字，循环可能需要数年才能完成。

例如，巨大的数字：

304,153,525,784,175,759

是对x=2700的一种解决方案，因为三位一组加起来等于2700

304+153+525+784+175+759 = 2700

但是，要遍历算法以获得等于该数字的n

th

解将需要数月或数年。

有没有一种方法可以直接计算n

th个解？即对于已知的解决方案，要计算出比该解决方案少的解决方案。

一个先前的问题以词序（从最低到最高）的要求，求出a + b + c + d…= x，其中a，b，c，d ...是0-999和x之间的任意整数一个固定的整数An ...

Answer 1

OP另外询问：

给定索引n，找到n th解决方案，而无需生成所有较早的解决方案。

• 给出解a，找出存在多少个较小的解。

随着算法有效地找到下一个解决方案，您只需要填写当前的解决方案即可。这里是一种以大整数或字符串形式填写当前解决方案的方法：

start = 304153525784175759  # start = '304,153,525,784,175,759'
x = 2700
grouping = 3
max_in_group = 10**grouping - 1

if start is not None:
    if isinstance(start, str):
        a = [int(s) for s in start.split(',')[::-1]]
    else: # suppose start is a large integer
        a = []
        while start != 0:
            a.append(start % (max_in_group+1))
            start //= max_in_group+1
else: # no start value given, start with the smallest
    a = [x]

如果将它放在other answer的其余部分之前，将得到输出：

304,153,525,784,175,759
304,153,525,784,176,758
304,153,525,784,177,757
304,153,525,784,178,756
304,153,525,784,179,755
304,153,525,784,180,754
304,153,525,784,181,753
304,153,525,784,182,752
304,153,525,784,183,751
304,153,525,784,184,750
304,153,525,784,185,749
304,153,525,784,186,748
...

这是一种找到解决方案索引的方法（或：有多少个较小的解决方案）。该代码分为两部分：

Answer 2

对于给定总和n，对于某个固定数目的x组，找到多少个解。这是一个递归函数。基本上，对于n组并求和x，对于从0到999的所有k，求和n-1组有多少解并求和x-k。由于经常使用相同的值来调用递归函数，因此结果存储在备忘录字典中，以备下次使用。