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

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

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

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

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

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

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

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

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 которого показана на следующем рисунке:

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

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

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

                                  !
 

#	2	3	#	#	6	7	#
9	#	#	12	13	#	#	16
17	#	#	20	21	#	#	24
#	26	27	#	#	30	31	#
#	34	35	#	#	38	39	#
41	#	#	44	45	#	#	48
49	#	#	52	53	#	#	56
#	58	59	#	#	62	63	#

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

64	$	$	61	60	$	$	57
$	55	54	$	$	51	50	$
$	47	46	$	$	43	42	$
40	$	$	37	36	$	$	33
32	$	$	29	28	$	$	25
$	23	22	$	$	19	18	$
$	15	14	$	$	11	10	$
8	$	$	5	4	$	$	1

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

64	02	03	61	60	06	07	57
09	55	54	12	13	51	50	16
17	47	46	20	21	43	42	24
40	26	27	37	36	30	31	33
32	34	35	29	28	38	39	25
41	23	22	44	45	19	18	48
49	15	14	52	53	11	10	56
8	58	59	5	4	62	63	1

Константа этого магического квадрата равна 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:

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

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

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

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

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

Magic mag(4);

mag.Magic::~Magic( );

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

1. Определить зависимость величины центрального элемента магического квадрата нечетного порядка и константы квадрата.

2. Разработать специальный компонентный метод в классе Magic, который формирует магический квадрат ло-шу, используя следующий алгоритм. Заполнить изначально пустой квадрат размером 5x5 целыми числами от 1 до 9, располагая их последовательно в строках и столбцах с нечетными номерами. Затем следует поменять местами цифры на противоположных концах главных диагоналей и придвинуть их на 1 позицию в направлении к центру квадрата. После этих преобразований 3 группы элементов матрицы 5x5 с одинаковыми суммарными индексами строк и столбцов, равными 4, 6 и 8, соответственно, образуют строки искомого магического квадрата ло-шу.

3. Средние числа в нижней строке магического квадрата А. Дюрера отображают год - 1514, когда им была создана гравюра "Меланхолия", содержащая этот магический квадрат 4-го порядка из 1-х 16-ти натуральных чисел. Применяя перестановку строк и столбцов квадрата А. Дюрера, требуется найти другие магические квадраты, где тот же год фигурирует таким же образом. Для решения этой проблемы рекомендуется расширить класс Magic компонентными методами перестановки строк и столбцов квадратов.

4. Разработать класс Multimag для формирования магических квадратов, у которых произведения элементов в каждой строке, столбце и главной диагонали равны. Для заполнения ячеек квадрата следует использовать члены геометрических прогрессий, у которых начальный элемент и знаменатель прогрессии равны (например, последовательности степеней 2, 3 и других натуральных чисел).

5. Расширить класс Magic компонентным методом mageven6( ) для формирования магического квадрата 6-го порядка на основе следующего алгоритма. Формируемый магический квадрат разбивается на 4 подквадрата 3-го порядка, которые заполняются соответствующим алгоритмом составления магического квадрата нечетного порядка. Подквадраты заполняются в такой последовательности: левый верхний, правый нижний, правый верхний, левый нижний. После заполнения подквадратов необходимо поменять местами элементы левых полудиагоналей у 2-х левых квадратов 3-го порядка.

6. Модифицировать конструктор класса Magic, введя для инициализации целочисленных компонент-данных список инициализаций вместо их инициализации внутри тела конструктора.

7. Модифицировать класс Magic, дополнив его конструктором копирования-инициализации, спецификация которого имеет вид:

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

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

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

2. М. Гарднер

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

3. О. Оре

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

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

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

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

    От Си к Си++, - М., ‘’Эдель’’, 1993г.

6. Д. Кнут

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

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