用x的校验和查找所有n个数字

Question

我正在寻找一种算法，该算法能够找到所有n个长且校验和为x（最好在python或golang中）的数字，以将其嵌入大型程序，这就是为什么它需要具有低时间复杂度。

示例：

findNumbers(2,5)

[[23，32，14，41，50]

findNumbers(10,90)

[9999999999]

Answer 1

以下代码查找所有所需的数字。您要使用除基数10以外的其他基数来运行参数max_in_group。

该代码首先创建a值的列表num_digits。列表中的每个条目代表一位数字。为了使代码更通用，可以设置最大位数。十进制为9，八角形为7。如果将3个小数位加在一起，甚至是999。 （现在，打印将打印所有十进制的内容，但可以轻松地将基数大于10进行调整。）

此数组a不必总是所有数字都低于10。第一步将最后一位的溢出重新分配给较早的一位。现在，当溢出需要额外的数字时，代码将停止。

在步骤2中，寻找后继者。如果不会发生溢出，则只需将倒数第二位加1。这将创建一个盈余（用于数字和），该盈余应从最后一个数字中再次减去。当倒数第二个数字太大时（已经是9），需要将其设置为0，并应将较早的数字递增，等等。

在第三步中，最后一位需要用余量进行调整。这可能会导致溢出，请在步骤1中进行处理。

[请注意，由于Python没有类似C语言的do ... while或repeat ... until构造，因此这些循环需要用while True和break编写。

def find_nunbers(num_digits, desired_sum, max_iterations=100, max_in_digit=9):
    a = [0 for i in range(num_digits)]
    a[0] = desired_sum - 1
    a[num_digits - 1] = 1
    all_numbers_found = False
    while not all_numbers_found and max_iterations > 0:
        # step 1: while a[0] is too large: redistribute to the left
        i = 0
        while a[i] > max_in_digit:
            if i == num_digits - 1:
                all_numbers_found = True
                break
            a[i + 1] += a[i] - max_in_digit
            a[i] = max_in_digit
            i += 1
        if all_numbers_found:
            break

        num = sum(10 ** i * a[i] for i, n in enumerate(a))
        print(f"{num:}")  # print(f"{num:,}")

        # step 2:  add one to the penultimate group, while group already full: set to 0 and increment the
        #   group left of it;
        #   while the surplus is too large (because a[0] is too small) repeat the incrementing
        i0 = 1
        surplus = 0
        while True:  # needs to be executed at least once, and repeated if the surplus became too large
            i = i0
            while True:  # increment a[i] by 1, which can carry to the left
                if i == len(a):
                    all_numbers_found = True
                    break
                else:
                    if a[i] == max_in_digit:
                        a[i] = 0
                        surplus -= max_in_digit
                        i += 1
                    else:
                        a[i] += 1
                        surplus += 1
                        break
            if all_numbers_found:
                break
            if a[0] >= surplus:
                break
            else:
                surplus -= a[i0]
                a[i0] = 0
                i0 += 1

        # step 3: a[0] should absorb the surplus created in step 1, although a[0] can get out of bounds
        a[0] -= surplus
        surplus = 0
        max_iterations -= 1

find_nunbers(2, 5)
find_nunbers(10, 90)
find_nunbers(20, 90)