1

Необходимо решить задачу по "игре в города", т.е входные данные это слова на латинице, например, "aab", "aac", "baas", соответственно ответ будет "aab","baas","aac". На небольшом количестве слов отрабатывает нормально, но при инпуте ~900 слов зацикливается бесконечно в части:

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")
3
  • Если на небольшом количестве данных работает правильно, то ошибки в алгоритме нет. А что зацикливается, так это кажется. Подождите час-два, может быть, день, рекурсия отработает и будет результат. 26 окт 2019 в 20:45
  • игра в города, как я помню - вспомнить город начинающийся на букву, которой закончился предыдущий город. Вы хотите построить такую цепочку из слов? Из вопроса это не понятно 26 окт 2019 в 21:20
  • Да, всё верно. Даны слова и из них нужно построить цепочку по принцицу игры в города. Если алгоритм работает на небольших значениях это не значит что он корректен. Видимо возникает ситуация в которой он уходит в бесконечный цикл. Потому что он сортирует условно 900/1000 слов за долю секунды и потом начинает крутить бесконечно.
    – LeFroys
    27 окт 2019 в 8:39

1 ответ 1

1

Для ускорения Вашего алгоритма модно рассмотреть два пути:

  • как альтернативу рекурсии можно попробовать использовать итеративный подход со стеком:

     stack = [(start_state)]
     while stack:
         current_state = stack.pop()
         # process this state
         # if conditions of the final result are true for the state 
         # then add result of the state into final data structure
         for child_state in current_state: # processed state
             stack.append(child_state)
    
  • в качестве словаря для городов можно воспользоваться префиксным деревом, в котором ответ для следующего города будет находиться как раз в корне этого дерева:

     # root = prefix tree with cities
     # last_city = results[-1]
     if last_city[-1] in root:
         # random choice of the next node until we reach the trie leaf
         # then mark this leaf as `used`
    

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.