Как использовать исходный список, если я отправил его в рекурсивную функцию, которая изменяет его? - PullRequest
Новая
       10

Как использовать исходный список, если я отправил его в рекурсивную функцию, которая изменяет его?

0 голосов
/ 02 февраля 2020

У меня есть рекурсивная функция, которая проверяет, существует ли путь от первого до последнего объекта списка.

шаг - это значение объекта, и он может идти в обоих направлениях:

Я начинаю с последнего объекта и проверяю, какое число, если я шагну от него, на несколько шагов в соответствии с его значением - переходит к последнему. Функция должна возвращать True, если мне удалось связать последнее с первым таким образом.

В своей функции я попытался изменить список после того, как нашел число, которое может прийти к последнему, так, чтобы номер, который я нашел, будет последним. Затем я изменил числа, чтобы расстояния были сохранены.

Но, скажем, к нему подходит число, как я смогу проверить это число позже? Я уже изменил список ..

Предположим, у меня есть этот список: [6, 4, 8, 2, 4, 2, 3, 6] функция вернет True. Путь будет 6,3,2,2,6

Но функция получает только список. Допустим, я начинаю с конца и обнаруживаю, что 2 прибывает в конец списка. Как мне продолжить ? Как я могу проверить, какой объект идет в 2? (на этот раз - 2) и так далее? 

    def walking_on_list(lst):
for i in range(len(lst)):
    if i + lst[i] == len(lst) - 1:
        if i == 0:
            return True
        else:
            diff = len(lst) - 1 - i
            lst[-1] = lst[i]
            lst[i] = 0
            for j in range(len(lst[:found])):
                lst[j] += diff
            temp = lst[found + 1:-1]
            temp = temp[::-1]
            for k in range(len(lst[found + 1:-1])):
                lst[k + len(lst[:found]) + 1] = temp[k]

            valid_path(lst)
    elif i == len(lst) - 1:
        return False

print (alking_on_list ([6, 4, 8, 2, 4, 2, 3, 6])

1 Ответ

2 голосов
/ 02 февраля 2020

Используйте алгоритм, который не меняет список. 

def walking_on_list(lst, indices=(0,)):
    index = indices[-1] + lst[indices[-1]]
    if index == len(lst) - 1:
        return True
    if (index < len(lst) and index not in indices
        and walking_on_list(lst, indices + (index,))):
        return True
    index = indices[-1] - lst[indices[-1]]
    if (index > 0 and index not in indices
        and walking_on_list(lst, indices + (index,))):
        return True
    return False

print(walking_on_list([6, 4, 8, 2, 4, 2, 3, 6]))
...