@SilentGr0ve
Первокурсник

Как с помощью рекурсии создать максимально возможную последовательность?

Всем привет! Получил задание в вузе с таким условием:
Существует такая игра, в которой химические элементы выстраиваются в длинную цепочку таким образом, чтобы каждое очередное слово на- чиналось на букву, на которую заканчивается предыдущее. Например, если последовательность начинается с элемента Hydrogen, то следующий элемент должен начинаться на N, и это может быть Nickel. Следом может идти Lithium. При этом элементы в ряду не должны повторяться. При игре в одиночку целью является составление списка элементов максимально возможной длины. Если в игре принимают участие двое, то целью стано- вится назвать такой химический элемент, чтобы оппонент не смог про-
должить последовательность.
Напишите программу, которая будет запрашивать у пользователя
химический элемент и при помощи рекурсивной функции определять максимально возможную последовательность слов. Выведите на экран полученный ряд. Удостоверьтесь, что программа выводит соответствующее сообщение об ошибке, если пользователь укажет несуществующий химический элемент.

Написал код, но нужный результат не выводится. Не понимаю в чём причина и как это можно исправить. Подскажите, пожалуйста! Фунцкию swap_elements добавил просто для личного удобства. Особо она никак не влияет на код, кроме проверки на существование элемента в списке.

elements_list = [
    "Hydrogen", "Helium", "Lithium", "Beryllium", "Boron", "Carbon", "Nitrogen", "Oxygen", "Fluorine",
    "Neon", "Sodium", "Magnesium", "Aluminum", "Silicon", "Phosphorus", "Sulfur", "Chlorine", "Argon",
    "Potassium", "Calcium", "Scandium", "Titanium", "Vanadium", "Chromium", "Manganese", "Iron", "Cobalt",
    "Nickel", "Copper", "Zinc", "Gallium", "Germanium", "Arsenic", "Selenium", "Bromine", "Krypton",
    "Rubidium", "Strontium", "Yttrium", "Zirconium", "Niobium", "Molybdenum", "Technetium", "Ruthenium",
    "Rhodium", "Palladium", "Silver", "Cadmium", "Indium", "Tin", "Antimony", "Tellurium", "Iodine",
    "Xenon", "Cesium", "Barium", "Lanthanum", "Cerium", "Praseodymium", "Neodymium", "Promethium", "Samarium",
    "Europium", "Gadolinium", "Terbium", "Dysprosium", "Holmium", "Erbium", "Thulium", "Ytterbium", "Lutetium",
    "Hafnium", "Tantalum", "Tungsten", "Rhenium", "Osmium", "Iridium", "Platinum", "Gold", "Mercury", "Thallium",
    "Lead", "Bismuth", "Polonium", "Astatine", "Radon", "Francium", "Radium", "Actinium", "Thorium", "Protactinium",
    "Uranium", "Neptunium", "Plutonium", "Americium", "Curium", "Berkelium", "Californium", "Einsteinium", "Fermium",
    "Mendelevium", "Nobelium", "Lawrencium", "Rutherfordium", "Dubnium", "Seaborgium", "Bohrium", "Hassium",
    "Meitnerium", "Darmstadtium", "Roentgenium", "Copernicium", "Nihonium", "Flerovium", "Moscovium", "Livermorium",
    "Tennessine", "Oganesson"
]


def swap_elements(elements_list,user_input):

    if user_input in elements_list:
        index = elements_list.index(user_input)
        new_list = list(elements_list)  # Создаем копию списка
        new_list[0], new_list[index] = new_list[index], new_list[0]
        return new_list  # Возвращаем новый список
    else:
        print("Ошибка ввода")
        return None

user_input = input("Введите название элемента: ").capitalize()
new_elements_list = swap_elements(elements_list,user_input) # Изменённый список

def find_max_sequence(start_element,elements,sequence):
    if sequence == None:
        sequence = []
    next_letter = start_element[-1]
    max_sequence = []

    for element in elements:
        if element not in sequence and element.startswith(next_letter):
            new_sequence = sequence + [element]
            new_max_sequence = find_max_sequence(element,elements,new_sequence)
            if len(new_max_sequence) > len(max_sequence):
                max_sequence = new_max_sequence
    return max_sequence

print(find_max_sequence(user_input,elements_list,sequence = None))
  • Вопрос задан
  • 212 просмотров
Пригласить эксперта
Ответы на вопрос 1
LaRN
@LaRN
Senior Developer
Чтобы ускорить перебор можно вместо elements_list использовать dict, где key - это первая буква элемента, а value - это список элементов которые начинаются на букву из key.

Если преобразовать потом sequence в set и найденный список элементов тоже в set, то можно из set полного списка вычесть set текущей последовательности и то что осталось перебирать.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы