Рассмотренный метод составления нечетных магических квадратов не является единственным. Не менее известным и не более сложным является следующий алгоритм, предложенный С. Лубером. Правила алгоритма Лубера удобно иллюстрировать на примере магического квадрата порядка 7 из натуральных чисел от 1 до 49, матрица 7x7 которого показана на следующем рисунке:

В основе алгоритма Лубера лежит заполнение ячеек квадрата в направлении вверх и влево по диагонали последовательными числами выбранной арифметической прогрессии. Заполнение начинается со среднего элемента верхней строки (01). Если следующая левая диагональная ячейка уже занята числом (ячейка 01 уже занята в момент заполнения ячейки 07), нужно перейти к нижнему соседу (08) текущей заполненной ячейки (07) и продолжить движение по диагонали. Чтобы избежать возможности выхода за границы квадрата при диагональном движении его надо мысленно превратить в тор, соединив верхнюю горизонталь с нижней, а затем соединить основания полученного цилиндра. После свертки строки, столбцы и диагонали квадрата превращаются в замкнутые кривые на поверхности тора и выход за границы квадрата становится невозможным. Превращение квадрата в тор в данном случае обеспечивает возможность диагонального перехода, например, из ячейки 01 в ячейку 02 или из ячейки 45 в ячейку 46.

2.2 Составление магических квадратов четного порядка

Универсальные методы составления магических квадратов произвольного четного порядка пока неизвестны. Однако, разработаны индивидуальные подходы для различных частных случаев. Ниже рассмотрен метод составления магических квадратов, порядок которых является экспонентой 2. Этот метод удобно рассмотреть на примере магического квадрата 8-го порядка из натуральных чисел от 1 до 64. Метод включает следующую последовательность шагов. [9]

1. Исходный квадрат делится на соответствующее число квадратов порядка 4. В данном случае таких квадратов будет 4. В каждом подквадрате отмечаются диагональные элементы (например, символом #). Остальные элементы построчно заполняются порядковыми целыми числами в направлении слева-направо и сверху-вниз. Числа, приходящиеся на выделенные диагональные элементы должны быть пропущены. Результат заполнения недиагональных элементов квадрата 8-го порядка показан на следующем рисунке:

2. Отмеченные на шаге 1 диагональные элементы квадрата заполняют пропущенными целыми числами в порядке возрастания в направлении справа-налево и снизу-вверх. Недиагональные элементы в каждом подквадрате должны быть отмечены (например, символом $), а числа, приходящиеся на них должны быть пропущены. Результат заполнения диагональных элементов для квадрата 8-го порядка показан на следующем рисунке:

3. Квадраты с пропусками диагональных и недиагональных элементов, полученные на шагах 1 и 2, объединяются в общий квадрат, где целочисленные элементы подавляют метки # или $. Результат объединения для квадрата 8-го порядка показан на следующем рисунке:

Константа этого магического квадрата равна 260, что подтверждается вычислением контрольных сумм элементов по строкам, столбцам и главным диагоналям.

2.3 Выводы

Существование общего алгоритма построения магических квадратов невозможно. Однако существуют частные алгоритмы, которые с увеличением порядка дают стремящееся к бесконечности число магических квадратов. Это частные методы составления магических квадратов, порядок которых является экспонентой 2 и квадратов нечетного порядка.

Глава 3. Программная реализация магических квадратов

Программная реализация основных магических квадратов основывается на уже известных словесных алгоритмах математиков и философов. Обычно это квадратная матрица, четная или нечетная. Также существует индивидуальный алгоритм заполнения каждого квадрата- или бесчисленного множества квадратов одного вида, но разных порядков. Рассмотрим некоторые из них.

3.1 Программная реализация квадратов нечетного порядка

Магические квадраты нечетного порядка можно построить с помощью метода французского геометра 17 в. А.де ла Лубера. Рассмотрим этот метод на примере квадрата 5-го порядка (рис. 3.1). Число 1 помещается в центральную клетку верхней строки. Все натуральные числа располагаются в естественном порядке циклически снизу вверх в клетках диагоналей справа налево. Дойдя до верхнего края квадрата (как в случае числа 1), продолжаем заполнять диагональ, начинающуюся от нижней клетки следующего столбца. Дойдя до правого края квадрата (число 3), продолжаем заполнять диагональ, идущую от левой клетки строкой выше. Дойдя до заполненной клетки (число 5) или угла (число 15), траектория спускается на одну клетку вниз, после чего процесс заполнения продолжается.[10]

Рис. 3.1

Ниже рассмотрим листинг программы, которая реализует данный квадрат на языке Паскаль.

progam algMR;

uses crt;

const n=5;

type mr:array[1..n,1..n]of integer;

var a:mr; b,i,j:integer;

begin

clrscr;

for i:=1 to n do

for j:=1 to n do

Страницы: 1, 2, 3, 4