В. Рубанцев - Как решать комбинаторные задачи на компьютере (1127108), страница 3
Текст из файла (страница 3)
5.15. Старый алгоритм в новом обличии25Примерный вид интерфейса приложенияИсходный код программы находится в папке Magic.Магические ферзиМагический квадрат седьмого порядка, составленный по методу де ла Лубера (Рис. 5.16), как показал американец Клиффорд Пиковер, непостижимым образом связан с другой знаменитой задачей – расстановкой ферзейна шахматном поле.Поскольку метод де ла Лубера позволяет строить только нечётные квадраты, а шахматная доска имеет чётный порядок, то придётся взять квад-26рат, наиболее близкий к шахматной доске, то есть 7 х 7 клеток.
Мы еголегко построим с помощью нашей программы.Рис. 5.16. Квадрат де ла ЛубераСледующий шаг: заменяем все числа в магическом квадрате остатками отих деления на семь. При этом нулевой остаток будем считать семёркой(Рис. 5.17).Рис. 5.17. Преобразование квадрата де ла ЛубераНовый квадрат в каждой строке и паре нисходящих диагоналей содержитрешение для задачи с ферзями. Например, из первой строки вытекает такое решение (Рис. 5.18).Одна из главных диагоналей квадрата нисходящая. Её можно использовать для решения задачи о ферзях, но мы рассмотрим другой пример - когда нисходящая диагональ является побочной (ломаной), поэтому должнабыть продолжена так, чтобы в ней оказалось ровно семь клеток (Рис.
5.19).27Рис. 5.18. Строки дают решение задачи с ферзямиРис. 5.19. Нисходящие диагонали дают решение задачи с ферзямиМагические квадраты четвёртого порядкаТеперь давайте составим магический квадрат четвёртого порядка. Одиниз таких квадратов изображён на гравюре Дюрера.Для удобства нарежьте из бумаги 16 квадратиков и напишите на них числаот 1 до 16. Это самая трудная и ответственная часть задания! Дальше будет легче, особенно если вам приходилось складывать картинки из пазлов.Разложите бумажки в каре так, чтобы числа следовали друг за другом поранжиру, то есть соблюдая субординацию (Рис.
5.20).28Рис. 5.20. Приняли исходное положениеШаг 1. Поменяйте местами вторую и третью строки (Рис. 5.21).Рис. 5.21. Первый шагШаг 2. Переложите числа во второй и четвёртой строках в обратном порядке (Рис. 5.22).Рис. 5.22. Второй шаг29Шаг 3. Переложите числа во втором и третьем столбцах в обратном порядке (Рис. 5.23).Рис. 5.23. Третий шагШаг 4.
Переложите числа в третьей и четвёртой строках в обратном порядке (Рис. 5.24).Рис. 5.24. Четвёртый шагМагический квадрат готов! И почти как у Дюрера, - только год стоит не впоследней, а в первой строке. Впрочем, вы можете перевернуть квадратвверх ногами, чтобы дата оказалась внизу. Осталось переставить первый ичетвёртый столбец – и наш квадрат превращается в «дюреровский» (Рис.5.25).30Рис. 5.25. Смастерили Дюреровский квадрат!Мы не знаем, как именно построил Дюрер свой магический квадрат, но,возможно, и «нашим» способом.Кстати говоря, в магическом квадрате, который мы построили, больше магических сумм, чем «требуется». Магическая сумма, которая в квадратахчетвертого порядка равна 34, повторяется не только в четырёх строках,четырёх столбцах и двух диагоналях, но и- в пяти квадратиках 2 х 2 клетки (Рис.
5.26).Рис. 5.26. Дополнительные магические квадратики 2 х 2- в углах четырёх квадратов 3 х 3 клетки (Рис. 5.27).31Рис. 5.27. Дополнительные магические квадраты 3 х 3- в углах двух прямоугольников 2 х 4 клетки (Рис. 5.28).Рис. 5.28. Дополнительные магические прямоугольники 2 х 4- в углах самого квадрата 4 х 4 клетки (Рис. 5.29).Рис. 5.29. Дополнительные магические прямоугольники 2 х 432Итого – 22 раза. Но, оказывается, и это не предел. До предела мы дойдём,если выполним ещё два шага.Шаг 5. Временно уберите третью и четвёртую строки.
Переложите вторую строку на место четвёртой, а затем верните третью и четвёртуюстроки на свободные места. То есть третья строка займет в квадрате местовторой, а четвёртая – третьей (Рис. 5.30).Рис. 5.30. Пятый шагШаг 6. Поменяйте местами третий и четвёртый столбец (Рис. 5.31).Рис. 5.31. Шестой шагЛегко заметить, что все числа, кроме первых двух, заняли в квадрате другие места, и теперь магическая сумма повторяется уже 30 раз. Конечно, в33этом квадрате сохранились все 22 магические суммы прежнего квадрата,но к ним добавились ещё 11:- в углах девяти (а не пяти) квадратов 2 х 2 клетки.- в углах шести (а не двух) прямоугольников 2 х 4 клетки.Найдите самостоятельно все магические суммы!Проект Чётно-чётные квадраты (DEMS)В уже упомянутой добрым словом книге С.Гудмана и С.Хидетниеми, настраницах 301-302 приведён алгоритм DEMS для составления любых чётно-чётных магических квадратов (то есть порядок квадрата должен бытькратен четырём).Работа алгоритма начинается с расстановки меток в левой верхней четверти квадрата.
В каждой строке и каждом столбце нужно поставить N/4меток. Сделать это можно произвольно, но алгоритм DEMS ставит метки вшахматном порядке сразу во всей верхней половине квадрата (Рис. 5.32). Вкачестве метки используется минус единица.Рис. 5.32. Метки расставленыМы видим, что метки из левого верхнего квадранта отражаются относительно вертикальной оси симметрии квадрата в правый верхний квадрант. Затем их нужно отразить относительно горизонтальной оси в нижнюю половину квадрата.
Впрочем, описываемый алгоритм обходится безэтой операции.34После того как метки расставлены, мы просматриваем все квадраты слеванаправо, сверху вниз. Если в очередной клетке метка отсутствует, мыставим первое ещё не вышедшее число i из ряда 1..N2. Отражаем клеткуотносительно центра квадрата и ставим в неё число N2 + 1 – i. Если же внём находится метка, то ставим число N2 + 1 – i - и число i в клеткуотражение. Следуя этому правилу, мы поставим в первую клетку число 16,а в последнюю – 1 (Рис. 5.33).Рис. 5.33. Первая пара чисел на своих местахВ следующей клетке квадрата метки нет, поэтому в неё мы должны поставить двойку – единица уже вышла.
Опять отражаем клетку относительноцентра квадрата и вписываем число 16+1-2 = 15 (Рис. 5.34).Рис. 5.34. И вторая пара чисел нашла своё местоВ следующие клетки пойдут числа 3 и 14, и так мы продолжаем сканировать квадрат, пока не заполним его целиком (Рис. 5.35).35Рис. 5.35. Квадрат готов к употреблениюВы, должно быть, обратили внимание, что способ построения магическогоквадрата таков, что сумма двух чисел, расположенных симметрично относительно центра квадрата, всегда равняется N2 + 1.
В нашем случае - семнадцати. Такие магические квадраты называются ассоциативными.Ну, а теперь за дело! Немного подновим интерфейс приложения Magic изапишем алгоритм DEMS на языке Си-шарп://Algorithm DEMSprivate void btnGen_Click(object sender, EventArgs e){//порядок квадрата:n = (int)udNum.Value;//создаем массив:matrix = new int[n*n+1];//генерируем магический квадрат:int halfn = n / 2;int mark = 1;int middle = n / 2;int upper = n * n + 1;int half = n * n / 2;//Ставим метки в первой половине массива:for (int k = 1; k <= halfn; ++k){for (int j = 1; j <= halfn; ++j){matrix[middle-j+1] = mark;matrix[middle+j] = mark;mark = -mark;}//Переходим к следующей строке:middle += n;36mark = -mark;}//расставляем числа:for (int i = 1; i <= half; ++i){//будущая координата числа i:int l=i;if (matrix[i] < 0)l= upper-i;matrix[l] = i;matrix[upper - l] = upper - i;//matrix[l] = upper-i;//matrix[upper-l] = i;}//построение квадрата закончено:writeMQ();lstRes.TopIndex = lstRes.Items.Count - 27;}Если вы хотите перевернуть квадрат, то раскомментируйте строчки//matrix[l] = upper-i;//matrix[upper-l] = i;и закомментируйте пару строк над ними.Здесь вместо двумерного массива mq используется одномерный массивmatrix, поэтому метод печати writeMQ готовых квадратов нам придётсяадаптировать к новым реалиям://Печатаем магический квадратvoid writeMQ(){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){int id = (i-1) * n + j;if (n*n > 10 && matrix[id] < 10) s += " ";if (n*n > 100 && matrix[id] < 100) s += " ";s= s + matrix[id] + " ";}lstRes.Items.Add(s);37}lstRes.Items.Add("");}//writeMQ()Запускаем новое приложение – оно работает, как кремлёвские часы (Рис.5.36).Рис.
5.36. Генерируем чётно-чётные магические квадратыКартинку с новым интерфейсом программы я приводить не буду. Вы еголегко получите из приложения Magic. Обратите только внимание на параметры компонента udLen!Исходный код программы находится в папке DEMS.38Проект 4 x 4 (_4x4)Шёл по улице отряд сорок мальчиков подряд:раз,два,три,четыреи четыреждычетыре,и четырена четыре,и еще потом четыре.Даниил Хармс, МиллионОдин магический квадрат может построить каждый. Потом его можно повертеть и получить ещё несколько экземпляров.
А давайте мы отыщем всемагические квадраты!Если вспомнить, что магических квадратов пятого порядка чрезмерномного для полного поиска, то нам придётся ограничить свой порыв квадратами четвёртого порядка, которых всего 880 (уникальных, общее же ихчисло 880 х 8 = 7040). Не очень много, но вот вариантов расстановки 16чисел в квадрате 4 х 4 имеется 16! = 20 922 789 888 000, что совсем немало.Но мы справимся. Итак, за дело!За основу мы возьмём наш предыдущий проект, хорошенько уменьшивширину списка lstRes, поскольку квадратики будут совсем маленькие. Полей нам понадобится всего 5 штук, что ясно говорит о том, что программабудет несложной (ну, не очень сложной).//=true, если число использовано:bool[] flg;//порядок квадрата:int n = 4;//магическая сумма:int magsum;//магический квадрат:int[,] mq;//число найденных магических квадратов:int nVar;В методе btnGen_Click мы просто создаём новые массивы для хранениямагического квадрата и флажков, которые будут отмечать использованныечисла:39//НАЖИМАЕМ КНОПКУ "ГЕНЕРИРОВАТЬ"private void btnGen_Click_1(object sender, EventArgs e){//создаем числовой массив:mq = new int[n, n];flg = new bool[n * n + 1];//находим магическую сумму:magsum = (n * n * n + n) / 2;//пока не нашли ни одного квадрата:nVar = 0;//составляем квадрат, начиная с первого числа:recGenerate(1);//все квадраты найдены:lstRes.Items.Add("");lstRes.Items.Add("Всего вариантов " + nVar);lstRes.Items.Add("");lstRes.TopIndex = lstRes.Items.Count-27;}Сам поиск магических квадратов мы перенесём в метод recGenerate.
Мыпоступим мудро, если напишем его рекурсивно. Тогда он получится оченькоротким, но «заковыристым»://Рекурсивный метод составления магических квадратовvoid recGenerate(int hod){int nw = 0;//перебираем все числа 1..n*n:for (int j = 1; j <= n * n; ++j){if (test(hod, j)){nw = j;//нашли подходящее число-->//ставим его в квадрат:int row = (hod - 1) / n;int col = (hod - 1) % n;mq[row, col] = j;flg[j] = true;if (hod < n * n) recGenerate(hod + 1);else writeVar();}//ifflg[nw] = false;}//for} //recGenerateСамая большая проблема здесь – придумать эффективную проверку длякаждого нового числа! В самом деле, если мы будем просто последова-40тельно расставлять 16 чисел по клеткам квадрата и только потом, проверять, получился ли у нас магический квадрат, то жизнь будет прожита даром.Но мы крепко сузим круг претендентов, если последнее число каждойстроки будем проверять так. Найдём сумму этого числа и ещё трёх, которые мы поставили раньше.
Мы знаем, что в магическом квадрате суммачисел во всех строках, столбцах и в двух главных диагоналях равна магической сумме, которую мы умеем вычислять. Таким образом, если суммачисел какой-либо строки вместе с числом-претендентом не равна магической сумме, то это число ставить в квадрат нет никакого смысла. Эта проверка обеспечит нам магическую сумму во всех строках.Но этого мало, поэтому, когда мы дойдём до последней строки, то будемпроверять также вертикали и диагонали.
Вот теперь любой составленныйнашей программой квадрат будет магическим://ПРОВЕРКА ЧИСЛА numbool test(int hod, int num){if (flg[num]) return false;int col = (hod - 1) % n;//номер строки:int row = (hod - 1) / n;int sum = 0;if (col == n - 1) //последнее число в строке{sum = 0;for (int i = 0; i < n - 1; ++i)sum += mq[row, i];if (sum + num != magsum) return false;//else return true;}if (row == n - 1){sum = 0;for (int j = 0; j < n - 1; ++j)sum += mq[j, col];if (sum + num != magsum) return false;}//диагонали:if (row == n - 1 && col == 0) //восходящая{sum = 0;for (int j = 1; j < n; ++j)41sum += mq[n - 1 - j, j];if (sum + num != magsum) return false;}if (row == n - 1 && col == n - 1) //нисходящая{sum = 0;for (int j = 0; j < n - 1; ++j)sum += mq[j, j];if (sum + num != magsum) return false;}return true;}Довольно быстро мы получим полный список из 7040 магических квадратов четвёртого порядка (Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
