时间戳

首页 > 解决方案 > 无休止的程序执行

python - 无休止的程序执行

问题描述

任务：需要输出一个单词链，使下一个单词从前一个单词的最后一个字母开始。

输入示例："aac", "cas", "baa", "eeb"

示例输出："eeb", "baa", "aac", "cas"

当使用大量单词（~ 980）时，程序进入无限循环。我认为问题就在这里，但我无法解决：

for j in range(0,N-U):
    if (s[j][0] == words[i][-1]):
       searchNextWord(s,j,U)

代码：

def searchNextWord(words,i,U):
        global Result
        s = [None]*N
        if (Result==True):
            return
        res[U] = words[i]
        U += 1
        if (U == N):
            Result = res[U - 1] == words[i]
        if (Result==True):
            return

        for j in range(0,N-U):
            if (j<i):
                s[j]=words[j]
            else:
                s[j]=words[j+1]

        for j in range(0,N-U):
            if (s[j][0] == words[i][-1]):
                searchNextWord(s,j,U)


    words=[]
    N=int(input())
    if (N<1 or N>1000):
        exit()
    for i in range(N):
        new_element = str(input())
        words.append(new_element)

    res = [None]*N
    for i in words:
        if (len(i)>10):
            exit()

    Result = False
    for i in range(0,N):
        if (Result==False):
            searchNextWord(words, i, 0)

    if (Result==True):
        for i in range(0,N):
            print(res[i])
    else:
        print("NO")

标签： pythonalgorithm

解决方案

太多的 for 循环，你的程序不会无休止，但执行起来需要大量的时间！

使用链表来做到这一点。每个单词会占用更多内存，但它会使搜索更容易。由于您正在重新排序输入，因此您需要考虑实现一个浏览器类，将这些对缓存到二叉树的变体中（其中每个节点都包含所包含元素的开始和结束。这将减少您需要执行的传递搜索。

推荐阅读