Этюды программистов

Модераторы: Duncon, Naeel Maqsudov, Хыиуду, Игорь Акопян

Ответить
jojo
Сообщения: 14
Зарегистрирован: 24 май 2004, 11:20
Контактная информация:

24 дек 2004, 06:55

Есть задача для студента мехмата :)
я то уже не студент :) мозги атрафировались

Пусть слово - это последоватетьность от 1 до 8 символов, не включающая пробелов Ввводится n слов А1, ... , An. Можно ли из переупорядочить так, чтобы получилась "цепочка", т.е. для каждого слова Aj его первая буква совпадать с последней буквой предыдущего слова, а последняя буква Aj с первой буквой последующего слова; соотвественно последняя буква последнего слова должна совпадать с первой буквой первого слова. В "цепочку" входят все n слов без повторений. Дать ответ в виде "Можно"/"Нельзя". Если такое упорядочение возможно, то вывести какую-нибудь цепочку слов. Слова при выводе разделяются пробелами!

Решение нада пож-та
Кому не лень

Было б неплохо найти решебник к книге
Ч.Уэзерелла "Этюды для программистов"
Jojo®
Аватара пользователя
Naeel Maqsudov
Сообщения: 2551
Зарегистрирован: 20 фев 2004, 19:17
Откуда: Moscow, Russia
Контактная информация:

24 дек 2004, 10:41

Так вот оказывается чем занимаются на мехмате :)

У меня тоже атрафировались мозги и мне в голову ничего не приходит иного как разобрать ввод на отдельные слова, а потом попытаться построить N деревьев, начиная от каждого слова. Большинство деревьев выродятся в единственный элемент (т.е. будут состоять только из корня), а результативными будут только деревья, содержащие N уровней. В этих результативных деревьях выбираем все самые длинные ветви (из N элементов), это и есть все решения.

Если результативных деревьев построить не удалось, то решений нет.

В этом алгоритме есть, конечно, недостаток. Если во введенном предложении есть повтотряющиеся слова, то их перестановка даст один и тот же результат, однако, для данного алгоритма это будут разные результаты и для фразы, где "ааа" повторяется N раз будет найдено N^2 лишних решений...
jojo
Сообщения: 14
Зарегистрирован: 24 май 2004, 11:20
Контактная информация:

24 дек 2004, 10:59

Интересно !!!
Спасибо
Jojo®
Аватара пользователя
Naeel Maqsudov
Сообщения: 2551
Зарегистрирован: 20 фев 2004, 19:17
Откуда: Moscow, Russia
Контактная информация:

24 дек 2004, 12:46

Есть еще подход, рекурсивный, но экономящий память, и работающий о первого решения (или до конца, если решений нет).

1.
Разбиваем ввод на список (коллекцию или динамический массив) слов. (Т.е. обеспечиваем доступ к словам по индексам).
2.
Строим спиисок IDX (коллекцию или динамический массив) из N индексов, сначала в порядкее оот 0 до N.
3.
Вызываем рекурсивную функцию, которая на рекурсивном спуске проверяет, является ли текущая перестановка решением. Если да, то возвращает True и выходит, иначе меняет местами очередные idx idx[j] и продолжает рекурсивный спуск, если переставлять нечего, то возвращает результат False и выходит.
4.
В завимсимости от полученного результата выводим первое найденное решение или сообщаем об оттсутствии решения.

PS
не совсем еще атрофировались мозги-то ;)
(У нас должна быть процедура, которая определяет является ли текущая перестановка решением, а перестановка определяется порядком значение в массиве IDX)
Вызываем
Eugie
Сообщения: 707
Зарегистрирован: 17 фев 2004, 23:59
Откуда: SPb

24 дек 2004, 16:41

Я эту задачу знаю в другой интерпретации: есть набор костяшек домино, требуется узнать, какую цепочку максимальной длины можно из них составить. Если добавить условие замыкания и использования всех доминошек, получим полную аналогию.

Можно дать еще одну эквивалентную формулировку: интерпретируем начальные и конечные буквы слов как вершины графа, а сами слова - как ребра. Тогда задача сводится к выяснению, является ли такой граф эйлеровым циклом, т.е. допускает такой циклический обход по всем ребрам, при котором каждое ребро проходится только 1 раз. Для эйлерова цикла есть простой критерий: 1) граф должен быть связным; 2) степени всех вершин должны быть четными, т.е. другими словами, число входов = числу выходов. Условие 2) легко проверить и если ответ отрицательный, сразу сказать, что искомой цепочки нет.
Хыиуду
Сообщения: 2388
Зарегистрирован: 06 мар 2005, 21:03
Откуда: Москва
Контактная информация:

16 мар 2005, 18:41

Возможно, я повторяю Eugie, но по крайней мере, я расшифрую его объяснение для тех, кто не сталкивался с Эйлеровыми циклами и прочими прелестями теории графов. Надо взять множество первых букв слов и множество последних. Если эти множества не совпадают, значит, построить цепочку нельзя.
А если можно - просто взять любое слово первым, прицепить к нему любое из подходящих после него, потом любое из подходящих ко второму. В любом случае цепочка должна замкнуться. Вроде бы так, а подробнее проверять лень. Я хоть и студент, но не мехмата.
Искусство программирования - заставить компьютер делать все то, что вам делать лень.
Для "спасибо" есть кнопка "Спасибо" в виде звездочки внизу под ником автора поста.
Аватара пользователя
Romeo
Сообщения: 3091
Зарегистрирован: 02 мар 2004, 17:25
Откуда: Крым, Севастополь
Контактная информация:

16 мар 2005, 18:56

Нет, первое попавшееся не получится. Цепочка может замкнуться раньше, чем её положено. А вообще классический пример задачки на перебор.
Entites should not be multiplied beyond necessity @ William Occam
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.
Vovik
Сообщения: 18
Зарегистрирован: 05 янв 2005, 14:39
Откуда: Киев

17 мар 2005, 00:23

Никакого перебора! Эйлеров цикл строится по следующему алгоритму:
1. Проверяем критерий Эйлера (к-во слов начинающехся с данной буквы равно к-ву слов на эту букву заканчивающихся + от для любой буквы (из тех что стоят в начале какого-то слова) можно построить цепочку слов, заканчиваищююся в любой другой такой букве). Т.е. граф связный и в каждую вершину входит столько ребер, сколько выходит (граф ориентированный).
2. Если граф (слова) удовлетворяют критерию, то можно построить такой цикл! Всегда! (это знают не только студенты мехмата :) ). Делаем по следующему алгоритму:
а) любой буквы и идем в любую другую (не используя дважды одно слово), из той буквы в другую и т.д. пока не прийдем к начальной (обязательно прийдем, можно доказать !).
б) Получили некий цикл, если он включает все ребра, то он искомый, если нет, ищем в этом цикле вершину из которой выходят неиспользованые ребра (буква, с которой начинаются неисп. слов). Повторяем для нее п. а). новый получившийся цикл "подшиваем" к уже построенному, повторяем п. б)

Болие подробно см. в литературе про Эйлеров цикл. Для ответа на поставленный вопрос сам цикл строить не нужно, достаточно проверить критерий 1.
С уважением
Ответить