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

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: