В. Рубанцев - Как решать комбинаторные задачи на компьютере (1127108), страница 2
Текст из файла (страница 2)
Магические квадратыДавным-давно это было… Китайская легенда гласит, что в 23 веке донашей эры (впрочем, дотошные историки утверждают, что это событиепроизошло не раньше четвёртого века до нашей эры) из реки Ло выползлачерепаха, на панцире которой люди обнаружили странные знаки (Рис. 5.1).Они пересчитали точки, и оказалось, что их число равно пятнадцати повсем горизонтальным и вертикальным рядам, а также по двум главнымдиагоналям «квадрата». Древние китайцы были так поражены этими необыкновенными свойствами «черепаховой» фигуры, что назвали её магическим квадратом Ло-шу.Рис.
5.1. Магический квадрат Ло-шу на панцире черепахиКитайцы придавали квадрату Ло-шу мистические свойства и считали егосимволом, объединяющим предметы, людей и вселенную. Чётные числа внём представляют женскую сущность Инь, а нечётные – мужскую – Ян (Рис.5.2).Рис. 5.2. Знаменитый символ Инь-ЯнВ центре Ло-шу находится пятёрка, которая символизирует Землю (Рис.5.3).
Вокруг неё располагаются элементы (стихии). Металл, представленный числами 4 и 9, вода – 1 и 6, огонь – 2 и 7, дерево 3 и 8. Легко заметить,что каждый элемент содержит мужское и женское начала Инь и Ян.12Рис. 5.3. Элементы природы в квадрате Ло-шуИз Китая магические квадраты попали в Индию, а затем - через арабскиестраны – в Европу. В эпоху Ренессанса немецкий математик Генрих Корнелиус Агриппа (1486-1536) построил магические квадраты от третьего додевятого порядка и дал им астрономическое толкование.Эти квадраты представляли собой семь известных тогдашней науке «планет»: Сатурн, Юпитер, Марс, Солнце, Венеру, Меркурий и Луну.Но создание первого «европейского» магического квадрата приписываютнемецкому художнику, уроженцу города Нюрнберга, современнику Леонардо да Винчи Альбрехту Дюреру.
На знаменитой гравюре Меланхолия(Рис. 5.4) в правом верхнем углу он поместил магический квадрат четвёртого порядка. Причём Дюрер составил его так ловко, что два средних числав нижней строке образовали год создания произведения - 1514 (Рис. 5.5).После Ло-шу это самый известный магический квадрат в мире!Конечно, Дюрер украсил свою гравюру магическим квадратом не толькодля того, чтобы указать год. Дело в том, что в то время квадраты четвёртого порядка считались хорошим терапевтическим средством, и астрологи«прописывали» их для амулетов против меланхолии.Необычным свойствам магических квадратов люди с давних времен находили применение в мистике и религии. Вырезанные на дереве, камне илиметалле магические квадраты служили амулетами (в этом качестве они досих пор используются в восточных странах). Ещё в 16-17 веках люди вери-13ли, что выгравированный на серебряной пластине магический квадратможет защитить их от чумы.Арабские астрологи более девяти веков назад употребляли магическиеквадраты при составлении гороскопов.Рис.
5.4. Дюрер. «Меланхолия»Рис. 5.5. Магический квадрат крупным планомМатематические подробностиМагический квадрат – это таблица, которая состоит из равного числастрок и столбцов. Во всех её клетках записано по одному числу. Если обозначить буквой N число строк (или столбцов) в таблице - это число называется порядком магического квадрата, - то в обычном магическом квадрате записаны последовательные числа от 1 до N2. Например, в самом простом магическом квадрате порядка 3 (то есть размером 3 х 3 клетки) мыотыщем все числа от 1 до 32 = 9 (Рис. 5.6).
Если вы не забыли, это и естьзнаменитый квадрат Ло-шу.14Магические квадраты иначе называют волшебными.Таким образом, мы всегда знаем, какие числа следует записать в таблицу.Сделать это в произвольном порядке, конечно нетрудно, но ведь квадратне зря называется магическим! В нём сумма чисел в каждой строке, столбце и в каждой из двух главных диагоналей должна быть одинаковой. Этасумма называется магической и обозначается буквой S.Магическая сумма называется также константой магического квадрата.Рис.
5.6. Магический квадрат третьего порядкаМы легко найдём магическую сумму любого квадрата, если сложим всечисла в квадрате и разделим сумму на порядок квадрата. Последовательные натуральные числа, которые находятся в магическом квадрате, образуют арифметическую прогрессию, сумму членов которой мы умеем находить:Первый член прогрессии равен 1.Последний член прогрессии равен N2.Число членов прогрессии равно N2.Сумму всех членов прогрессии можно вычислить по формуле:15А магическую сумму – по формуле:А сколько всего магических квадратов?Мало ли в Бразилии Педров? И не сосчитаешь!Фраза тётушки Чарлииз комедии Здравствуйте, я ваша тётяМагические квадраты первого и третьего порядков существуют в единственном числе, а квадратов второго порядка вообще нет.Мы считаем только уникальные квадраты, которые нельзя получить издругих с помощью поворотов и отражений.Имеется 8 способов размещения чисел 1..9 в квадрате 3 х 3 клетки. Но если не считать различными квадраты, совпадающие при поворотах и отражениях, то останется единственный квадрат Ло-шу.Подробное доказательство этих утверждений вы найдёте, например, вкниге Мартина Гарднера [ГМ90], в главе 17 Магические квадраты и кубы.Французский математик Бернар де Бесси (Bernard Frénicle de Bessy, 1605 –1675) насчитал 880 магических квадратов четвёртого порядка.Долгое время ученые оценивали число магических квадратов пятого порядка в 13 миллионов, пока в 1973 году американский программистРичард Шрёппель (Richard Schroeppel) с помощью компьютера не нашёл ихточное число - 275 305 224.16Существует несколько различных классификаций магических квадратовпятого порядка, призванных хоть как-то их систематизировать.
В книгеМартина Гарднера [ГМ90, сс. 244-345] описан один из таких способов –по числу в центральном квадрате. Способ любопытный, но не более того.Сколько существует квадратов шестого порядка, до сих пор неизвестно, ноих примерно 1.77 х 1019. Число огромное, поэтому нет никаких надежд пересчитать их с помощью полного перебора, а вот формулы для подсчётамагических квадратов никто придумать не смог.Как составить магический квадрат?Придумано очень много способов построения магических квадратов.
Проще всего составлять магические квадраты нечётного порядка. Мы воспользуемся методом, который предложил французский учёный XVII векаА. де ла Лубер (De La Loubère). Он основан на пяти правилах, действие которых мы рассмотрим на самом простом магическом квадрате 3 х 3 клетки.Правило 1. Поставьте 1 в среднюю колонку первой строки (Рис. 5.7).Рис. 5.7. Первое числоПравило 2.
Следующее число поставьте, если возможно в клетку, соседнююс текущей по диагонали правее и выше (Рис. 5.8).17Рис. 5.8. Пытаемся поставить второе числоПравило 3. Если новая клетка выходит за пределы квадрата сверху, то запишите число в самую нижнюю строку и в следующую колонку (Рис. 5.9).Рис. 5.9. Ставим второе числоПравило 4. Если клетка выходит за пределы квадрата справа, то запишитечисло в самую первую колонку и в предыдущую строку (Рис.
5.10).Рис. 5.10. Ставим третье число18Правило 5. Если в клетке уже занята, то очередное число запишите под текущей клеткой (Рис. 5.11).Рис. 5.11. Ставим четвёртое числоДалее переходите к Правилу 2 (Рис. 5.12).Рис. 5.12. Ставим пятое и шестое числоСнова выполняйте Правила 3, 4, 5, пока не составите весь квадрат (Рис.5.13).Не правда ли, правила очень простые и понятные, но всё равно довольноутомительно расставлять даже 9 чисел. Однако, зная алгоритм построениямагических квадратов, мы сможем легко перепоручить компьютеру всюрутинную работу, оставив себе только творческую, то есть написание программы.19Рис. 5.13.
Заполняем квадрат следующими числамиПроект Магические квадраты (Magic)Набор полей для программы Магические квадраты совершенно очевиден:// ПРОГРАММА ДЛЯ ГЕНЕРИРОВАНИЯ// НЕЧЕТНЫХ МАГИЧЕСКИХ КВАДРАТОВ// ПО МЕТОДУ ДЕ ЛА ЛУБЕРАpublic partial class Form1 : Form{//макс. размеры квадрата:const int MAX_SIZE = 27;//varint n=0;// порядок квадратаint [,] mq; // магический квадратint number=0;// текущее число для записи в квадрат20int col=0;int row=0;// текущая колонка// текущая строкаМетод де ла Лубера годится для составления нечётных квадратов любогоразмера, поэтому мы можем предоставить пользователю возможность самостоятельно выбирать порядок квадрата, разумно ограничив при этомсвободу выбора 27-ью клетками.После того как пользователь нажмёт заветную кнопку btnGen Генерировать!, метод btnGen_Click создаёт массив для хранения чисел и переходитв метод generate://НАЖИМАЕМ КНОПКУ "ГЕНЕРИРОВАТЬ"private void btnGen_Click(object sender, EventArgs e){//порядок квадрата:n = (int)udNum.Value;//создаем массив:mq = new int[n+1, n+1];//генерируем магический квадрат:generate();lstRes.TopIndex = lstRes.Items.Count-27;}Здесь мы начинаем действовать по правилам де ла Лубера и записываемпервое число – единицу – в среднюю клетку первой строки квадрата (илимассива, если угодно)://Генерируем магический квадратvoid generate(){//первое число:number=1;rule1://колонка для первого числа - средняя:col = n / 2 + 1;//строка для первого числа - первая:row=1;//заносим его в квадрат:mq[row,col]= number;Теперь мы последовательно пристраиваем по клеткам остальные числа –от двойки до n * n://переходим к следующему числу:21nextNumber:number++;Запоминаем на всякий случай координаты актуальной клеткиint tc=col;int tr = row;и переходим в следующую клетку по диагонали:col++;row--;Проверяем выполнение третьего правила:rule3:if (row < 1) row= n;А затем четвёртого:rule4:if (col > n) {col=1;goto rule3;}И пятого:rule5:if (mq[row,col] != 0) {col=tc;row=tr+1;goto rule3;}Как мы узнаем, что в клетке квадрата уже находится число? – Очень просто: мы предусмотрительно записали во все клетки нули, а числа в готовомквадрате больше нуля.
Значит, по значению элемента массива мы сразу жеопределим, пустая клетка или уже с числом! Обратите внимание, что здесьнам понадобятся те координаты клетки, которые мы запомнили перед поиском клетки для следующего числа.Рано или поздно мы найдём подходящую клетку для числа и запишем егов соответствующую ячейку массива:22//заносим его в квадрат:mq[row, col] = number;Попробуйте иначе организовать проверку допустимости перехода в новую клетку!Если это число было последним, то программа свои обязанности выполнила, иначе она добровольно переходит к обеспечению клеткой следующегочисла://если выставлены не все числа, тоif (number < n*n)//переходим к следующему числу:goto nextNumber;И вот квадрат готов! Вычисляем его магическую сумму и распечатываемна экране://построение квадрата закончено:writeMQ();} //generate()Напечатать элементы массива очень просто, но важно учесть выравнивание чисел разной «длины», ведь в квадрате могут быть одно-, дву- и трёхзначные числа://Печатаем магический квадратvoid writeMQ(){lstRes.ForeColor = Color.Black;string s = "Магическая сумма = " + (n*n*n +n)/2;lstRes.Items.Add(s);lstRes.Items.Add("");// печатаем магический квадрат:for (int i= 1; i<= n; ++i){s="";for (int j= 1; j <= n; ++j){if (n*n > 10 && mq[i,j] < 10) s += " ";if (n*n > 100 && mq[i,j] < 100) s += " ";s= s + mq[i,j] + " ";}lstRes.Items.Add(s);}lstRes.Items.Add("");}//writeMQ()23Запускаем программу – квадраты получаются быстро и на загляденье (Рис.5.14).Рис.
5.14. Изрядный квадратище!В книге С.Гудман, С.Хидетниеми Введение в разработку и анализ алгоритмов, на страницах 297-299 мы отыщем тот же самый алгоритм, но в «сокращённом» изложении. Он не столь «прозрачен», как наша версия, но работает верно.Добавим кнопку btnGen2 Генерировать 2! и запишем алгоритм на языкеСи-шарп в метод btnGen2_Click://Algorithm ODDMSprivate void btnGen2_Click(object sender, EventArgs e){//порядок квадрата:n = (int)udNum.Value;//создаем массив:mq = new int[n + 1, n + 1];//генерируем магический квадрат:int row = 1;24int col = (n+1)/2;for (int i = 1; i <= n * n; ++i){mq[row, col] = i;if (i % n == 0){++row;}else{if (row == 1)row = n;else--row;if (col == n)col = 1;else++col;}}//построение квадрата закончено:writeMQ();lstRes.TopIndex = lstRes.Items.Count - 27;}Кликаем кнопку и убеждаемся, что генерируются «наши» квадраты (Рис.5.15).Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
