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

Алгоритм Евклида компактен, элегантен и полезен. Предлагаю вам подумать над тем, как создать еще более компактную реализацию этого алгоритма на Python.

Японские магические квадраты

История японской математики особенно увлекательна. В книге «История японской математики», опубликованной в 1914 году, историки Дэвид Юджин Смит (David Eugene Smith) и Ёсио Миками (Yoshio Mikami) написали, что японская математика исторически обладала «гениальной способностью прикладывать титанические усилия» и «изобретательностью в распутывании тысяч мелких узелков». С одной стороны, математики открывают абсолютные истины, которые не должны зависеть от времени и культуры. С другой — те или иные группы обычно склонны концентрироваться на задачах определенного типа и создают свои специфические подходы к ним, не говоря уже о различиях в системах записи и обмена информацией. И этот факт позволяет оценить примечательные культурные различия даже в такой аскетичной области, как математика.

Создание квадрата Ло Шу на Python

Японские математики обожали геометрию, и во многих древних рукописях формулируются и решаются задачи, связанные с нахождением площади разных экзотических фигур — например, эллипсов с вписанными кругами или японских ручных вееров. Другим постоянным направлением исследований для японских математиков на протяжении веков было изучение магических квадратов.

Магический квадрат представляет собой массив, содержащий уникальные последовательные натуральные числа, суммы всех строк, столбцов и двух главных диагоналей которого одинаковы. Магические квадраты могут иметь любой размер. В табл. 2.9 приведен пример магического квадрата 3 × 3.

Таблица 2.9. Квадрат Ло Шу

4

9

2

3

5

7

8

1

6

В этом квадрате суммы всех строк, столбцов и двух главных диагоналей равны 15. Пример выбран не случайно: это знаменитый квадрат Ло Шу. Согласно древнекитайской легенде, этот магический квадрат впервые был начертан на панцире волшебной черепахи, вышедшей из реки в ответ на молитвы и жертвоприношения страдающего народа.

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

Легенда о внезапном появлении этого простого, но очаровательного квадрата как дара богов хорошо подходит для изучения алгоритмов. Алгоритмы часто легко проверять и использовать, но их бывает трудно проектировать «с нуля». Особенно элегантные алгоритмы, если нам вдруг повезет изобрести их, кажутся божественным откровением, словно они появились из ниоткуда на панцире волшебной черепахи. Если вы сомневаетесь в этом, то попробуйте построить магический квадрат 11 × 11 «с нуля» или изобрести алгоритм общего назначения для генерирования волшебных квадратов.

Информация об этом и других магических квадратах перешла из Китая в Японию как минимум в 1673 году, когда математик по имени Санэнобу опубликовал в Японии магический квадрат 20 × 20. На языке Python квадрат Ло Шу создается с помощью следующей программы:

luoshu = [[4,9,2],[3,5,7],[8,1,6]]

Будет полезно иметь функцию, которая проверяет, является ли заданный квадрат магическим. Для этого следующая функция вычисляет суммы по всем строкам, столбцам и диагоналям, а затем проверяет, что все они одинаковы:

def verifysquare(square):

    sums = []

    rowsums = [sum(square[i]) for i in range(0,len(square))]

    sums.append(rowsums)

    colsums = [sum([row[i] for row in square]) for i in range(0,len(square))]

    sums.append(colsums)

    maindiag = sum([square[i][i] for i in range(0,len(square))])

    sums.append([maindiag])

    antidiag = sum([square[i][len(square) - 1 - i] for i in \

    range(0,len(square))])

    sums.append([antidiag])

    flattened = [j for i in sums for j in i]

    return(len(list(set(flattened))) == 1)

Реализация алгоритма Курусимы на Python

Выше мы обсуждали, как выполнять интересующие нас алгоритмы «вручную», до того как предоставить подробности реализации. В случае алгоритма Курусимы мы кратко обрисуем основные шаги и одновременно рассмотрим код. Эти изменения объясняются относительной простотой алгоритма и особенно длиной кода, необходимого для его реализации.

Один из самых элегантных алгоритмов генерирования магических квадратов, алгоритм Курусимы, назван в честь математика по имени Курусима Ёсита, жившего в период Эдо. Алгоритм Курусимы работает только для магических квадратов нечетного размера, то есть для любого квадрата n × n, где n — нечетное число. Он начинается с заполнения центра квадрата по такой же схеме, как в квадрате Ло Шу. В частности, пять центральных квадратов определяются следующими выражениями, где n — размер квадрата (табл. 2.10).

Таблица 2.10. Центр квадрата Курусимы

n2

n

(n2 + 1) / 2

n2 + 1 – n

1

Алгоритм Курусимы для генерирования магического квадрата n×n, где n — нечетное число, описывается с помощью простой схемы, представленной ниже.

1. Заполните пять центральных квадратов по табл. 2.10.

2. Начиная с любого элемента, значение которого уже известно, определите значение неизвестного соседнего элемента по одному из трех правил (см. далее).