Вы программист, и вам дан массив целых чисел, и ваша задача состоит в том, чтобы напечатать все возможные подпоследовательности, но все подпоследовательности должны быть в порядке, то есть слева -> справа.
Что, черт возьми, я имею в виду под каждой возможной подпоследовательностью?
Допустим, массив содержит 3 элемента, например {5,2,1}. И если вы погуглите слово подпоследовательность, вы получите что-то вроде этого
последовательность, которая может быть получена из данной последовательности путем удаления некоторых элементов или их отсутствия без изменения порядка оставшихся элементов.
да, я также скопировал и вставил его, в любом случае продолжая тему, поэтому для массива {5,2,1} возможная подпоследовательность будет
{5,2,1}
{5,2}
{5,1}
{5}
{2,1}
{2}
{1}
{}
где каждая последовательность идет по порядку слева направо. {1,5} не может быть подпоследовательностью, потому что она не в порядке.
И чтобы подтвердить, что те 8 подпоследовательностей, которые мы написали выше, являются всеми возможными последовательностями, существует формула для проверки количества подпоследовательностей, которые могут быть сформированы на любой последовательности, и это 2^n где n — количество элементов в массиве или в элементах этой последовательности.
Теперь нам не надо разбираться, как работает эта формула, мы программисты, а не математики.
И для последовательности из 3 мы получаем 8, применяя эту формулу, которая, кстати, не что иное, как (2 * 2 * 2).
Теперь как написать программу, которая может вывести все возможные подпоследовательности для n элементов?
Не знаю, как вам, но когда я слышу слово «каждая подпоследовательность», мне на ум приходит только один алгоритм — рекурсия.
Теперь позвольте мне устроить вам сердечный приступ, показав код напрямую.
Вывод кода ниже
Давайте сначала разберемся с кодом, но не с его потоком пока.
мы создали массив и предварительно инициализировали его с помощью {5,2,1}, после чего я создал пустой связанный список, который будет использоваться для хранения всех возможных последовательностей, и после этого мы вызываем функцию printEverySubSequence и передаем ее следующие аргументы
0 — — — — -›, который является первым индексом массива
arr — — — —› сам массив
size — — — -› размер этого массива, который в данном случае будет равен 3
tempList — -› пустой связанный список, который мы создали.
Теперь функция printEverySubSequence, где происходит настоящее волшебство.
Ключевым моментом в функции printEverySubSequence является то, что мы начинаем с первого элемента и формируем все возможные последовательности, которые могут быть сформированы этим первым индексом, а затем переходим к следующему индексу и снова повторяем цикл.
И чтобы получить все возможные подпоследовательности для этого первого элемента, мы должны сделать два выбора: либо выбрать этот элемент, либо оставить/игнорировать его.
Например, если у меня есть массив {5,2,1}, и если я возьму первый элемент 5, у меня есть два варианта: я могу взять 5 или оставить его. И так как мы должны формировать каждую подпоследовательность, почему бы не сделать оба выбора по отдельности. И после того, как мы сделали оба выбора, мы продвигаемся вперед в массиве, увеличивая значение индекса на 1 и применяя то же самое к двум вновь сгенерированным вариантам/последовательностям, которые были созданы путем выбора этих двух вариантов и повторения цикла снова.
Вот дерево рекурсии, чтобы понять его визуально.
В этом дереве рекурсии каждый уровень представляет индекс массива, уровень 1 — это индекс 0, уровень 2 — это индекс 1, а последний уровень представляет индекс 2. А листовые узлы или наборы, выделенные желтым цветом, — это возможные последовательности, которые мы можем есть для массива {5,2,1}.
И в printEverySubSequence мы делаем эти два выбора, сначала добавляя текущий элемент индекса в tempList(это наш первый выбор), а затем снова вызывая функцию printEverySubSequence с этим tempList и увеличенным индексом. И как только он возвращается из этой подрекурсии, мы удаляем элемент из tempList, который является нашим вторым выбором, и снова вызываем функцию printEverySubSequence с tempList и снова индексируем с шагом 1.
И для базового случая при каждом вызове рекурсии мы проверяем, больше ли индекс или равен размеру, и если это так, мы печатаем текущий tempList и возвращаемся.
Временная сложность будет O(2^n)
Сложность пространства будет O(n).
Если вы узнали что-то новое из этой статьи, нажмите кнопку «Подписаться»
если (!уже)🚗
