Алгоритмы неформально. Инструкция для начинающих питонистов - [14]

Шрифт
Интервал

3. Повторите шаг 2, пока не будут заполнены все элементы магического квадрата.


Заполнение центральных квадратов

Процесс создания магического квадрата можно начать с создания пустой квадратной матрицы, которая будет заполняться алгоритмом. Например, если вы хотите создать матрицу 7 × 7, то можно определить n=7 и создать матрицу с n строками и n столбцами:

n = 7

square = [[float('nan') for i in range(0,n)] for j in range(0,n)]

Пока мы не знаем, какие числа должны находиться в квадрате, поэтому он будет заполнен значениями float('nan'). Здесь nan означает «не число» (Not A Number); это заполнитель, который может использоваться в Python для заполнения списков, когда числа не известны заранее. Если затем выполнить команду print(square), то будет видно, что матрица в исходном состоянии заполнена значениями nan:

[[nan, nan, nan, nan, nan, nan, nan], [nan, nan, nan, nan, nan, nan, nan],

[nan, nan, nan, nan, nan, nan, nan], [nan, nan, nan, nan, nan, nan, nan],

[nan, nan, nan, nan, nan, nan, nan], [nan, nan, nan, nan, nan, nan, nan],

[nan, nan, nan, nan, nan, nan, nan]]

В консольном выводе Python квадрат выглядит не слишком красиво, поэтому мы можем написать функцию, которая выводит его в намного более удобочитаемом виде:

def printsquare(square):

    labels = ['['+str(x)+']' for x in range(0,len(square))]

    format_row = «{:>6}» * (len(labels) + 1)

    print(format_row.format(«», *labels))

    for label, row in zip(labels, square):

        print(format_row.format(label, *row))

На функцию printsquare() пока можно не обращать внимания, поскольку она предназначена только для красивого вывода и не является частью нашего алгоритма. Пять центральных квадратов заполняются простыми командами. Сначала получим координаты центральной ячейки:

import math

center_i = math.floor(n/2)

center_j = math.floor(n/2)

Пять центральных квадратов заполняются в соответствии с выражениями из приведенной выше табл. 2.10:

square[center_i][center_j] = int((n**2 +1)/2)

square[center_i + 1][center_j] = 1

square[center_i - 1][center_j] = n**2

square[center_i][center_j + 1] = n**2 + 1 - n

square[center_i][center_j - 1] = n


Три правила

Основное содержание алгоритма Курусимы — заполнение остальных квадратов nan по простым правилам. Три простых правила позволяют заполнить любой другой квадрат независимо от размера магического квадрата. Правило 1 объясняется на рис. 2.1.

Рис. 2.1. Правило 1 алгоритма Курусимы

Чтобы для любого x в магическом квадрате определить значение, находящееся по диагонали от x, достаточно прибавить к x значение n и вычислить остаток от деления результата на n2. Конечно, можно пойти и в противоположном направлении: вычесть n и вычислить остаток от деления результата на n2.

Правило 2 еще проще, оно представлено на рис. 2.2.

Рис. 2.2. Правило 2 алгоритма Курусимы

Для любого x в магическом квадрате элемент ниже и правее x равен остатку от деления x + 1 на n2. Это простое правило, но у него есть одно важное исключение: оно не действует при переходе из левой верхней половины магического квадрата в правую нижнюю. Можно также сказать, что второе правило не выполняется при пересечении антидиагонали магического квадрата — линии, соединяющей левый нижний угол с правым верхним (рис. 2.3).

Здесь видны ячейки, находящиеся на антидиагонали. Линия полностью проходит через них. Имея дело с этими ячейками, можно следовать двум обычным правилам. Правило 3 необходимо только тогда, когда вы начинаете с ячейки, находящейся полностью над антидиагональю, и пересекаете ее, переходя в ячейку, находящуюся полностью под ней (или наоборот). Последнее правило представлено на рис. 2.4, на котором изображены антидиагональ и две ячейки, которые связываются правилом при ее пересечении.

Рис. 2.3. Антидиагональ матрицы квадрата

Рис. 2.4. Правило 3 алгоритма Курусимы

Это правило выполняется при пересечении антидиагонали. Если антидиагональ пересекается в направлении от правого нижнего угла к левому верхнему, то выполняется обратное правило — x преобразуется в x + n – 1 (mod n2).

