Интересная задача, ГОРОДА

Допустим есть город САРАТОВ, название заканчивается на букву В, значит требуется назвать другой город, у которого в названии первая буква В, ну и далее по аналогии (думаю все помнят эту детскую игру). Название не может начинаться с твёрдого знака!!! в этом случае название начинается с предпоследней буквы. Повторять названия НЕЛЬЗЯ!
Надо написать программу или хотя бы алгоритм, которая из TXT файла читала названия городов и постоила цепочку максимальной длинны и запишет её в новый файл.

а в чём собственно вопрос ?

Цитата

а в чём собственно вопрос ?

Помогите алгоритм составить, а может и решение подскажите. А то торможу я.

Цитата(Denny @ 17.12.2005, 12:04)

Допустим есть город САРАТОВ, название заканчивается на букву В, значит требуется назвать другой город, у которого в названии первая буква В, ну и далее по аналогии (думаю все помнят эту детскую игру).

Вот тебе и алгоритм.

1.Береш первый город
2виводим назву города
3.Узнаем какая последняя буква
4. Ищем в списке город з таким названием
5. стираем город з списка (штобы не повторялса)
6. виводим назву города
7. если список не пуст переходим на 3

Вопрос же ясно задан - построить самую длинную цепочку. А вы тут про что?...

Вот Именно МАКСИМАЛЬНОЙ ДЛИНЫ.
Здесь то я и сел в лужу.

Делаем массив городов, сортируем по алфавитному порядку.
Начинаем с какой-то буквы.
Выбираем город на эту букву (первый который попадается). Записываем его в строчку, удаляем из массива, берем его последнюю букву и опять ищем в массиве слово.

Можно сделать как фичу, что если есть несколько городов на одну букву, то мы стараемся из них выбрать тот, последняя буква которого доаст продлжение уепочки, т.е. на нее будет начинаться какое-то слово.

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

или перебор включать когда цепочка составленна и слова остались, вернуться назад, попытаться их вставить туда и продолжить перебор.

Цитата(Temp @ 18.12.2005, 17:45)

такого алгаритма наверное нет, только перебором,

Не совсем. Перебор для строк можно сократить, к примеру, поиск делать методом половинного деления. Если очень много городов, то через внешний массив с индексами для поиска.

Цитата

поиск делать методом половинного деления

это как?

Можно например сперва составить цепочку с именами начинающемися на "неудобные" буквы (Ц, Ч, Ф) сложность будет именно их пристроить, а остолькое уже проще приложить.

Цитата(Temp @ 18.12.2005, 19:24)

это как?

Сам метод половинного деления знаешь? Только тут со строками работаешь.

Цитата(Temp @ 18.12.2005, 19:24)

Можно например сперва составить цепочку с именами начинающемися на "неудобные" буквы (Ц, Ч, Ф) сложность будет именно их пристроить, а остолькое уже проще приложить.

Не, не катит.

Есть алгоритм поло-перебор: когда создаетса дерева з возможных вареантов.
увеличеваетса скорость но и увеличуетса память

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

например:

саратов + вологда + архангельск + киев + вильнюс -> нет на "с"
саратов + вологда + архангельск + киев + владимир + рим -> нет на "м"
саратов + вологда + архангельск + киев + владимир + рим + москва -> нет на "а"
саратов + вологда + архангельск + киев + владимир + рим -> нет на "а" кроме "москва"
саратов + вологда + архангельск + киев + владимир -> нет на "р" кроме "рим"
саратов + вологда + архангельск + киев- > нет на "в" кроме "владимир"
саратов + вологда + архангельск + курск + кёльн + новосибирск + суздаль + львов + владимир + рим + москва

и т.д.

и сохранять все таблицы а потом брать самую длинную
или бред?

Это сообщение отредактировал(а) Alx - 19.12.2005, 01:40

Цитата(Alx @ 19.12.2005, 01:39)

и сохранять все таблицы а потом брать самую длинную

Да, это самый верный способ, но таких комбинаций получится ужас какой. Ну может получиться в 70% случаев, а следовательно вариант отпадает, т.к. ПХП просто упадет.