Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Интересная логическая задача


Автор: Denny 17.12.2005, 12:04
Интересная задача, ГОРОДА

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

Автор: Temp 17.12.2005, 15:39
а в чём собственно вопрос ?

Автор: Denny 17.12.2005, 16:15
Цитата

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

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

Автор: Mal Hack 17.12.2005, 21:16
Цитата(Denny @ 17.12.2005, 12:04)
Допустим есть город САРАТОВ, название заканчивается на букву В, значит требуется назвать другой город, у которого в названии первая буква В, ну и далее по аналогии (думаю все помнят эту детскую игру).

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

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

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

Автор: Denny 18.12.2005, 16:14
Вот Именно МАКСИМАЛЬНОЙ ДЛИНЫ.
Здесь то я и сел в лужу. smile

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

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

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

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

Автор: Mal Hack 18.12.2005, 18:10
Цитата(Temp @ 18.12.2005, 17:45)
такого алгаритма наверное нет, только перебором,

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

Автор: Temp 18.12.2005, 19:24
Цитата
поиск делать методом половинного деления

это как?

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

Автор: Mal Hack 18.12.2005, 20:18
Цитата(Temp @ 18.12.2005, 19:24)
это как?

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

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

Не, не катит.

Автор: Diesel Draft 18.12.2005, 23:32
Есть алгоритм поло-перебор: когда создаетса дерева з возможных вареантов.
увеличеваетса скорость но и увеличуетса память smile

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

например:

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

и т.д.

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

Автор: Mal Hack 19.12.2005, 02:05
Цитата(Alx @ 19.12.2005, 01:39)
и сохранять все таблицы а потом брать самую длинную

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

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

Автор: Mal Hack 19.12.2005, 02:23
Можно. Тут уже все-таки надо более детально смотреть ресурсы и пробовать.

Автор: Gold Dragon 19.12.2005, 11:04
топорно конечно сделал (ну так ведь не мастер smile ), но просто хотелось попробывать
Код

<?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);


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

Автор: Хоббит 19.12.2005, 19:57
а теорию графов никто не учил ... это же еб .... шся перебором это делать

Автор: Diesel Draft 20.12.2005, 00:17
можно попробувать создать граф, апотом искать самый походящый путь.
мне кажетсаето самый подходящый вареант

Автор: Denny 20.12.2005, 08:27
Цитата

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


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

Автор: Gold Dragon 20.12.2005, 10:20
и меня заодно научите smile

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

Как паутина

Автор: Alx 20.12.2005, 16:21
як можливо маiть богато предков?


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

Автор: Хоббит 21.12.2005, 10:25
Цитата(Diesel @ 20.12.2005, 00:17)
можно попробувать создать граф, апотом искать самый походящый путь.
мне кажетсаето самый подходящый вареант

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

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

Автор: sergejzr 4.1.2006, 00:06
Цитата(Temp @ 18.12.2005, 16:45)
такого алгаритма наверное нет, только перебором,
хотя учитывая кол-во слов в базе это жулкий цикл.

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

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

Автор: Illuminaty 4.1.2006, 12:19
Можно свести задачу к следующей.
Есть 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]}
Полученная матрица описывает орграф. Таким образом решением задачи будет максимальный эйлеров контур в этом орграфе + (возможно) две дуги. Одна входящая в эйлеров контур (начальное слово из условия задачи) и одна исходящая (конечное слово). Естественно, что таких дополнительных дуг может и не быть или может быть одна.
Нахождение такого эйлерова контура гораздо менее трудоемкая операция чем полный перебор.

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

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

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

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

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

Автор: esperant0 6.1.2006, 21:19
это задача класса P Space поэтому полный перебор

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)