Цель занятия:
Целью занятия является практическое изучение способов объектно-ориентированной обработки 2-мерных массивов в системе программирования С++ для составления магических квадратов, которые являются популярным примером кросс-сумм теории чисел.

Формулировка задания:
Требуется разработать программу magic для составления магических квадратов четного и нечетного порядка в произвольном диапазоне натуральных чисел. Исходными данными программы magic считаются порядок и арифметическая прогрессия элементов магического квадрата. Исходные данные передаются программе через аргументы командной строки ее вызова. В результате работы программы magic должна быть построена матрица элементов и вычислена константа магического квадрата. Результат работы программы должен отображаться через поток стандартного вывода.

Понятие магического квадрата

Под магическим квадратом порядка N понимается квадратная матрица размером NxN из N в квадрате последовательных элементов произвольной арифметической прогрессии натуральных чисел, которые размещены так, что суммы элементов любого столбца, строки или главной диагонали одинаковы. Результат вычисления любой из перечисленных сумм принято называть константой магического квадрата. Порядок магического квадрата определяется числом элементов любого столбца или строки. Например, магический квадрат 3-го порядка из 9-ти 1-х натуральных чисел (известный в Китае как талисман ло-шу) представляется следующей матрицей 3x3:


Константа квадрата ло-шу равна 15. Это единственный квадрат 3-го порядка, который можно построить из натуральных чисел от 1 до 9, если не использовать преобразования поворота и отражения. Классический образец магического квадрата 4-го порядка, известный еще в Древней Индии, представляется следующей матрицей 4x4:


Константа "индийского" квадрата равна 34. В несколько измененном виде (достигаемом перестановкой строк и столбцов):


он известен художникам по философской гравюре А. Дюрера "Меланхолия". Астрологи средних веков приписывали числовым сочетаниям магических квадратов таинственные и волшебные свойства. Современных математиков и программистов интересуют формальные методы составления магических квадратов.

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

Наибольший практический интерес представляют универсальные методы, которые не зависят от порядка магического квадрата. Такие методов известны для магических квадратов нечетного порядка. Наиболее наглядный из них удобно рассмотреть на примере составления магического квадрата 5-го порядка из натуральных чисел от 1 до 25. Алгоритм этого метода включает следующие шаги.

1. Сначала исходный пустой квадрат достраивается до симметричной ступенчатой ромбовидной фигуры как показано на следующем рисунке, где ячейки для элементов квадрата обозначены символом #, а достроенные ячейки - символом $.


Рис. 1.  

2. Полученная на шаге 1 фигура заполняется по косым рядам сверху-вниз-направо целыми числами от 1 до 25 в натуральном порядке. Результат заполнения показан на следующем рисунке:
Рис. 2.  

3. Каждое число, расположенное в фигуре шага 2 вне исходного квадрата, переносится по вертикали или горизонтали внутрь исходного квадрата на число позиций, равное порядку квадрата. В рассматриваемом примере перенос осуществляется на 5 позиций. Таблица переносов имеет следующий вид:
1 - вниз под 13; 2 - вниз под 14; 6 - вниз под 18;
21 - вправо за 13; 22 - вправо за 14; 16 - вправо за 8;
5 - влево перед 13; 4 - влево перед 12; 10 - влево перед 18;
25 - вверх над 13; 24 - вверх над12; 20 - вверх над 8.


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

4. После преобразований переноса на шаге 3 освободившиеся ячейки (заполненные символом $) должны быть исключены. Оставшиеся (внутренние) ячейки (заполненные натуральными числами) образуют магический квадрат, представленный следующей матрицей 5x5:






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

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

Рис. 3.  

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

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

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

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

Рис. 4.  

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

Рис. 5.  

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

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

Программирование магических квадратов

Для программирования магических квадратов удобно использовать парадигму инкапсуляции объектно-ориентированного программирования, сосредоточив "магические" структуры данных и методы их обработки в отдельном классе Magic. В класс Magic рекомендуется включить следующие приватные (privat) компоненты - данные:

unsigned degree - порядок квадрата;

unsigned basic, differ - начальный элемент и разность арифметической прогрессии натуральных чисел, заполняющих магический квадрат;

unsigned **tab - указатель на двумерный массив беззнаковых целых чисел, который должен содержать матрицу магического квадрата.

Для обработки приватных данных в классе Magic целесообразно предусмотреть следующие общедоступные (public) компонентные методы:

void magodd( ) - формирует магический квадрат нечетного порядка;

