什么限制会导致此脚本卡住？

Question

我在用python做一个数学拼图，你会发现数字的序列k个数字的长度，其中每个数字的乘积等于数字的和，即k=3 1*2*3=1+2+3

一般来说，我对python和编程都是新手，我很好奇为什么会有一个“落差”，它可以非常快地计算到某个点，然后程序就会卡住

psnumbers = []

#this gives me a number to start a for loop later in the script
def ones(n):
    string = '1'*n
    return int(string)

#multiplies and adds the digits together and compares the values
def check(n):
    global psnumbers
    add = 0
    mult = 1
    for i in range(len(n)):
        add += int(n[i])
        mult*= int(n[i])
    if add == mult and n[0] != 0:
        print(n)
        psnumbers.append(n)
        return True
    else:
        return False

#starts checking numbers, starting with the value from ones()      
def loop(n):
    for x in range(2,n+1):
        for i in range(ones(x),ones(x)*2):
            if check(str(i)) == True:
                break
            else:
                continue

#loop(23) works for me fine, but loop(n) where n>=24 doesn't finish processing      
loop(23)

循环（n）的所有值，其中n<；=23个工作完全按照我想他们太和脚本完成不到半秒钟。但是，对于大于等于24的n值，脚本生成的值将达到它将为循环（23）输出的值，并且在处理过程中卡住。什么问题会导致这种情况

Answer 1

你确定n=24有解吗？我认为你的代码是按预期工作，它只是需要很长时间才能得到正确的答案。 我改变了你的循环，所以我只寻找n=24的解，并打印出它正在尝试的数字。。。这将允许您在命令行上运行它，并打印出它正在尝试的数字，您可以看到为什么需要这么长时间

def loop(n):
    x = n
    for i in range(ones(x),ones(x)*2):
        print('\r' + str(i), end='')
        if check(str(i)) == True:
            break
        else:
                continue
    print('done')

这个数字要高得多

n=23 >> 11111111111111111111228

n=24 >> 111111111111111112163473在我达到jupy笔记本极限之前

我不确定你是否有时间让电脑来解决这个问题，比如说你一秒钟能查1000个数字，这需要你10^24 * 10^-4 = 10^20 seconds。。。或者1.15740741 × 1015 days。您可能需要做一些复杂的逻辑来避免两次检查相同的数字（对于您的算法，112==121）

你的问题“为什么要花更长的时间”的答案是，答案离n=24的起点比n=23要远得多

Answer 2

在为任何给定的字符串长度找到单个解决方案后，代码将退出。碰巧，对于n到23的任何值都有一个简单的解决方案

然而，当我们得到n=24时，所有前导的1的开销最终滑过了小数的各种数值性质，并且没有这样的解

我更改了算法findall中的指令插入，并在每个循环前后添加了一个简单的time()调用

def loop(n):
    for x in range(2,n+1):
        start = time()
        for i in range(ones(x),ones(x)*2):
            check(str(i))
        print(x, time() - start)

n的前几个值的计时如下

n     time (sec)
2 0.00010895729064941406
3 0.0007987022399902344
4 0.008989572525024414
5 0.08109426498413086
6 0.6398007869720459
7 6.47220778465271
8 70.14981818199158

如果您编写只处理非递减序列（数字按数字顺序排序）的代码，并进行检查以确保乘积在和的范围内，则可以大大加快速度