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

Допустим есть город САРАТОВ, название заканчивается на букву В, значит требуется назвать другой город, у которого в названии первая буква В, ну и далее по аналогии (думаю все помнят эту детскую игру). Название не может начинаться с твёрдого знака!!! в этом случае название начинается с предпоследней буквы. Повторять названия НЕЛЬЗЯ!
Надо написать программу или хотя бы алгоритм, которая из 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% случаев, а следовательно вариант отпадает, т.к. ПХП просто упадет.

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

Можно. Тут уже все-таки надо более детально смотреть ресурсы и пробовать.

топорно конечно сделал (ну так ведь не мастер ), но просто хотелось попробывать

Код

<?php mysql_connect('localhost', 'root', '') or die("Ошибка соединения"); mysql_select_db('chat'); if(!isset($_GET[sity])){     mysql_query("UPDATE `test` SET `index`='0' WHERE `index`=1");     $sity = "саратов";     $mes .=$sity.' -> ';     $f_sity = f_sity($sity);     $mes .= $f_sity[name];     $mes .= ($f_sity[index]==0)? "<br><br><a href='index.php'>Сначала</a>" : "<br><br><a href='index.php?sity=".$f_sity[name]."&index=".$f_sity[index]."'>Дальше</a>"; }else{     $sity = $_GET[sity];     $mes .=$sity.' -> ';     $f_sity = f_sity($sity);     $mes .= $f_sity[name];     $mes .= ($f_sity[index]==0)? "<br><br><a href='index.php'>Сначала</a>" : "<br><br><a href='index.php?sity=".$f_sity[name]."&index=".$f_sity[index]."'>Дальше</a>"; } echo $mes; function f_sity($sity){     $alfa = substr($sity, -1);     if(($alfa=="ь") or ($alfa=="Ь")){$alfa = substr($sity,-2,1);}     $z = "SELECT * FROM `test` WHERE `index`=0 AND LEFT(sity,1)='".$alfa."' LIMIT 1";     $r = mysql_query($z);     if (mysql_num_rows($r)>0){         $f = mysql_fetch_array($r);         $f_sity[name] = $f[sity];         $f_sity[index] = 1;         mysql_query("UPDATE `test` SET `index` = '1' WHERE `sity`='".$f_sity[name]."'") ;     }else{         $f_sity[name] = 'Городов на букву &laquo;<b>'.$alfa.'</b>&raquo; больше нет';         $f_sity[index] = 0;     }     return $f_sity; } ?>

Код

CREATE TABLE `test` (   `sity` varchar(200) NOT NULL default '',   `index` tinyint(1) NOT NULL default '0',   PRIMARY KEY  (`sity`) ) ENGINE=MyISAM DEFAULT CHARSET=cp1251; INSERT INTO `test` VALUES ('саратов', 0); INSERT INTO `test` VALUES ('вологда', 0); INSERT INTO `test` VALUES ('архангельск', 0); INSERT INTO `test` VALUES ('курск', 0); INSERT INTO `test` VALUES ('кёльн', 0); INSERT INTO `test` VALUES ('новосибирск', 0); INSERT INTO `test` VALUES ('суздаль', 0); INSERT INTO `test` VALUES ('владимир', 0); INSERT INTO `test` VALUES ('москва', 0); INSERT INTO `test` VALUES ('рим', 0);

сделал с базой данных и пошагово, т.к. самому было интересно , но перевести это всё для записи в TXT файл и за один цикл думаю легко

а теорию графов никто не учил ... это же еб .... шся перебором это делать

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

Цитата

а теорию графов никто не учил

Я не учил... Поподробнее можно.

и меня заодно научите

Вы знаете што такое дерево даных? Если знаете то дерев мает одного предка и много нащадков. А граф может иметь много предков и много нащадков.

Как паутина

як можливо маiть богато предков?


зы - Diesel Draft, пишите по-русски!!!

Цитата(Diesel @ 20.12.2005, 00:17)

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

Это самый правильный вариант, для решения таких задач. Тем более сведя графы к матрицам инцидентности или смежности вся задача превратится в простые математические вычисления (сложения вычитания матриц и.т.д.) ....
Хотя по сути задача не легкая.

Самое простое, что приходит в голову - сделать по алгоритму фронта волны.
По Дейкстре, увы, не найдешь, так как классический Дейкстра - для бесконтурных графов.
По-моему, сложность в любом случае будет n*4. Но это все же лучше, чем n! (перебор).
Но вообще задачу обалдеешь делать.

Это сообщение отредактировал(а) error - 4.1.2006, 00:03

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

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

А это на рюкзак не похоже?

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

Можно свести задачу к следующей.
Есть n слов.
Создадим множество {b[i], e[i]}, отображением из множества введеных слов по следующему правилу:
b[i] - первая буква i-того слова
e[i] - первая с конца буква i-того слова, с которой может начинаться другое слово (т.е. не 'ъ', 'ы' и т.п.)
пусть A - объединение множеств {b[i]} и {e[i]} m-размерность A
Создадим матрицу B размерности m на m такую, что B[u, v] = {набор целых чисел из интервала [1..n] таких, что для любого числа x из этого набора b[x] = A[u], e[x]=A[v]}
Полученная матрица описывает орграф. Таким образом решением задачи будет максимальный эйлеров контур в этом орграфе + (возможно) две дуги. Одна входящая в эйлеров контур (начальное слово из условия задачи) и одна исходящая (конечное слово). Естественно, что таких дополнительных дуг может и не быть или может быть одна.
Нахождение такого эйлерова контура гораздо менее трудоемкая операция чем полный перебор.

Емхмо, проще сделать так.
Завести матрицу mat['А'..'Я','А'..'Я']. И заполнить ее таким образом
Например элементу mat['A','H'], будем ставить количество городов, которые начинаются на А заканчиваются на Н. А потом с ней работать, что будет побыстрее.
Кстати это и будет матрица смежности ориентированого графа, у которого вершинам соответсвуют буквы русского алфавита. И здесь можно попробговать алгоритм Эйлера... Приблизительный ответ это даст.

poor_yorik, только все-таки надо брать не mat['А'..'Я','А'..'Я'], а как я предложил (см. выше) т.к. у меня матрица меньше получится. А что в элементах хранить - не суть важно (из двух этих вариантов). Либо там храняться дуги с номерами (номер слова) - мой вариант, либо там хранится количество дуг (твой вариант), но в твоем варианте придется востанавливать последовательность слов по найденным дугам - это выйдет немного дольше

Представте себе города на карте. Рассмотрим все пары городов. Если последняя буква названия первого города совпадает с первой буквой названия второго города, то проложим между ними дорогу с односторонним движением. Таким образом на карте возникнет сеть дорог с односторонним движением (ориентированный граф).

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

Задача вообще говоря NP-полна. Но метод ветвей и границ решает ее довольно быстро.(хотя и не полиномиально). Метод ветвей и границ конкретно для этой задачи преращается в рекурсивный обход ориентированного графа в глубину.

это задача класса P Space поэтому полный перебор