Чтобы написать простую реализацию первого правила на Python, достаточно определить функцию, которая получает x и n в аргументах и возвращает (x+n)%n**2:

def rule1(x,n):

    return((x + n)%n**2)

Функцию можно опробовать на центральной ячейке квадрата Ло Шу. Квадрат представляет собой матрицу 3 × 3, так что n = 3. Центральная ячейка квадрата Ло Шу содержит значение 5. Ячейка ниже и левее ее содержит значение 8, и если функция rule1() была реализована правильно, то при выполнении следующей строки будет получено значение 8:

print(rule1(5,3))

На консоли Python должна появиться строка 8. Похоже, функция rule1() работает так, как задумано. Тем не менее ее можно улучшить, чтобы она могла работать и в обратном направлении, определяя значение не только внизу слева от заданной ячейки, но и значение справа наверху (то есть чтобы можно было перейти не только от 5 к 8, но и от 8 к 5). Чтобы внести это улучшение, можно добавить в функцию еще один аргумент upright; это индикатор True/False, который указывает, вычисляется ли значение справа и наверху от x. Если он не задан, то по умолчанию вычисляется значение слева внизу от x:


Рекомендуем почитать
Изучаем Java EE 7

Java Enterprise Edition (Java EE) остается одной из ведущих технологий и платформ на основе Java. Данная книга представляет собой логичное пошаговое руководство, в котором подробно описаны многие спецификации и эталонные реализации Java EE 7. Работа с ними продемонстрирована на практических примерах. В этом фундаментальном издании также используется новейшая версия инструмента GlassFish, предназначенного для развертывания и администрирования примеров кода. Книга написана ведущим специалистом по обработке запросов на спецификацию Java EE, членом наблюдательного совета организации Java Community Process (JCP)


Геймдизайн. Рецепты успеха лучших компьютерных игр от Super Mario и Doom до Assassin’s Creed и дальше

Что такое ГЕЙМДИЗАЙН? Это не код, графика или звук. Это не создание персонажей или раскрашивание игрового поля. Геймдизайн – это симулятор мечты, набор правил, благодаря которым игра оживает. Как создать игру, которую полюбят, от которой не смогут оторваться? Знаменитый геймдизайнер Тайнан Сильвестр на примере кейсов из самых популярных игр рассказывает как объединить эмоции и впечатления, игровую механику и мотивацию игроков. Познакомитесь с принципами дизайна, которыми пользуются ведущие студии мира! Создайте игровую механику, вызывающую эмоции и обеспечивающую разнообразие.


Обработка событий в С++

В книге рассказывается история главного героя, который сталкивается с различными проблемами и препятствиями на протяжении всего своего путешествия. По пути он встречает множество второстепенных персонажей, которые играют важные роли в истории. Благодаря опыту главного героя книга исследует такие темы, как любовь, потеря, надежда и стойкость. По мере того, как главный герой преодолевает свои трудности, он усваивает ценные уроки жизни и растет как личность.


MFC и OpenGL

В книге рассказывается история главного героя, который сталкивается с различными проблемами и препятствиями на протяжении всего своего путешествия. По пути он встречает множество второстепенных персонажей, которые играют важные роли в истории. Благодаря опыту главного героя книга исследует такие темы, как любовь, потеря, надежда и стойкость. По мере того, как главный герой преодолевает свои трудности, он усваивает ценные уроки жизни и растет как личность.


Симуляция частичной специализации

В книге рассказывается история главного героя, который сталкивается с различными проблемами и препятствиями на протяжении всего своего путешествия. По пути он встречает множество второстепенных персонажей, которые играют важные роли в истории. Благодаря опыту главного героя книга исследует такие темы, как любовь, потеря, надежда и стойкость. По мере того, как главный герой преодолевает свои трудности, он усваивает ценные уроки жизни и растет как личность.


Питон — модули, пакеты, классы, экземпляры

Python - объектно-ориентированный язык сверхвысокого уровня. Python, в отличии от Java, не требует исключительно объектной ориентированности, но классы в Python так просто изучить и так удобно использовать, что даже новые и неискушенные пользователи быстро переходят на ОО-подход.