void mageven2( ) - составляет магический квадрат четного порядка, у которого порядок является экспонентой 2;

int chksum( ) - вычисляет контрольные суммы элементов столбцов, строк и главных диагоналей квадрата, возвращая величину константы квадрата или 0, если квадрат не является магическим;

void print( ) - отображает матрицу и константу магического квадрата в потоке стандартного вывода;

void magbuild( ) - вызывает метод составления, соответствующий порядку магического квадрата.

Для инициализации компонент-данных в классе Magic следует предусмотреть конструктор. Конструктор класса Magic должен иметь возможность принимать 3 аргумента, определяющих порядок, начальный элемент и разность арифметической прогрессии элементов магического квадрата. При декларации конструктора рекомендуется указать значения аргументов по умолчанию:

class Magic { 

...................... 

public: 

Magic(unsigned=3, unsigned=1, unsigned=1); 

..................... 

}; 

Это позволит для создания объектов класса Magic использовать вызов конструктора в сокращенном формате; с одним , двумя или без аргументов. Например, следующий вызов конструктора:

Magic loshoo;

является корректным для составления магического квадрата ло-шу, где приватные компоненты-данные degree, basic, differ по умолчанию инициализируются величинами 3, 1, 1, соответственно. Кроме инициализации целочисленных компонент-данных конструктору класса Magic желательно поручить динамическое распределение памяти, необходимое для хранения 2-мерного массива элементов магического квадрата tab. Для динамического распределения памяти под 2-мерный массив рекомендуется использовать следующую 2-х этапную схему:

1.Распределить память под 1-мерный массив указателей на беззнаковые целые размером degree по адресу tab используя оператор new:

tab=new unsigned *(degree);


2. Под каждый указатель полученного массива указателей распределить одномерный массив беззнаковых целых из degree элементов, используя оператор new в цикле:

for (int i=0; i<degree;i++) 

tab[i]=new unsigned(degree);

Рассмотренный способ формирования 2-мерного массива позволит обращаться к любому j-му элементу i-й строки в компонентных методах класса Magic традиционным образом tab[i][j]. Вызов компонентных методов составления магического квадрата может быть реализован в теле конструктора класса Magic, а обращение к компонентному методу отображения результатов целесообразно организовать в основной функции программы magic.

После завершения требуемой обработки и отображения результатов объекты класса Magic должны быть уничтожены с помощью деструктора ~Magic( ). Деструктор класса Magic должен освободить память, динамически распределенную конструктором по адресу tab для хранения 2-мерного массива элементов магического квадрата. Рекомендуется освобождать память по схеме обратной ее распределению, используя оператор delete:

1. Освободить память, распределенную под degree одномерных массивов беззнаковых целых (из degree элементов каждый) по адресам от tab[0] до tab[degree-1]:

for (int i=0; i<degree; i++) 

delete [degree](tab[i]);

2. Освободить память, распределенную под 1-мерный массив указателей на беззнаковые целые, состоящий из degree указателей по адресу tab:

delete [degree]tab;

Обычно деструктор вызывается неявно при завершении работы с объектом класса, например, после выхода из блока, где объект был определен. При необходимости явного вызова деструктора в обращении к нему должно быть специфицировано имя класса, которому он принадлежит:

Magic mag(4); 

mag.Magic::~Magic( );

В соответствии с принципами структурного программирования следует разместить декларацию класса Magic в отдельном заголовочном h-файле. Исходный код компонентных методов класса Magic и основной функции main( ) программы magic, которая оперирует ими, рекомендуется разместить в 2-х отдельных файлах. Для успеха трансляции в каждый из них нужно включить заголовочный файл класса Magic, используя директиву include.

Контрольные задания

    Magic(Magic&);

Аргументом этого конструктора является ссылка на объект класса Magic, точной копией которого должен быть создаваемый объект.
Список литературы

1. Б. А. Кордемский

Математическая смекалка, - М., ТТЛ, 1957г.

2. М. Гарднер

Математические головоломки и развлечения, - М., Мир, 1971г.

3. О. Оре

Приглашение в теорию чисел, - М., Наука, 1980г.

4. Д. Е. Намиот

Язык программирования TURBO C++, - М., МГУ, 1991г.

5. Д. Рассохин

От Си к Си++, - М., &lsquo;&rsquo;Эдель&rsquo;&rsquo;, 1993г.

6. Д. Кнут

Искусство программирования для ЭВМ

т.1 Основные алгоритмы - М., Мир, 1976г.