Задачи для программирования можно как найти в каком-нибудь учебнике, так и придумать самому. Иногда придуманная задача может вытекать из уже существующей.
Решая очередную задачу на проекте Эйлера наткнулся на вопрос, связанный со спиральной матрицей. Для того, чтобы прийти к ответу строить её оказалось необязательно, поэтому результат нашёл и пошёл решать следующую. Но недавно написал друг с одним коротким вопросом "как сгенерировать матрицу по спирали?" И я задумался, а почему бы не придумать алгоритм, вроде интересная задача.
Перед собой я не ставил задачу написать универсальный способ генерации спиральной матрицы в любом указанном направлении. Мой вариант это:
- квадратная матрица
- с нечетным количеством строк и столбцов, соответственно
- с началом в центре
- с первым шагом вправо
- и последующим движением по часовой стрелке
Если короче, то так, как на верхнем рисунке.=)
Как придумывается алгоритм
В голове возникло два варианта для алгоритма. Первый - найти закономерность в поведении каждой строки: с первой и последней это легко, а с остальными сложнее. Второй - найти закономерность в индексах, идущих по спирали. Именно историю с индексами я решил проверить сначала.
Для нахождения алгоритмов использую старый метод: тетрадка + ручка. Записал индексы матрицы i и j, начиная с центра матрицы. Взял для теста матрицу 5 на 5. Центром будет элемент с индексом [3, 3], но для Python - это [2, 2] (не забываем про индексацию с 0). Дальше написал табличку изменения индексов на каждом из шагов. Все эти вычисления ниже:
Уже после понимания того, что закономерность вполне очевидная, начал писать программу. Хотя как я буду переводить всё в код, доходил только при написании.
Для начала написал функцию вывода на экран матрицы. Ведь в программе это, возможно, придется делать не один раз. Далее обозначил размерность матрицы в переменной n, создал саму матрицу и заполнил её нулями. Это для того, чтобы потом спокойно менять значения матрицы по её индексам.
Дальше мне пришлось отвлечься, и пока я занимался другими делами, немного сформировал перевод алгоритма в код в голове. Дальше уже напрограммировал его с некоторыми изменениями в итоговый вариант. Вот он на картинке:
Для тех, кому интересен сам алгоритм, постарался расписать в комментариях к коду. Здесь дублировать не вижу смысла.
Решение этой задачи, скорее всего является изобретением велосипеда. Но для тренировки и развития это было интересно. =)