Доброго времени суток, читатели, зрители моего канала programmer's notes. Не забывайте подписываться и писать свои комментарии к моим статьям и видео.
А это подборки моих материалов на канале
Пример рекурсивной задачи генерации списков
Продолжаем пополнять подборку по алгоритмам. И опять рекурсивный алгоритм.
Задача на первый взгляд частная, но в действительности она легко обобщается на более широкий спектр задач.
В чём суть проблемы? Есть множество пар целых чисел. Вводятся они следующим образом. В начале идёт число - количество пар. А далее пары, по одной в строке. Например
2
1 2
3 4
Нужно получить все списки, состоящие из чисел. Каждое число из своей пары. Для данного примера получим
[1, 3]
[1, 4]
[2, 3]
[2, 4]
Последовательность этих списков нам не важна, главное, чтобы они все были.
Кстати, легко показать, что количество таких списков будет равно 2^n, где n это количество пар. И вот тут, тем кто интересуется задачами ЕГЭ может прийти в голову мысль, что я хочу разобрать как раз одну из задач ЕГЭ. В которой нужно найти одну из сумм таких последовательностей, удовлетворяющей определённому условию. Сразу скажу: нет. Во-первых, постановка другая. Но самое главное то, что при n = 20 мы уже получим 1048576 вариантов списков. Для задач из ЕГЭ этот подход не годится. Но с другой стороны данный подход абсолютно общий и получив все варианты, мы можем найти суммы последовательностей, удовлетворяющих любым заранее заданным условиям.
Моя задача лишь продолжить показ рекурсивных алгоритмов и их применение.
Функция recg() как раз та рекурсивная функция, выполняющая основную работу по получению всех вариантов списков. Например для
4
1 2
3 4
5 6
7 8
Получим
[[1, 3, 5, 7], [1, 3, 5, 8], [1, 3, 6, 7], [1, 3, 6, 8], [1, 4, 5, 7], [1, 4, 5, 8], [1, 4, 6, 7], [1, 4, 6, 8], [2, 3, 5, 7], [2, 3, 5, 8], [2, 3, 6, 7], [2, 3, 6, 8], [2, 4, 5, 7], [2, 4, 5, 8], [2, 4, 6, 7], [2, 4, 6, 8]]
Вот они всевозможные искомые списки. Естественно их 16 (2 в степени 4).
Несколько, пояснений к программе выше.
- В программе есть определённый компромисс между использованием глобальных переменных (lss, l1) и параметров рекурсивной функции. Можно в принципе обойтись вообще без параметров. Попробуйте.
- Условие if i == n это как раз то условие, которое говорит нам, что получен очередной список, длина которого естественно равна n.
- l1.pop() — выход из рекурсии на один шаг назад предполагает, что мы удаляем последний элемент, который был добавлен на данном шаге.
- Обратите внимание вот на это lss.append(l1[:]). Это добавление очередного полученного списка. Но написать lss.append(l1) было бы ошибкой. Мы бы добавили не сам список, а ссылку на него. А l1 ведь постоянно меняется.
Кстати, решение очень легко обобщается, когда в строках у нас не пары чисел, а скажем тройки, четверки, пятёрки и т.д.
Ну в общем так. Надеюсь, я увлек вас рекурсиями.
Хорошего программирования. Оставляйте свои комментарии, не забывайте про лайки и подписывайтесь на мой канал programmer's notes.
