Темы курсовых работ по «Технология программирования (Python)»
жүктеу/скачать 0,69 Mb.
|
- Бұл бет үшін навигация:
- 4. Дробление заявок.
- Тема 5: Эвристическое составление головоломки
| Неожиданная удача — соответствующий игрок может немедленно продать любое число из имеющихся у него ЕГП по 6500 долл.
3. Закрытие фабрики. В очередной месяц, как раз перед подачей заявки на строительство, игрок может закрыть все или некоторые свои фабрики. Начиная со следующего месяца постоянные издержки по такой фабрике сократятся вдвое, но продукции не будет совсем. Впоследствии закрытую фабрику можно открыть в той же точке очередного месячного цикла. Через два месяца после этого фабрика снова вступает в строй, и надо опять оплачивать издержки в полном размере. Например, вновь открытая в 13-м месяце фабрика вступает в строй действующих в 15-м. 4. Дробление заявок. На любых торгах любой игрок может сделать одну заявку, две или ни одной. Общий объем заявок одного игрока как на покупку, так и на продажу не должен превосходить предложений банка (для продажи — еще и имеющегося у данного игрока объема продукции). Банк рассматривает различные заявки одного игрока точно так же, как заявки разных игроков. Заявки эти конкурируют как друг с другом, так и с заявками других игроков. Удовлетворены могут быть обе, одна или ни одной. При прочих равных условиях по-прежнему побеждает старший игрок. Тема 5: Эвристическое составление головоломки Многие считают кроссворды слишком трудной головоломкой, потому что отгадать слово им не под силу. Но вписывать буквы в клетки нравится. Для подобных людей существует более простая головоломка — крисс-кросс. Каждый крисс-кросс состоит из списка слов, разбитых для удобства на группы в соответствии с длиной и упорядоченных по алфавиту внутри каждой группы, а также из схемы, в которую нужно вписать слова. Схема подчиняется тому же правилу, что и в кроссворде, — в местах пересечения слова имеют общую букву, однако номера отсутствуют, поскольку слова известны заранее, требуется лишь вписать их в нужные места. Обычно в схемах крисс-кросса гораздо меньше пересечений по сравнению с кроссвордами, а незаполняемые клетки не заштриховываются, если это не приводит к путанице. Крисс-кросс всегда имеет единственное решение, в котором используются все перечисленные слова. Пример головоломки, правда очень маленький, приведен на рис. 5.1. Заметьте, что длина слова служит важным ключом к разгадке. Рисунок 5.1. Пример головоломки крисс-кросс. Тема. Напишите программу, читающую список слов и строящую для этого списка правильную схему крисс-кросса. Представьте заполненную схему как доказательство того, что она правильная. Возможно, хотя и маловероятно, что для данного списка слов не существует решения (как и в кроссворде, схема должна быть связной). Ваша программа должна сообщать о всех неудачах при построении схемы и о всех ситуациях, нарушающих однозначность (таких, например, как наличие повторяющихся слов). Попутно решите еще одну задачу — получите красивый графический вывод. Указания исполнителю. Качество схем крисс-кросса пропорционально их «связанности», т. е., чем теснее в среднем слова переплетены с соседями, тем интереснее головоломка. Связанность можно измерять по-разному: как отношение площади схемы к площади наименьшего объемлющего прямоугольника; как среднее число пересечений на слово; как среднее число пересечений на букву; как минимальное число пересечений на слово. При генерации головоломок крисс-кросс для массовых изданий использовалась коммерческая программа, но головоломки получались неинтересные — слишком длинные и извилистые. Когда ваша программа заработает, позаботьтесь об увеличении связанности. Предложенная задача — классическая для метода перебора с возвратами. Начните с вписывания слов в фиксированную схему, пока в списке есть подходящие слова. Когда они кончатся, вернитесь на шаг назад, удалив последнее вписанное слово, и попытайтесь вписать другое слово. Необходимо разработать эвристику для выбора очередного кандидата из списка неиспользованных слов. Контроль однозначности должен включать проверку того, что в схеме нельзя поменять местами никакие два слова равной длины. Достаточна ли такая проверка? Нет ли более изящной? Полное алгоритмическое решение, максимизирующее связанность, несомненно, представит значительный теоретический интерес. жүктеу/скачать 0,69 Mb. Достарыңызбен бөлісу:
|