В. Рубанцев - Как решать комбинаторные задачи на компьютере (1127108), страница 4
Текст из файла (страница 4)
5.38).Рис. 5.38. Все четырежды четырки найдены!Совершенно немыслимо составлять таким способом квадраты 5 х 5 клеток. Как говорил анекдотический Рабинович: «Не дождётесь!»42Интерфейсом программы займитесь самостоятельно. Здесь компонентudLen не нужен, так что его следует удалить.Исходный код программы находится в папке _4x4.1. С помощью программы UniGen вы можете составить квадратылюбого размера, но только по одному для каждого порядка. Увы,все подобные алгоритмы действуют именно так.
Но мы всё-такиможем внести некоторое разнообразие в наши квадраты. Например, если прибавить или вычесть одно и то же число (или умножить на одно и то же число), то квадрат останется магическим, аего магическая сумма изменится. Научите программу составлятьтакие квадраты.2. Можно также поворачивать квадрат на 90 градусов и отражать его относительно горизонтальной и вертикальной осей. Поскольку эти операции проводятся над уже готовыми квадратами,то это задание совсем несложное.3.
Каждый магический квадрат имеет дополнение – другой магический квадрат, который получается из исходного, если все числа внем вычесть из N2+1.4. Для квадратов пятого порядка известны 2 преобразования, порождающие новые магические квадраты.Переставьте столбцы 1 и 5, затем переставьте строки 1 и 5.Переставьте строки 1 и 2, а также 4 и 5, а затем столбцы 1 и 2, 4 и5.5. Усовершенствуйте приложение DEMS, чтобы оно расставлялометки в левом верхнем квадранте случайно.
Так вы добьётесьбольшего разнообразия в готовых изделиях. Не более сложно заставить приложение расставлять метки всеми возможными способами, чтобы можно было составить много разных квадратов.6. Ответы на Пентамагики вы найдёте в конце книги, но почемубы вам не написать приложение, которое могло бы самостоятельно составлять и решать такие головоломки?43Глава 6. Словесные магические квадратыЕсли числовые магические квадраты «официально» признаны первой комбинаторной задачей в истории человечества и известны всем и каждому,то словесные магические квадраты популярностью не избалованы, хотя ипоявились всего на несколько столетий позже знаменитого квадрата Лошу, ещё до нашей эры.В словесных магических квадратах все слова можно прочитать дважды –по горизонтали и по вертикали.
Причём каждое слово пересекается совсеми остальными, так что такие магические квадраты дали начало самойпопулярной головоломке в мире - кроссвордам! Шустрые англосаксонцыпо обыкновению приписали изобретение кроссвордов себе, но, как мы ясно видим, это опрометчивое утверждение можно охарактеризовать русской пословицей Поспешишь – людей насмешишь!Самый знаменитый из всех словесных магических квадратов называютСатор – по первому слову в этом квадрате (Рис.
6.1).Рис. 6.1. Словесный магический квадрат СаторТочный перевод фразы SATOR AREPO TENET OPERA ROTAS неизвестен, нообычно его переводят с латыни как Сеятель Арепо с трудом держит колеса. Можно заметить, что эта фраза одинаково читается и в обратномнаправлении, то есть является палиндромом!44Удивительное дело: романе Умберто Эко Маятник Фуко мы найдёмубийцу, которого зовут … Сатор Арепо:- Сатор Арепо! — кричу я голосом, который бы заставил задрожатьдаже гром.Отложив в сторону колесо, которое он так уверенно держал своимируками убийцы, Сатор Арепо поспешил предстать предо мной. Я узнаюего, впрочем, я и так подозревал, кто он такой.
Это Лучано, калекаэкспедитор, которого Неведомые Настоятели назначили исполнителем моей гнусной и кровавой задачи.Словесные магические квадраты с отдельными словами-палиндромами ипалиндромоидами не редкость, поскольку их составить куда проще, чемс осмысленными фразами (Рис. 6.2).Рис. 6.2.
Словесный магик по-английскиПодобно числовым магическим квадратам, словесный квадрат Сатор использовался в средние века как талисман. Первые христиане из тех жебукв находчиво составили крест Pater Noster (Отче наш) (Рис. 6.3). Лишниебуквы А и О обозначают в нём начало и конец (альфа и омега) всего сущего. По-моему, весьма остроумное решение проблемы.45Рис. 6.3. Магический крестДругие магические квадраты находили применение в магических обрядах.Вот пример такого квадрата (Рис.
6.4). Он, якобы, превращал волшебника вворону, чтобы тот мог летать.Рис. 6.4. Волшебный магический квадрат!Впрочем, такие квадраты малоинтересны, поскольку они составлены избессмысленных (по крайней мере, для непосвященных в таинства) слов.Столетия спустя составление словесных магических квадратов стало излюбленным занятием личностей, склонных к литературному творчеству.46Задача непростая: собрать из «нормальных» слов магический квадрат какможно большего размера. Правда, зачастую в ход идут и редкие слова, иформы слов, а не только имена существительные, как это обычно принятов подобных головоломках.
Как мы вскоре убедимся, конструированиеквадратов из 2-6-буквенных слов не представляет большого труда (Рис.6.5).Рис. 6.5. Размер имеет значение!В английском языке букв меньше, поэтому англичане – не без труда! добрались до квадрата девятого порядка. Посмотреть на него вы можете здесь: http://en.wikipedia.org/wiki/Word_squareКонечно, после такого исторического экскурса трудно отказать себе в удовольствии и не написать программу, которая умела бы составлять такиеудивительные квадраты!47Проект Магические слодраты (WordSquares)Мы сразу откажемся от глобальной задачи – составить вообще все возможные квадраты, поскольку труд окажется непосильным.
Мы предоставим пользователю возможность самому выбрать первое слово для квадрата, а все остальные будет подбирать наша программа.Нетрудно догадаться, что нам потребуется словарь, из которого мы и будем выбирать слова для квадрата. Все слова в квадрате имеют равнуюдлину, поэтому вполне разумно воспользоваться фракционным словарем.Большая часть полей нашей программы как раз и будет задействована призагрузке словаря и хранении списка подходящих слов.
Другие поля понадобятся нам для работы с магическим квадратом – для хранения порядкаквадрата, слова пользователя и массива слов в квадрате://ПРОГРАММА ДЛЯ СОСТАВЛЕНИЯ//СЛОВЕСНЫХ МАГИЧЕСКИХ КВАДРАТОВ//порядок квадрата:int N = 0;Random rand = new Random();//словарь:rvDict dict;//магический квадрат:string[] mq;//число подходящих слов://int nLex;//число найденных магических квадратов:int nVar;//список подходящих слов:List<string> lex= new List<string>();//=true, если слово использовано:List<bool> flg= new List<bool>();Словарь по умолчанию лучше загрузить сразу же при запуске приложения,чтобы не заставлять пользователя делать это самостоятельно.
А затем онможет выбрать любой словарь из папки с программой или загрузить собственный.public frmWS(){InitializeComponent();//загружаем словарь:dict = new rvDict("frc.txt");dict.CreateBeginWord();}48В текстовое поле txtWord1 пользователь должен впечатать первое словодля квадрата.
Мы должны разумно ограничить его длину. Действительно,квадрат из одной буквы составить можно и без помощи компьютера, а дляквадрата из семибуквенных слов практически невозможно наугад выбратьпервое слово.После нажатия на кнопку btnGen мы переходим в метод btnGen_Click, гдепо длине слова легко определяем порядок квадрата и создаём новый строковый массив для него. Первое слово нам уже известно, поэтому мы тут жезаписываем его в квадрат://СОСТАВЛЯЕМ МАГИЧЕСКИЙ КВАДРАТprivate void btnGen_Click(object sender, EventArgs e){//первое слово:string word1 = txtWord1.Text.ToUpper();//Длина слова:N = word1.Length;//если слово отсутствует, выбираем случайно из словаря:if (word1 == ""){N = (int)udLength.Value;int id= rand.Next(dict.beginWord[N],dict.beginWord[N]+dict.numWord[N]);word1 = (string)dict.list[id];txtWord1.Text = word1.ToUpper();}else if (N < 2 || N > 6){MessageBox.Show("В слове должно быть от двух до шестибукв!");return;}//создаем массив для слов:mq = new string[N + 1];mq[1] = word1;flg.Clear();//составляем список подходящих слов://nLex = 0;string letters = word1.Substring(1, N - 1);lex.Clear();//длина всех слов должна быть равна порядку квадрата n:for (int i = dict.beginWord[N]; i < dict.beginWord[N] +dict.numWord[N]; ++i){//не включаем в список первое слово:49if ((string)dict.list[i] == word1) continue;//слово должно начинаться с буквы в letters:char ch = ((string)dict.list[i])[0];//если нашли слово,if (letters.IndexOf(ch) >= 0){//добавляем его в список:lex.Add((string)dict.list[i]);//слово не использовано:flg.Add(false);}}//пока не нашли ни одного квадрата:nVar = 0;//составляем квадрат, начиная со второго слова:recGenerate(2);lstRes.Items.Add("");lstRes.Items.Add("Найдены все решения: " + nVar.ToString());lstRes.Items.Add("");lstRes.TopIndex = lstRes.Items.Count - 27;}Так как словарь dict довольно большой, а нам придётся перебирать всеслова заданной длины, то лучше сразу об этом призадуматься и постараться уменьшить перебор.
Это очень просто! Первое слово квадрата даётнам начальные буквы всех остальных слов. Это легко понять, если посмотреть, как составлен магический квадрат Sator. Нам известна длина слов иих начальные буквы, поэтому мы составляем словарик lex, в которыйвключаем только те слова, которые могут быть поставлены в квадрат. Он,безусловно, будет значительно короче общего списка слов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
