1

Дана последовательность '2 2 4 4'.

Мы берем очерёдно 2 числа, например: 2 2, 2 4, 4 4.

Если сумма 2 чисел представляет собой чётное число, мы заменяем оба числа cуммой этих 2 чисел делённой на 2, например: ((2 + 4)/2 = 3), поэтому новая последовательность (2 3 4), но здесь я должен найти все возможные варианты. Если невозможно найти четное число, то мы возвращаем саму последовательность.

Если условие не совподает возвращаем саму последовательность или конечное число. Функция должна быть рекурсивной без использования библиотек и глобальных переменных.

На данный момент есть сложность с тем что parentNodes переписываются в рекурсивном функции. То есть при итерации теряются предидущие очерёдности.

Например:

введите сюда описание изображения

Код:

def checkIfPossible(child):
    for num1, num2 in zip(child[:-1], child[1:]):
        if (num1 + num2) % 2 == 0:
            return False
    return True  

def recFunc(n):
    if len(n) == 1:
        return n
    else:
        for i in range(len(n)):
            if i+1 <= len(n)-1:
                if ((n[i] + n[i+1]) % 2 == 0):
                    n[i] = int((n[i] + n[i+1])/2)
                    n.pop(i+1)
                if checkIfPossible(n):
                    return n
                else:
                    return recFunc(n)
def main(s):
    s = s.split()
    integers = [int(x) for x in s]
    final = [x for x in recFunc(integers)]
    print(final)


main('2 2 4 4')

Не могу вычитать помеченое красным В конце я должен получить упорядоченый по длине и по первому числу Array без повторения результатов ['3', '2 3', '3 4', '2 3 4']

1
  • 1. У вас всегда передаётся ссылка на n, поэтому все изменения во всех рекурсивных функциях будут отражаться на изначальном списке. Чтобы скопировать список: a = list(n). 2. Если нашли два числа, сумма которых чётная, копируем список, оттуда уже совершаем pop, и для него вызываем recFunc, причём результат прибавляем к текущему res, который объявили пустым списком в начале функции recFunc
    – Philippe
    28 дек 2018 в 15:05

1 ответ 1

0

Я немного переписал ваш код, чтобы чётко выразить то, что хотел сказать в комментариях.

def checkIfPossible(child):
    for i in range(len(child) - 1):
        if (child[i] + child[i + 1])% 2 == 0:
            return True

    return False

def recFunc(n):
    if not checkIfPossible(n):
        return [n] #terminal node
    else:
        res = [] #res = [n], если нужны ВСЕ возможные конфигурации
        for i in range(len(n) - 1):  
            if (n[i] + n[i + 1]) % 2 == 0:
                a = list(n)
                a[i] = int((n[i] + n[i+1])/2)
                a.pop(i+1)

                res += recFunc(a)

    return res

def main(s):
    s = s.split()
    integers = [int(x) for x in s]
    final = recFunc(integers)
    final = [tuple(x) for x in final]
    final = list(set(final))
    final.sort(key=lambda x: x[0]) #Сюда можно свою сортировку, если угодно

    print(final)


main('2 2 4 4')

У вас была проблема в том, что функция recFunc на самом деле не рекурсивна. На каждом шаге передаётся ссылка на n, который меняется при каждом вызове функции. Поэтому происходит всего одна итерация по n. В моём же коде, n не меняется, а каждый раз, когда находится подходящая пара, создаётся копия и снова вызывается функция.

1
  • Большое спасибо, вы очень помогли мне понять основы рекурсии. С наступающим!
    – Kukuriku
    28 дек 2018 в 15:40

Ваш ответ

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

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