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

[jojo]

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

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

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

Было б неплохо найти решебник к книге
Ч.Уэзерелла "Этюды для программистов"

[Naeel Maqsudov]

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

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

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

В этом алгоритме есть, конечно, недостаток. Если во введенном предложении есть повтотряющиеся слова, то их перестановка даст один и тот же результат, однако, для данного алгоритма это будут разные результаты и для фразы, где "ааа" повторяется N раз будет найдено N^2 лишних решений...

[jojo]

Интересно !!!
Спасибо

[Naeel Maqsudov]

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

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

PS
не совсем еще атрофировались мозги-то
(У нас должна быть процедура, которая определяет является ли текущая перестановка решением, а перестановка определяется порядком значение в массиве IDX)
Вызываем

[Eugie]

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

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

[Хыиуду]

Возможно, я повторяю Eugie, но по крайней мере, я расшифрую его объяснение для тех, кто не сталкивался с Эйлеровыми циклами и прочими прелестями теории графов. Надо взять множество первых букв слов и множество последних. Если эти множества не совпадают, значит, построить цепочку нельзя.
А если можно - просто взять любое слово первым, прицепить к нему любое из подходящих после него, потом любое из подходящих ко второму. В любом случае цепочка должна замкнуться. Вроде бы так, а подробнее проверять лень. Я хоть и студент, но не мехмата.

[Romeo]

Нет, первое попавшееся не получится. Цепочка может замкнуться раньше, чем её положено. А вообще классический пример задачки на перебор.

[Vovik]

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

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