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'], будем ставить количество городов, которые начинаются на А заканчиваются на Н. А потом с ней работать, что будет побыстрее.
Кстати это и будет матрица смежности ориентированого графа, у которого вершинам соответсвуют буквы русского алфавита. И здесь можно попробговать алгоритм Эйлера... Приблизительный ответ это даст.