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 that you have read and understand our privacy policy and code of conduct.

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