В. Рубанцев - Как решать комбинаторные задачи на компьютере (1127108), страница 5
Текст из файла (страница 5)
Также мы незабываем заполнить список флажков «фальшивыми» значениями, которые отмечают еще неиспользованные слова.Иногда первое слово не приходит в голову или его нужно выбрать случайно. Поэтому мы установим на форме компонент udLength, в которомудобно задавать длину слов (или порядок квадрата). Но тут может возникнуть непреднамеренная коллизия со словом в поле txtWord1, поскольку программа будет теряться в догадках, выбирать ли ей слово случайно или брать то, которое ввёл пользователь. Чтобы рассеять её сомнения, следует очистить поле txtWord1, дважды кликнув на нём:private void txtWord1_MouseDoubleClick(objecttArgs e){txtWord1.Text = "";sender,MouseEven-50}Вот теперь программа поймёт вас правильно и выберет слово случайно.И вот у нас всё готово для составления магического квадрата, и мы отправляемся прямиком в рекурсивный метод recGenerate.Конечно, метод должен быть именно рекурсивным, поскольку действияпри составлении квадрата практически полностью повторяются для каждого нового слова: ставим второе слово с учётом первого, затем ставимтретье слово с учётом первых двух, и так далее, пока квадрат не будет построен или мы не убедимся, что его построить нельзя.Единственная трудность здесь - в организации проверки слов из списка:годятся ли они для квадрата или нет.Опять обратимся к магическому квадрату Sator.
В нашем случае первоеслово уже стоит в квадрате:SATORA....T....O....R....Хорошо видно, что второе слово оно должно начинаться с буквы А (второеслово – вторая буква в исходном слове), а все остальные четыре буквы могут быть любыми.Ставим второе слово:SATORAREPOTE...OP...RO...Третье слово должно начинаться с букв TE - а это третья буква первогослова и третья буква второго слова.51Если решение ещё не пришло вам в голову, то продолжайте составлятьквадрат. Рано или поздно вы найдёте простой алгоритм для составленияподстроки shablon, с которой и должно начинаться очередное слово://создаём шаблон для слова num:string shablon = "";for (j = 1; j < num; ++j)shablon += mq[j].Substring(num - 1, 1);Остальное, как говорится, дело техники, и рекурсивный метод готов://Рекурсивный метод составления магических квадратовvoid recGenerate(int num){int j = 0;//создаем шаблон для слова num:string shablon = "";for (j = 1; j < num; ++j)shablon += mq[j].Substring(num - 1, 1);//перебираем все слова в списке lex:foreach (string s in lex){//оно должно начинаться с букв shablon:if (s.StartsWith(shablon)){//нашли подходящее слово-->//ставим его в квадрат:mq[num] = s;flg[j] = true;if (num < N) recGenerate(num + 1);else writeVar();++j;}//ifflg[j] = false;}//for} //recGenerateНайденные магические квадраты мы печатаем в списке lstRes://ПЕЧАТАЕМ МАГИЧЕСКИЙ КВАДРАТvoid writeVar(){//нашли еще один магический квадрат:nVar++;lstRes.Items.Add("");lstRes.Items.Add("Вариант: " + nVar.ToString());for (int i = 1; i <= N; ++i) lstRes.Items.Add(mq[i]);//прокручиваем список вниз:52lstRes.TopIndex = lstRes.Items.Count - 27;lstRes.Invalidate();Application.DoEvents();}Ну вот и пришло время позабавиться!Запускаем программу и вводим слова из 2-6 букв.
Результат получаеммгновенно (Рис. 6.6).Рис. 6.6. Магическое производство налажено!Так мы можем составить сколько угодно магических квадратов!Если вам наскучит словарь по умолчанию, вы в любой подходящий моментможете загрузить другой, нажав кнопку btnLoadDict:53//ЗАГРУЖАЕМ СЛОВАРЬ ПО ВЫБОРУprivate void btnLoadDict_Click(object sender, EventArgs e){dict = new rvDict();dict.Load();//фракционируем список://dict.Fract();dict.CreateBeginWord();}Для составления больших магических квадратов нужен и солидный словарь.
Например, с файлом SSSRLfrc.txt я нашёл 21 решение для ведущегослова МОСКВА (Рис. 6.7), тогда как словарь по умолчанию не находит вообще ни одного!Рис. 6.7. Москва – как много в этом!..54А с иностранными словарями, например DeutschUnicodeFRC.txt, вы можетесоставлять магические квадраты на чуждых вам языках, даже не зная ниодного иностранного слова (Рис. 6.8)!Рис. 6.8. Шпрехен Зи дойч?Исходный код программы находится в папке WordSquares.55Примерный интерфейс приложения1. Хотя наш алгоритм работает достаточно быстро, но при поискевсех квадратов заданного размера он будет неуклюже составлятьсписок подходящих слов для каждого нового начального слова.Лучше один раз и навсегда запомнить индексы начала не толькослов заданной длины, но и каждой буквы в отдельности.
Тогда принеобходимости вы сразу выйдете на нужную часть списка. Для56хранения начальных индексов годится структура данныхDictionary<>, а вот для индексов начала и конца слов, а такжефлажка их использования придётся завести структуру.Ещё одна возможность оптимизации – записывать слова в сетку непоследовательно, а выбирать такую начальную букву, на которуюимеется меньше всего подходящих слов. Например, если первоеслово ПАРОЛЬ, то нет никакого смысла перебирать начальныеслова, поскольку на мягкий знак слов нет вообще.2.
В нынешнее время словесные квадраты утратили свою магическую силу и используются исключительно как головоломки.В простейшем варианте – это обычный кроссворд (Рис. 6.9). Иногда такиезадания встречаются в головоломных журналах, но магические квадратыздесь сильно уступают своим потомкам: они маленькие по размерам ивсе слова в сетке повторяются дважды, что не очень хорошо действуетна умных людей. Совсем маленькие квадраты и вовсе неинтересны, абольшие трудно составлять, поэтому в них неизбежно попадают редкиеслова.Рис. 6.9.
Магический кроссворд1. Вот тебе проблема!2. Приятный запах денег.3. Главный герой третьей главы.4. Жидкий ароматизированный крахмал для машинной и ручной стирки.5. Традиционное блюдо грузинской кухни.6. Потеря тонуса мышц.57Некоторое разнообразие привносят новые формы сетки, отличные отквадратной (Рис.
6.10):Магические крестыМагическая лестница Магический треугольникРис. 6.10. Магические фигурыДругой тип заданий скорее логический и напоминает знаменитые пазлы.Нужно правильно расставить слова в пустом квадрате (Рис. 6.11).58Рис. 6.11. Магический пазлИ наконец, самая популярная головоломка из этой серии. Первое словозаписано в квадрат (Рис. 6.12).Рис. 6.12. Магическая сеткаСетка сопровождается таблицей, в которой указаны буквы и их число –для тех слов, которые нужно найти (Рис.
6.13).59Рис. 6.13. Магическая статистикаПоследняя строка этой таблицы оставлена пустой, чтобы отгадчик моготмечать вышедшие буквы. По этим данным нужно «вычислить» все слова и заполнить сетку.Эта задача также логическая, но предполагает и знание слов. Легко догадаться, что табличная буква, присутствующая в единственном числе,должна стоять на главной нисходящей диагонали квадрата, а остальныебуквы располагаются симметрично относительно этой диагонали.60Глава 9. Считаем деньгиМахнём не глядя,как на фронте говорят...Песня из фильма Щит и мечЗадача о размене денег возникла задолго до появления самих денег – ещёпри натуральном обмене. Действительно, роль денег тогда исполнялиразличные ценные предметы: ракушки, зерно, шкуры, соль, плоды, животные.
Пережитки далёкого «бартерного» прошлого сохранились до нашихдней. Именно так и сейчас обмениваются коллекционеры книг, значков,марок и прочей утвари.Первыми настоящими, металлическими деньгами начали пользоватьсялидийцы в 8 веке до нашей эры. Ну, а дальше пошло-поехало – и теперь безденег уже ничего и не идёт, и не едет.Но для нас важнее комбинаторная сторона этого меркантильного вопроса,а именно: как правильно разменять одни деньги на другие и при этом неостаться внакладе.С разменом денег тесно связана другая задача – помоложе, но тоже имеющая многовековую историю – о разбиении чисел.
Если бы в какой-либо денежной системе были монеты всех достоинств, начиная с одного «цента»,то достаточно было бы решить только эту задачу. Но, как мы знаем, человечество проявило здесь немалую изобретательность, поэтому размен денег даётся значительно труднее.Проект Разменный пункт (Разбиения)Пусть у нас имеется сколько угодно монет любого достоинства и нам нужно составить из них сумму в n копеек. В комбинаторике подобная задачаформулируется так:Сколькими способами можно записать натуральное число n в виде суммыn = n1 + n2 + … + nk ?(1)Последовательность слагаемых при этом не учитывается, но принято записывать их в порядке убывания, то есть от больших слагаемых к меньшим.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
