В 2010 году после поступления в бакалавриат для меня было большим удивлением то, как быстро стартовали все учебные дисциплины, бодро и без особых прелюдий. Но если у предметов, которые преподавали местные профессора ритм изложения был довольно размеренный, то у приезжающих из Москвы преподавателей, как правило, такого не случалось — сроки сильно поджимали и необходимо было за короткое время изложить весь запланированный материал. Одним из первых в самом начале осеннего семестра 2010 года к нам приехал Владимир Михайлович Староверов, который прочитал нам краткий курс по алгоритмам на языке Си.
Поскольку я с языком Си знаком к тому моменту не был и вообще опыт программирования у меня был почти нулевой (привет языку Паскаль), этот курс для меня оказался своеобразной шоковой терапией. Многие из однокурсников уже неплохо разбирались и в Си и в базовых алгоритмах, приходилось в экстренном порядке срочно усваивать вообще все чтобы не отставать — было весьма стрессово и безумно увлекательно! Помню, к примеру, как засиживался ночью и разбирался в загадочном алгоритме слияния с рекурсией.
На изучение синтаксиса Си было отведено несколько часов, после чего мы стали галопом осваивать сортировки, основные структуры данных, учились проводить оценку сложности алгоритмов. К сожалению, не успели дойти до более продвинутых вещей (таких как красно-черные деревья), но, тем не менее, польза от курса для меня была неоценима. В особенности потому, что курс был наполовину практический и надо было решать алгоритмические задачи почти в режиме реального времени. Об одной из задач, которые мне попались в далеком 2010 недавно вспомнил и захотелось о ней рассказать, тем более что она не очень сложно формулируется, а содержательно довольно интересная. Для пущей интриги дадим этой задачке кодовое имя «карусель».
Итак, на одном из первых практических занятий выпало такое задание:
Необходимо написать процедуру циклического сдвига массива длины n вправо на k позиций (0<=k<n). Алгоритм должен работать за линейное время от длины массива (т.е. за O(n)) и не использовать дополнительной памяти (т.е. дополнительная память должна быть О(1)).
Мне, как всякому порядочному студенту, сначала показалось что я вообще все понял и я тут же предложил преподавателю целых две процедуры циклического сдвига массива, которые тут же были забракованы. Ниже я приведу примерный код своих первых предложенных решений.
Нетрудно догадаться, что я просто не обратил внимания на требования про скорость и память, и поэтому мои первые «наивные» решения ценз не прошли. Первый вариант работает за время O(k*n), а не за O(n), хотя по памяти требует всего O(1), однако k может быть сопоставимо с n. Второй вариант требует O(k) дополнительной памяти, хотя работает за O(n). Дело ко всему прочему усложнялось тем, что надо было писать на абсолютно незнакомом мне тогда языке и каждый вариант программы создавался с огромным скрипом (теперь к Си отношусь с большим теплом и признателен за этот период «ломки»).
В конце концов я обратился к преподавателю за подсказкой, и ответ мне запомнился: «У этой задачи есть решение красивое, а есть умное. Вы какое хотите?». Я выбрал красивое и не прогадал. Про умное расскажу тоже, но в самом конце. Итак, к красоте...
Мне было предложено изобразить индексы массива на плоскости в виде кольца и поведан замечательный геометрический факт, что всякий поворот на плоскости (а именно его я и пытался построить) есть комбинация двух отражений. Это в самом деле так, и доказательство этого факта можно найти, например, здесь. Я на тот момент так глубоко копать не стал, доверился умному человеку, и попытался «покрутить руками», рисуя какие-то несложные примеры. Попробуем повернуть массив из семи элементов на 4 позиции вправо и проиллюстрируем это на плоскости:
Очевидно, что отражение массива можно делать за линейное время и дополнительной памяти не потребуется, а нам нужно всего лишь найти правильные «оси» для двух отражений. В далеком 2010 году мне пришлось написать довольно громоздкий код, который учитывал всякие разные случаи четности числа элементов в массиве и был не особо лаконичен, тем не менее В.М. быстро пробежался глазами и сказал «сойдет». Здесь я приведу код на питоне, который, к тому же, вдохновлен коротким постом с медиума с доказательством корректности. Доказательство в вышеупомянутом посте вообще не применяет геометрии, а основано лишь на модульной арифметике.
Взглянув на код становится понятная идея: для поворота на k шагов вправо нам достаточно отразить сначала весь массив по «центральной» оси, потом отразить первые k элементов массива относительно их «центральной» оси, а потом аналогичным образом отразить последние «n-k» элементов массива. Доказательство корректности очень несложное, советую попробовать сначала провести его самостоятельно, а если не получится — обращайтесь к заметке.
Этот алгоритм был назван «красивым», что же тогда «умный» алгоритм? К сожалению, я не узнал этого у преподавателя тогда, во время обучения, но сейчас мне кажется что подразумевается алгоритм прохода по циклам в массиве. Дело в том, что циклический сдвиг, по сути, задает перестановку элементов. Чтобы обойти эту перестановку достаточно пройтись по её циклам, которых может быть несколько, если k не взаимно просто с n, где n — длина исходного массива. Ничего особо «умного» в этом алгоритме нет, думаю что назван так для красного словца. Ниже приведен примерный код такого подхода.
Для меня эта задача на первом курсе была весьма сложна и я получил огромное удовольствие, когда наконец её «добил». Размышляя над тем, для чего может понадобится такой алгоритм циклического сдвига (быстрый и без дополнительной памяти), в голову пока не пришло ничего лучше, чем приложения для компьютерной графики (быстрый скроллинг матрицы изображения, представленной набором векторов). Напишите в комментарии если знаете интересную область применения.
На этом у меня все, спасибо что дочитали до конца! Подписывайтесь на канал и ставьте лайки, если понравился материал.
Желаю Вам круговорота интересных и радостных событий в жизни!