Rambler's Top100
"Knowledge itself is power"
F.Bacon
Поиск | Карта сайта | Помощь | О проекте | ТТХ  
 Круглый стол
  
Правила КС
>> Настройки

Фильтр вопросов
>> Новые вопросы
отслеживать по
>> Новые ответы

Избранное

Страница вопросов
Поиск по КС


Специальные проекты:
>> К л ю к в а
>> Г о л о в о л о м к и

Вопрос №

Задать вопрос
Off-topic вопросы

Помощь

 
 К н и г и
 
Книжная полка
 
 
Библиотека
 
  
  
 


Поиск
 
Поиск по КС
Поиск в статьях
Яndex© + Google©
Поиск книг

 
  
Тематический каталог
Все манускрипты

 
  
Карта VCL
ОШИБКИ
Сообщения системы

 
Форумы
 
Круглый стол
Новые вопросы

 
  
Базарная площадь
Городская площадь

 
   
С Л С

 
Летопись
 
Королевские Хроники
Рыцарский Зал
Глас народа!

 
  
ТТХ
Конкурсы
Королевская клюква

 
Разделы
 
Hello, World!
Лицей

Квинтана

 
  
Сокровищница
Подземелье Магов
Подводные камни
Свитки

 
  
Школа ОБЕРОНА

 
  
Арсенальная башня
Фолианты
Полигон

 
  
Книга Песка
Дальние земли

 
  
АРХИВЫ

 
 

Сейчас на сайте присутствуют:
 
  
 
Во Флориде и в Королевстве сейчас  20:17[Войти] | [Зарегистрироваться]
Ответ на вопрос № 58913

Головоломки и алгоритмические задачки | 28-01-2008 11:44
Вечер добрый. Вот столкнулся с задачкой, на уме вертятся несколько вариантов решения, но едвали они верны. Полный перебор - бред, количество проверок будет достигать заоблачных значений(при 6 словах получаем 6!=720, а при 20 - 20!=2432902008176640000),так что этот вариант отпадает, есть еще пара идей, однако не думаю, что и они верны.
Вот собственно сама задача:
    Ввести N слов и определить,  можно ли построить из них цепочку,  в
которой каждое последующее число начинается с той же буквы на которую
оканчивается  предыдущее.  Вывести  возможную  цепочку,  являющуюся
решением задачи. Если цепочки нет, вывести ответ "нет".
    Пример: количество слов - 6.
    Слова: ком арбуз лак маска лес ствол
    Ответ (выводится в строчку):
    лес, ствол, лак, ком, маска, арбуз.

[+] Добавить в избранные вопросы

Отслеживать ответы на этот вопрос по RSS

Ответы:


Уважаемые авторы вопросов! Большая просьба сообщить о результатах решения проблемы на этой странице.
Иначе, следящие за обсуждением, возможно имеющие аналогичные проблемы, не получают ясного представления об их решении. А авторы ответов не получают обратной связи. Что можно расценивать, как проявление неуважения к отвечающим от автора вопроса.

13-04-2009 08:51 | Комментарий к предыдущим ответам
ой.. да и сортировать не надо. вот попробуйте хотя бы с первым примером. там 6 слов.
2 массива:
К А Л М Л С
М З К А С Л
теперь соответствие:
К А Л М С Л
| | | | | |
К А Л М С З

значит цепочка начинается с буквы Л и заканчивается буквой З. строим

13-04-2009 08:44 | Комментарий к предыдущим ответам
а попробуйте без графов
составить просто 2 массива первых и последних букв, потом отсортировать и то что совпадает обнулить. а потом как то надо анализировать результат...

08-05-2008 09:32
после прочтения всех ваших советов и решений, я ушел читать статьи по поводам графов и т.п. сейчас я могу решить эту задачу. :)
если кому интересно то мне сильно помогла данная статья, метод очень прост.
http://fvn2009.narod.ru/Olympiads/Rules_Olympiads/Rules29.htm

14-04-2008 16:54 | Комментарий к предыдущим ответам
Еще вариант


  Type TSVec = array of String;
  ...

  procedure AddToSVec(s: String; var v: TSVec);
  // добавление строки в массив
    var n: Integer;
  begin
    n:= Length(v); SetLength(v,n+1); v[n]:= s;
  end;

  function CutOnWords(s: String): TSVec;
  // резка строки слов на массив слов
    var i,n: Integer; q: String;
  begin
    Result:= Nil; q:= ''; s:= s+' '; n:= Length(s);
    for i:= 1 to n do
    if s[i] = ' ' then
      begin
      if Trim(q) <> '' then AddToSVec(Trim(q),Result);
      q:='';
      end else q:= q+s[i];
  end;


  function Permatate(a: TSVec): boolean;
  // метод эффективных перестановок
  var i,j,n: Integer;
//-------------------------------------------------------
  function Compare(a,b: String): boolean;
  // сравнение слов
  begin
    Result:= (Length(a)>0) and (Length(b)>0) and (a[Length(a)] = b[1]);
  end;

  function IsChain: boolean;
  // массив - готовая цепочка?
    var i: Integer;
  begin
    Result:= true;
    for i:= 0 to n-2 do
    if not Compare(a[i],a[i+1]) then
      begin Result:= false; exit; end;
  end;

  procedure Permute(i,j: Integer);
  // перестановка 2-х элементов
    var s: String;
  begin
    if i<>j then
    begin s:= a[i]; a[i]:= a[j]; a[j]:= s; end;
  end;

  procedure Perm(m: Integer);
  // рекурсивная процедура перестановок строк в массиве
    var j: Integer;
  begin
    if Result then exit;
    Result:= false;
    for j:= m+1 to n-1 do
    if not Result then
      if Compare(a[m],a[j]) then
      begin
        Permute(j,m+1);
        Result:= IsChain;
        if (m<n-2) and not Result then Perm(m+1);
      end;
  end;
//-------------------------------------------------------
begin
  n:= Length(a); Result:= n<2;
  if Result then exit;
  for i:= 0 to n-1 do
  for j:= 0 to n-1 do
    if not Result then
    if i <> j then
      if Compare(a[i],a[j]) then
      begin
        if (n=2) and (i=1) and (j=0) then Permute(i,j) else
        begin Permute(i,0); Permute(j,1); end;
        Result:= IsChain;
        Perm(1);
        if Result then exit;
      end;
end;

  function SumWords(a: TSVec): String;
    var i: Integer;
  begin
    Result:='';
    for i:= 0 to Length(a)-1 do
    Result:= Result+' '+a[i];
  end;

procedure TForm1.Button2Click(Sender: TObject);
  var a: TSVec; s: String;
begin
  s:= ' олег анна  оля лес лос атолл болото село якоб гена ';
  a:= CutOnWords(s);
  if Permatate(a) then ShowMessage(SumWords(a)) else
  ShowMessage('Нет цепочки слов.');
  a:= Nil;
end;


14-04-2008 14:39 | Комментарий к предыдущим ответам

Type TSVec = array of String;
      TIVec = array of Integer;
...
procedure CopyIVec(var a,b: TIVec);
  var n: Integer;
begin
  n:= Length(a); SetLength(b,n);
  Move(a[0],b[0],n*SizeOf(Integer));
end;

function Compare(a,b: String): boolean;
begin
  Result:= (Length(a)>0) and (Length(b)>0) and (a[Length(a)] = b[1]);
end;

function ExistsInIVec(i: Integer; v: TIVec): boolean;
  var n,j: Integer;
begin
  Result:= false; n:= Length(v)-1;
  for j:= 0 to n do
  if v[j] = i then
    begin Result:= true; exit; end;
end;

procedure AddToIVec(j: Integer; var v: TIVec);
  var n: Integer;
begin
  n:= Length(v); SetLength(v,n+1); v[n]:= j;
end;

procedure AddToSVec(s: String; var v: TSVec);
  var n: Integer;
begin
  n:= Length(v); SetLength(v,n+1); v[n]:= s;
end;

function FindChain(a: TSVec; var b: TIVec): boolean;
var NeedRecurse: boolean; t: TIVec; n,i: Integer;
// ------------------------------------------------
procedure Recurse(s: String; t: TIVec);
  var j,k1,z: Integer; g: TIVec;
begin
  z:= Length(t);
  for j:= 0 to n-1 do
  if NeedRecurse then
    if (T[z-1]<>j) then
    if Compare(a[T[z-1]],a[j]) then
      if not ExistsInIVec(j,T) then
      begin
        CopyIVec(t,g);
        AddToIVec(j,g);
        k1:= z+1;
        if k1 = n then
        begin
          NeedRecurse:= false;
          CopyIVec(g,b);
        end;
        if NeedRecurse then Recurse(s+' '+a[j],g);
        g:= Nil;
      end;
end;
// ------------------------------------------------
begin
  NeedRecurse:= true; n:= Length(a); Result:= n<2;
  if not Result then
  begin
    for i:= 0 to n-1 do
    if NeedRecurse then
      begin
      t:= Nil;
      AddToIVec(i,t);
      Recurse(a[i]+' ',t);
      end;
    t:= Nil;
    Result:= not NeedRecurse;
  end;
end;

function CutOnWords(s: String): TSVec;
  var i,n: Integer; q: String;
begin
  Result:= Nil; q:= ''; s:= s+' '; n:= Length(s);
  for i:= 1 to n do
  if s[i] = ' ' then
    begin
    if Trim(q) <> '' then AddToSVec(Trim(q),Result);
    q:='';
    end else q:= q+s[i];
end;

function SumWords(a: TSVec; v: TIVec): String;
  var i: Integer;
begin
  Result:='';
  for i:= 0 to Length(a)-1 do
  Result:= Result+' '+a[v[i]];
end;

procedure TForm1.Button1Click(Sender: TObject);
  var a: TSVec; IndVec: TIVec; n,i: Integer; s: String;
begin
  s:= ' олег анна  оля лес лос атолл болото село якоб гена ';
  a:= CutOnWords(s);
  if FindChain(a,IndVec) then ShowMessage(SumWords(a,IndVec))
  else ShowMessage('Нет цепочки слов.');
  IndVec:= Nil; a:= Nil;
end;


21-03-2008 15:04 | Комментарий к предыдущим ответам
Если будет на выходных времи и не будет лень попробую накатать код. но не обещаю

21-03-2008 15:01 | Комментарий к предыдущим ответам
С п 8 не всё так просто. Это самое слабое место алгоритма.
Соображения следующие :
вопревых структура данных для вставки замкнутых графов должна бытьзакольцованым массивом.т.к. для его построения берется произвольный начальный элемент и мы не знаем с какого места вставлять его в результирующий граф. соответственно нужно реализовать сначала процедур поиска в таблице "вершины" точки входа(перебор всего замкнутого графа и далее (индексы массива вершин нужно адресовать на прямою вычисляя инедкс вершины исходя из перавой буквы) дале если  найдена первая попавшаяся вершина с непустым значением запоминаем ее и ищем в рез. графе элемент с первой буквой соотв. этой вершине. собсно туда и вставлять.
Я щас совсем нетрезв , мысли путаются, если будет не ясно в понед напишу еще раз.
Алгоритм не оптимален. но тут полно умных людей. мож кто оптимизирует.

21-03-2008 11:55 | Комментарий к предыдущим ответам
А алгоритм п8 поподробнее можно?

21-03-2008 11:19 | Комментарий к предыдущим ответам
Всем привет
вот собсно мои соображения по теме :
(повторю многое , что тут уже писали)
1.вводм массив структуры данных "Вершины" где содержатся номер(буква)он же индекс и и указатели на входящие и исходящие дуги, заполняем.
2.определяем начальную точку входа, если граф не замкнут, или выбираем произвольную
3.вводим два списка элементов : а)сам спсиок элементов графа и б)оставшиеся неиспользованые элементы
4.в цикле начинае с епрвого вставляем элементы в граф. точки выхода и вход выбираем почти произвольно. т.е. элементы повторно не используем. для этого и создавался список оставшихс элементов(вставленный элемент из него удаляем).
5. цикл обрывем если в текущем узле не осталось свободных точек выхода, которые ссылаются на свободную точку входа
6. на выходе у нас получился некий граф. если в списке неиспользованных элементоов что-то осталось, значит они представляют собой замкнутый граф, иначе мы построили всё что хотели.
7.проделывем с оставшимися элеменетами опреацию начиная с п.2
8 пытаемся всавить полученный из оставшихся элементов граф в результирующий граф , если не получилось, то имеет место быть 2 или более изолировынных графов. т.е. построение не возможно.
9.операцию п 6.повторяем пока не кончаться все элементы

сосственно все. нет никакой рекурсии и нет проблемы с элементами которые замкнуты на самих себя.

ЗЫ : думал всего пару часов над проблемой, по этому может я и ощибаюсь, чего-то не учел . прошу поправить если найдете изъяны.
ЗЗЫ : тему всю не читал, ибо лень. по этому ногами не бить, если повторил чёй-то алгоритм.

20-03-2008 06:23
Алгоритм примерно следующий:
1) Оцениваем каждое слово по принципу первая_буква*X*100+последняя_буква*X, где X = [2..N+1 слов]
2) Составляем N таблиц по N слов сгурппированных по X
3) Инвертируем матрицу (или как там еще)
4) Сортируем каждую таблицу
5) Ищем связность
Число переборов для пузырька будет (N^2)^2
Для QuickSort еще быстрее
Quick sort можно ускорить, если применять не 2 таблицы с половинным делением, а некоторое эвристически определенное число таблиц.

Извините, дальше лень думать, может ошибся :)

18-03-2008 08:14 | Комментарий к предыдущим ответам
Возможно поможет:
Есть такая теорема, точного условия не помню, но суть такова:
Если в графе для каждой вершины с ней смежно не менее N/2 (формулу точно не помню, N - кол-во вершин), то Эйлеров цикл можно искать следующим алгоритмом:
1. Начинаем откуда угодно.
2. Пока есть возможность добавить слово в конец -- добавляем.
3. Если этой возможности нет -- смотрим, можно ли что-то "воткнуть" в цепочку, втыкаем все возможные слова.
4. Если начало = конец то вуаля, иначе нашли просто Гамильтонов путь.

Грубо говоря, условие на кол-во смежных вершин, даёт нам гарантию, что на 3 шаге все вершины вставятся в цепочку.
Здесь как раз ситуация -- вершин не более 33, слов может быть много...

17-02-2008 19:26 | Комментарий к предыдущим ответам
Ещё элегантнее можно сделать если слова хранить в виде двумерном массиве так чтобы один из двух индексов слова в массиве одновременно являлся порядковым номером его последней буквы в алфавите, а оставшийся индекс был номером слова среди всех заканчивающихся на ту же букву. Это позволит вместо перебора перейти к прямой адресации, число циклов будет сокращено.

17-02-2008 18:57 | Комментарий к предыдущим ответам
Задача как обычно состоит в нахождении баланса между использованием процессора и памяти. Имхо:

0. Выбор стартового слова - по Эйлеру (этот шаг не обязателен, но без него число разветвлений на старте будет равно числу слов).

1. Нужно ввести дополнительный числовой массив с размерностью равной [1..3,1..N]
2. В массив [1,i] вносить число возможных разветвлений на каждом i-том шаге, в [2,i] номер текущего разветвления, в [3,i] индекс использованного слова.
3. если цепочка уперлась в тупик (нет подходящего слова), по массиву можно легко определить куда вернуться и какое слово выбрать следующим (хвост массива от этой точки перестраивается заново).
4. При исчерпании списка слов - стоп решение есть.
5. при исчерпании разветвлений - стоп решения нет.

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

Теперь тот же путь предстоит проделать компьютерам, но вот что они изобретут в конце - это вопрос :-).


09-02-2008 20:15 | Комментарий к предыдущим ответам
я могу выслать свое решение в личку (чтобы не портить удовольствия другим от создания собственного решения)

Не лешайте других удовольствия от поиска ошибок :)
Это определяется в момент, когда мы не можем найти очередного слова, хотя список еще не использованных слов не пуст.
В этот момент уже поздно. Связность графа можно нарушить выбирая очередное слово. Вы правильно обращаете внимание на слова, начинающиеся и заканчивающиеся на одну букву, но Geo уже писал, что это могут быть не только отдельные слова, но и цепочки и достаточно сложные конструкции.

09-02-2008 06:05 | Комментарий к предыдущим ответам
амфитеатр колокол радуга люк
Считайте входы-выходы ;-)

Проверил на своей прогремме, понял о чем речь. Прошу прощения. Пришлось дописать проверку еще одного условия. Теперь все работает.
Изменения:
условие, что вершин с кол-ом входящих и исходящих связей отличающихся на 1 не должно быть или их должно быть ровно 2-е: одна с одной лишней исходящей и одна с лишней входящей НЕОБХОДИМО (но не ДОСТАТОЧНО) для существования решения задачи
Но выполнения этого условия, говорит, что решение либо есть, либо цепочек несколько. Это определяется в момент, когда мы не можем найти очередного слова, хотя список еще не использованных слов не пуст. тут есть 2 варианта, либо сообщить что единой цепочки нет, либо вывести все не зависимые цепочки.
2Geo: я могу выслать свое решение в личку (чтобы не портить удовольствия другим от создания собственного решения)

09-02-2008 02:02 | Комментарий к предыдущим ответам
2All: прошу прощения за очепятки. Это мой бич. Я их замечаю когда уже поздно. :((

09-02-2008 01:58
Вы, видимо, недостаточно внимательно читали обсуждение. Я понимаю, конечно, что оно большое и не всегда по теме, но все же...
Как раз поэтому и решил написать, что прочитал всю переписку. И за час написал рабочий алгоритм, без перебора.
>>> условие, что вершин с кол-ом входящих и исходящих связей отличающихся на 1 не должно быть или их должно быть ровно 2-е: одна с одной лишней исходящей и одна с лишней входящей НЕОБХОДИМО и ДОСТАТОЧНО для решения задачи

амфитеатр колокол радуга люк

Считайте входы-выходы ;-)

Просто я это написал для того чтобы отбросить сомнения, что перебор не нужен (были сомнения в Вашем посте от 30-01-2008 15:47)
>>> Чтобы не было проблемы с "баобаб", при работе надо первым делом клеить такие слова (начинающиеся и заканчивающиеся на одинаковые буквы)
Баобаб был взять для наглядности. Его вполне можно заменить на

барьер рокот трюк корпус сугроб

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

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

08-02-2008 14:39 | Комментарий к предыдущим ответам
to Миша Басов:
Вы, видимо, недостаточно внимательно читали обсуждение. Я понимаю, конечно, что оно большое и не всегда по теме, но все же...

>>> условие, что вершин с кол-ом входящих и исходящих связей отличающихся на 1 не должно быть или их должно быть ровно 2-е: одна с одной лишней исходящей и одна с лишней входящей НЕОБХОДИМО и ДОСТАТОЧНО для решения задачи

амфитеатр колокол радуга люк

Считайте входы-выходы ;-)

>>> Чтобы не было проблемы с "баобаб", при работе надо первым делом клеить такие слова (начинающиеся и заканчивающиеся на одинаковые буквы)
Баобаб был взять для наглядности. Его вполне можно заменить на

барьер рокот трюк корпус сугроб

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

08-02-2008 14:05 | Комментарий к предыдущим ответам
Ну что вы паритесь. Уже несколько раз было преведено решение, никаких переборов. Скорость работы алгоритма очень мала(основное время поиск слов в списке по критерию (начинается заканчивается на ...). Тут простор для оптимизации: хеши, сортировки и т.д. Актуально для тысч слов. Для наших задачь достаточно TStringList). Ресурсы только на хранение списка слов+массив (33х33) of integer - для хранения данных о графах+массив(33) record (2хInteger)+рабочие переменные, короче ерунда.
Небольшое дополнение:
1) условие, что вершин с кол-ом входящих и исходящих связей отличающихся на 1 не должно быть или их должно быть ровно 2-е: одна с одной лишней исходящей и одна с лишней входящей НЕОБХОДИМО и ДОСТАТОЧНО для решения задачи.
2) При наличии 2=х особых вершин, одной мы начинаем, другой заканчиваем.
3) Чтобы не было проблемы с "баобаб", при работе надо первым делом клеить такие слова (начинающиеся и заканчивающиеся на одинаковые буквы).

Суть алгоритма:
1) заполняем массив графов (Inc(Grafs[Word[i]First,Word[i]Last])
2) Пробегаемся по массиву и считаем кол-во входящих и кол-во исходящих связей для каждой вершины (33 рекорда по 2 integer (In,Out))
3) Если есть вершина с abs(In-Out)>1>0 then Решения нет
4) Если вершин с In-Out=1>1 then Решения нет
5) Если вершин с In-Out=-1>1 then Решения нет
6) Если вершин с (In-Out=1=1)и(In-Out=-1<>1) then Решения нет
7) Если вершин с In-Out=-1=1 then
  Начать со слова начинающегося на эту букву (слова "баобаб" имеют приоритет)
  Закончить словом заканчивающимся на вершину с In-Out=1 (слова "баобаб" имеют приоритет)
8) Клеить по одному слову, пока они не кончатся (слова "баобаб" имеют приоритет).
9) Приклеить последнее слово (если оно не пусто)
10) Вывести результат.

С уважением Михаил Басов ака Quazi.

2Geo: >>> <...> ибо таких как Geo осталось мало <...>
Спасибо, конечно, за комплимент, но нас еще много ;-)

Все дело в том, что сейчас люди именно программисты. Я бы даже сказал инженеры-программисты. Которые великолепно знают железо, операционную систему и особенности языков программирования. А из нас готовили совсем не программситов. Программирование это так... между делом. Готовили именно научных работников, закладывая прочную базу по математике и физике. Так что это не Ваша вина, а поворот нашей системы образования.

Полностью согласен. Принцип непрерывного образования СССР - мечта всей Европы. Тока власть-придержащие этого пока не понимают... Прошу прощения за off-topic, наболело...

08-02-2008 08:27 | Комментарий к предыдущим ответам
Как правильно заметили, вершин всего 33.
Это повод всю задачу решить графически.
Тут мы обращаемся не к классикам, а к древним грекам :)

Если мы не "Войну и мир" в цепочку выстраиваем :)
Можно программку наваять для этого.
С передачей маркера, если наглядности недостаточно.
И связность графа проверяется на раз.

Вот тут замечание о том, что сложность это количество колец
получит свою иллюстрацию.

06-02-2008 07:15 | Комментарий к предыдущим ответам
не суть, я просто показал пример, чтоб меня поняли.

05-02-2008 19:18
Я бы сразу добавил
list = record
  info: string;
  first:char;
  last:char;
  next: TList;
end;
чтобы каждый раз не искать в строке первую и последнюю букву.

05-02-2008 07:18 | Комментарий к предыдущим ответам
>>> надеюсь меня поняли
Поняли, поняли. Я этих списков за свою жизнь много сделал, так что понимаю, о чем идет речь.

05-02-2008 07:16 | Комментарий к предыдущим ответам
>>> изначально, мне нужно на Паскале
Значит использование "родных" динамических массивов отменяется. Хотя, помнится, я на Delphi 1 создавал класс, который предоставляет ту же функциональность, что и динамический массив. Что-то похожее можно сваять и на Turbo Pascal 6 или 7.

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

А спорить и продолжать думать -- на эрто уже Сергей Перовский ответил.

05-02-2008 07:14 | Комментарий к предыдущим ответам
еще раз о списках, я не имею ввиду TStrings, я о списках в другом смысле, это что-то вроде дерева, это массив произвольной длинны
TList = ^list;
list = record
  info: string;
  next: TList;
end;

надеюсь меня поняли, хотя в этом глубоко сомневаюсь, зная как ужасно объяснил.

05-02-2008 07:08 | Комментарий к предыдущим ответам
to Geo
изначально, мне нужно на Паскале, другое дело, что языки похожи, но, как видишь, не до конца.
Никаких игр мне не надо, просто я и впрямь не могу понять, зачем спорить, продолжать думать как решить задачу, когда перед тобой стоит готовый код, который можно только опровергнуть, принять или прокоментировать.
Списки не в том плане что ты подумал, это что-то вроде двоичного дерева, только одноричного, или как еще сказать...А может просто я тебя не понял.
Делфи это хорошо, но все же именно эта задача мне позарез как нужна на Паскале.

04-02-2008 13:52
вариант массив вершин и массив ребер мне не нравится, тк. в паскале нельзя устанавливать длину массива
В стандартном Паскале нельзя, а в Дельфи можно.
Что касается вершин, то их всего 33 (если слова только из русского языка), да и из них не все будут задействованы.
А для слов в Дельфи существуют наследники TStrings.
Так что, если списки не нравятся можно без них в данном случае обойтись. Вот только разобраться с ними рано или поздно придется.

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

04-02-2008 13:37 | Комментарий к предыдущим ответам
>>> вот вас унесло, здесь уже был дан работающий код, при помощи рекурисии, и впрямь, как автомат.
Э-э-э... И что? Берите готовый работающий код и дайте нам поиграться в свои игры ;-)

>>> в паскале нельзя устанавливать длину массива
Это кто Вам такое сказал? Вам наврали. Или это... в Паскале, может быть. и нельзя, но в Delphi начиная... э-э-э... точное не скажу, в первой версии еще нет, а в шестой уже есть динамические массивы ;-)

>>> потому хочу сделать списки
А какие именно списки? Честные списки состоящие из с записей с указателями, или через класс TList? Если через TList, то посмотрите в исходниках VCL реализацию и увидите, что они сделаны именно через динамические массивы.


04-02-2008 12:12 | Комментарий к предыдущим ответам
нда... вот вас унесло, здесь уже был дан работающий код, при помощи рекурисии, и впрямь, как автомат. Вы тут бьетесь над решением и тонкостями, пока я тупо пытаюсь построить граф, собственно, вариант массив вершин и массив ребер мне не нравится, тк. в паскале нельзя устанавливать длину массива, потому хочу сделать списки, что сильно усложнит мне жизнь.

04-02-2008 09:51 | Комментарий к предыдущим ответам
Хм... А у меня в голове вертится некая "матрица достижимости" вершин. Матрица, в которой каким-то образом фиксируется количество способов достижения одной вершины из другой. Каждый раз при включении нового слова в цепочку мы корректируем эту матрицу, выбрасывая из графа пройденный путь. Соответственно, перед тем, как добавить слово в цепочку, нужно проверить, не возникнет ли при этом недостижимость определенных вершин. И если возникнет, то сначала нужно обойти их.

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

04-02-2008 09:37 | Комментарий к предыдущим ответам
На базарной площади в обсуждении смешалось понятие графа и дерева.
Подумалось, нельзя ли использовать в этой задаче скелетное дерево графа?
Правда не очень ясно, как его строить для орграфа.

03-02-2008 16:11
Любопытная ссылка по теме:
http://www.5ballov.ru/referats/preview/24366/7

03-02-2008 16:09
Для проверки на связность ничего не приходит в голову кроме аналога волнового алгоритма.

03-02-2008 15:45 | Комментарий к предыдущим ответам
В общем, у меня есть подозрение, что основной "рабочей лошадкой" все же окажется рекурсия. Естественно, мы упростим перебор. Для упрощения уже есть следующие кандидаты:
1. Сразу определяем невозможность солставления цепочки, если не выполняется условие Эйлера.
2. Сразу определяем начальную и конечную вершины, если они однозначно определяются из условия Эйлера.
3. Схлопываем однозначные цепочки (когда какая либо буква встречается только один раз).

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

03-02-2008 13:56 | Комментарий к предыдущим ответам
да, да, я все это понимаю, только с некоторым опозданием...

02-02-2008 19:25
так или иначе ответ будет.Хотя это не гарантирует, что я прав

К сожалению это не гарантирует, что ответ будет :)
Geo уже писал:
Если мы с апломба перескочим сразу на брежнева, то к баобабу уже не попадем :(

02-02-2008 08:04 | Комментарий к предыдущим ответам
to  schurik
как по мне плохой вариант, это довольно громоздко и не практично, теперь, когда я понял суть графов, мне это кажеться немного не правильным, ведь если существует эйлеров путь (а это легко проверить), то начинаем с той вершины где выходов больше, чем входов, дальше идем только по по ребрам, так сказать "по течению" и так или иначе ответ будет, нас же не просят все цепочки, вот и не важно куда заверну, я проверял...
Хотя это не гарантирует, что я прав

02-02-2008 07:59 | Сообщение от автора вопроса
По-тихоньку продвигается, полностью разобрался с динамическими переменными, построил пару списков для практики, теперь занимаюсь построением графа. Суть решения уловил, все просто, в задаче труднее всего построить граф. Всем огромное спасибо.

31-01-2008 05:39 | Комментарий к предыдущим ответам
А не пора ли перейти в рассуждениях от цепочек слов к цепочкам символьных пар.

31-01-2008 05:22
цепочку с одинаковым началом и концом наоборот легко вставить в уже имеющуюся цепочку.
Во первых я имел в виду не любые цепочки, а однозначные.
Во вторых хотел обратить внимание как раз на то, что ее легко НЕ вставить.
При прохождении через букву, для которой есть подобные цепочки, их необходимо включать в первую очередь, иначе можно к ним уже не вернуться.

31-01-2008 04:38 | Комментарий к предыдущим ответам
Во первых нужно сократить перебор, убрав вершины с одним входом и одним выходом - "склеим" такие пары слов в цепочки.
Тогда подозрительными на отпадение будут цепочки начинающиеся и заканчивающиеся одинаково, как баобаб в приведенном примере.
Впрочем, доказать пока не могу.


я этот случай уже описывал:
29-01-2008 08:51
В общем можно построить из моих выдуманных слов не 1 цепочку а цепочки 4(ну или уж сколько получится). причем цепочку можно оставлять в покое, если первая и последняя буквы цепочки совпадают, и пробовать строить следующую цепочку. Когда слова закончатся то нужно брать цепочки по очереди и вставлять их в друг друга.


цепочку с одинаковым началом и концом наоборот легко вставить в уже имеющуюся цепочку. ТОлько нужно, чтобы выполнилось условие:
2 цепочки можно склеить если у них есть одинаковые буквы(начала или конца любого слова входящего в цепочку)

Пример:
апломб баобаб брежнев ворог

если 1 цепочка: апломб брежнев ворог
вторая: баобаб

то вторую цепочку легко вклеить в первую.


Я думаю можно из имеющихся слов составить определенное количество цепочек и потом их склеивать.

30-01-2008 20:24
Неужели действительно придется все рекурсивно перебирать?! :(
Во первых нужно сократить перебор, убрав вершины с одним входом и одним выходом - "склеим" такие пары слов в цепочки.
Тогда подозрительными на отпадение будут цепочки начинающиеся и заканчивающиеся одинаково, как баобаб в приведенном примере.
Впрочем, доказать пока не могу.

30-01-2008 15:47 | Комментарий к предыдущим ответам
Помедитировал. Стало грустно...

Пусть у нас есть такая цепочка

апломб баобаб брежнев ворог

Если мы с апломба перескочим сразу на брежнева, то к баобабу уже не попадем :(

Неужели действительно придется все рекурсивно перебирать?! :(

30-01-2008 14:20 | Комментарий к предыдущим ответам
>>> А что, если в цепочке есть основная, и вторая, которая замкнута на себе
Прблема эта озвучивалась, Вы просто не поняли некоторых сообщений, так как это было сказано в терминах теории графов, используя термин связность. Связный или односвязный граф -- это такой граф, в котором, перемещаясь по дугам, можно попасть из любой вершины в любую вершину. Не строго, но, думаю, понятно.

Озвучил проблему сергей перовский в сообщении от 29-01-2008 12:11

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

*ушел медитировать*

30-01-2008 13:47 | Комментарий к предыдущим ответам
А проверка на связность оказалась критически важной: легко показать, что включение в цепочку любого слова преращает "правильный" набор слов в новый "правильный". Значит при выборе очередного слова придется проверять, не нарушится ли связность графа.
И как это эффективно сделать?

30-01-2008 12:03 | Комментарий к предыдущим ответам
я уже совсем во всем запутался. у меня одни цепочки идут другие нет, и не должны. не знаю. буду решать своими силами, не заглядывая сюда, я только путаюсь. как решу, прийду. а калашников то не подводит, все таки, вот только исскуственный интелект мыши совсем уже в горле застрял, наверное новую прийдется брать.

30-01-2008 11:43 | Комментарий к предыдущим ответам
и калашников подводит

30-01-2008 11:42 | Комментарий к предыдущим ответам
to DRoник
решено не верно, из этого цепь составить не может
лес
лос
село
олег
оля
ялоп
поло

хотя она есть
лес
лос
село
оля
ялоп
поло
олег

30-01-2008 11:30 | Комментарий к предыдущим ответам
Кстати, по-моему, в способе проверки наличия эйлерова пути есть недочет. А что, если в цепочке есть основная, и вторая, которая замкнута на себе, тогда подсчет кол-ва входящих и исходящих не подойдет. Например:
лес, ствол, лак,    Москва, Амстердам

30-01-2008 11:22 | Комментарий к предыдущим ответам
нда..
Похоже эта задача уже начала разветвлятся, и вы, невыдерживая моего отсутствия, потихоньку начали даже код писать. Плохо только то, что я появляюсь по вечерам, а вы по утрам. Продолжаю работу над решением. Дело в том, что вчера я доучивал работу с динамическими переменными, решение идет туго, просто весь этот матерьял абсолютно нов. Но от того даже интересней. Большое всем спасибо.

30-01-2008 08:26 | Комментарий к предыдущим ответам
>>> мы говорим об одном и том же но разными словами:)
А я как бы не особо и возражал

Как я понял, спор сейчас идет по двум возможным направлениям

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

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

Маленький пример, иллюстрирующий мой подход ко воторому пункту (в частности, ответ  DROнику на "само решение так не получишь"). Понимаю, что это не доказательство, но как пример вполне годится.

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

абак артишок абрек кобра калитка краска

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

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

P.S. Не стоит забывать о том, что связность возможна не всегда.

30-01-2008 06:54 | Комментарий к предыдущим ответам
Geo
Если бы в цепочке первая буква первого слова отличалась от последней буквы последнего слова, то количество слов, начинающихся с первой буквы, было бы на единицу больше, чем количество слов, заканчивающихся на нее. А количество слов, заканчивающихся на последнюю букву, было бы на единицу больше, чем количество слов, начинающихся с этой буквы.


Schurik
29-01-2008 04:30
В итоге начинаем цепочку со слова, которое начинается на ту букву,которая у нас осталась в первом массиве, и заканчиавем цепочку тем словом, у которого последняя буква совпадает с оставшейся во 2 массиве.


мы говорим об одном и том же но разными словами:)


Можете пересчитать в своем наборе до и после добавления в него слова "артишок".


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


30-01-2008 05:35 | Комментарий к предыдущим ответам
>>> в моем примере начальная и конечная буквы совпадают, поэтому там практически любое слово можно всунуть.
Именно поэтому я и сказал, что Вы подобрали себе удачный пример.

>>> но это нелепая случайность:))
Это не случайность. Это условие, которое в моем описании следует за номером 2: для каждой буквы, количество слов, которые начинаются с этой буквы, и которые заканчиваются на эту букву, одинаково. Если бы в цепочке первая буква первого слова отличалась от последней буквы последнего слова, то количество слов, начинающихся с первой буквы, было бы на единицу больше, чем количество слов, заканчивающихся на нее. А количество слов, заканчивающихся на последнюю букву, было бы на единицу больше, чем количество слов, начинающихся с этой буквы. Можете пересчитать в своем наборе до и после добавления в него слова "артишок".

* * *
>>> Подсчетом букв мне кажется можно только проверить на да/нет. само решение так не получишь
Хм... Видимо, пока я код не напишу, мне не поверят ;-)

30-01-2008 04:18 | Комментарий к предыдущим ответам
Рекурсивное решение надежно как автомат калашникова:)


function WordsInLine(Words: TStrings): string;
type
PWord = ^TWord;
TWord = record
  ind: integer; //индекс в Words
  used: boolean;
  conti: array of PWord; //продолжения
end;
var
Graph: array of TWord; //граф
Solution: array of integer; //решение
function Check(left,right: integer): boolean;
begin
result:= Words[ left ][length(Words[ left ])]=Words[ right ][1];
end;
procedure MakeGraph;
var
i,j: integer;
begin
SetLength(Graph,Words.Count);
SetLength(Solution,Words.Count);
//поиск связей
for i:= 0 to Words.Count-1 do begin
  Graph[i].ind:= i;
  Graph[i].used:= false;
  for j:= 0 to Words.Count-1 do
  if i<>j then
    if Check(i,j) then begin
    SetLength(Graph[i].conti,High(Graph[i].conti)+2);
    Graph[i].conti[High(Graph[i].conti)]:= @Graph[j];
    end;
end;
end;
function Step(cur: PWord; N: integer): boolean;
var
i: integer;
begin
cur.used:= true; //блокируем это слово
Solution[N]:= cur.ind; //запоминаем решение
if N=Words.Count-1 then begin
  //конец
  result:= true;
  exit;
end;
result:= false;
for i:= 0 to High(cur.conti) do
if not cur.conti[i].used then begin
  result:= Step(cur.conti[i],N+1);
  if result then exit;//конец
end;
cur.used:= false; //разблокируем
end;
var
i,j: integer;
begin
MakeGraph;
for i:= 0 to Words.Count-1 do
  if Step(@Graph[i],0) then begin
  result:= '';
  for j:= 0 to Words.Count-1 do
    result:= result+Words[Solution[j]]+', ';
    delete(result,length(result)-1,2);
  exit;
  end;
result:= 'нет';
end;



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

30-01-2008 04:18 | Комментарий к предыдущим ответам
Неужели?! ;-)
действительно можно:) в моем примере начальная и конечная буквы совпадают, поэтому там практически любое слово можно всунуть. но это нелепая случайность:))


30-01-2008 03:01 | Комментарий к предыдущим ответам
>>> добавив это слово Вы как раз и выполните условие, при котором цепочку построить нельзя:)
Неужели?! ;-)

ананас сироп перец цветок козел лес ствол лак ком маска анод дерево огород дом молоток корова анаконда арбуз зона артишок

В общем, Сергей Перовский в терминах графов уже все озвучил. В терминах данной задачи будет примерно такой алгоритм:

1. Для каждой буквы подсчитать сколько слов начинается на эту букву и сколько слов заканичвается на эту букву (буквы, на которые слова не начинаются и не заканчиваются отбрасываем).

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

3. Если для одной из букв слов, начинающихся с этой буквы, на единицу больше, чем слов заканичвающихся на эту букву (начальная вершина), а для другой буквы слов, заканичвающихся на эту букву на единицу больше, чем слов, начинающихся на эту букву (конечная вершина), то начинать нужно с любого слова начальной вершины, а зваершать -- любым словом конечной вершины. В процессе подбора очередного слова следить нужно только за тем, чтобы не попасть в конечную вершину раньше времени: то есть она должна быть последней. Что-то плохо получается словами, попробую на примере (на том же самом):
У нас начальной буквой должна быть "а", а конечной "к" (желающие могут посчитать сами). Пусть в какой-то момент временимы имеем следующую цепочку:

ананас сироп перец цветок козел лес ствол лак ком маска

Можно ли дальше вставить "артишок"? Смотрим сколько у нас осталось неиспользованных слов, начинающихся и заканчивающихся на букву "к": молоток, артишок, корова. То есть продолжит словом "артишок" можно, так как у нас есть продолжение по слову "корова". А если у нас цепочка более длинная:

ананас сироп перец цветок козел лес ствол лак ком маска анод дерево огород дом молоток корова

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

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

4. Если не выполняется ни условие 2, ни условие 3, то построить цепочку нельзя.

Все.

P.S. Рекурсия не нужна ;-)

30-01-2008 01:06 | Комментарий к предыдущим ответам
to Schurik:
Хороший Вы себе набор слов подобрали. Удобный ;-)

А если я к Вам в набор еще добавлю артишок, то построите цепочку? :D


Хмм, ну добавив это слово Вы как раз и выполните условие, при котором цепочку построить нельзя:)

Мой теска прав, хотя частично, его метод подходить, но только для определения существования цепочки. Объясню, он не учитывает возможность развилки, в примере данном мной все однозначно, а если на одну букву начинаются 2 или 3 слова,притом заканчиваются на разные?
Ну этот вариант я вроде тоже рассмотрел во 2 примере с 20 словами.
строишь разные цепочки, а потом встраиваешь их друг в друга:)


необходимым и достаточным условием существования обхода СВЯЗНОГО ориентированного графа является условие равенства для каждой вершины (кроме быть может двух) количества входящих и исходящих дуг. Как и у Эйлера, две вершины могут быть особенными: у одной исходящих на 1 больше, у другой на 1 меньше. В этом случае однозначно определяется точка старта.
Ну так вроде с моим предложенным вариантом так и полйчается. ТОлько если перевести все на язык заданной задачи: условие равенства для каждой вершины - это и есть в примитивном случае совпадение букв(одной буквы из множества первых букв и одной буквы из множества последних букв: соответственно так называемая вершина будет иметь сетное колво входов и выходов) так называемые особенные вершины(т.е. после вычеркивания осталось по 1 букве то это и есть начало и конец).

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

29-01-2008 14:21 | Комментарий к предыдущим ответам
>>> Кто-то распостранил :)
Обскакали меня. Не удастся на этом получиить филдсовскую меадль ;-) Придется продолжать разработку быстрого алгоритма факторизации :D

>>> но суть понятна
Понятно, конечно, то суть понятна. Мознами шевельныть надо, но самую малость.

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

29-01-2008 12:11 | Комментарий к предыдущим ответам
Кто-то распостранил :)
К сожалению точной ссылки дать не могу, но суть понятна: необходимым и достаточным условием существования обхода СВЯЗНОГО ориентированного графа является условие равенства для каждой вершины (кроме быть может двух) количества входящих и исходящих дуг. Как и у Эйлера, две вершины могут быть особенными: у одной исходящих на 1 больше, у другой на 1 меньше. В этом случае однозначно определяется точка старта.
Как проще сделать проверку связности, с ходу не скажу.
Вот и еще головоломка.

29-01-2008 11:30 | Комментарий к предыдущим ответам
А вот и еще один математик зашел! ;-)

Сергей! А что, решение Эйлера кто-то уже распространил на ориентированные графы? Честно говоря, таких деталей уже не знаю, так что немного мозгами пошевелить придется. По крайней мере, мне ;-)

29-01-2008 11:26 | Комментарий к предыдущим ответам
Тут нет математической головоломки.
А вот программистская есть :)
Как наиболее просто реализовать алгоритм обхода?
Какие изменения нужно внести чтобы получить все возможные обходы?
Впрочем, вот маленькая математическая головоломка: сосчитать количество возможных обходов.

29-01-2008 11:17 | Комментарий к предыдущим ответам
>>> кстати, Geo, не стоило переводить задачу в головоломки, это классика, как задача о мостах :)
Во-первых, новое -- это хорошо забытое старое. Во-вторых, по сравнению с вопросами, почему неправильно работает свойство RecordCount или как сложить два элемента в массиве, данный вопрос -- просто шикарная головоломка, на которой отдыхаешь ;-)

>>> как прогнать по графу, узнать, можно ли пройти один раз или нет?
Не впадайте в крайности: компьютер с графами не работает, а работает с массивами и списками. Так что стройте себе структуру данных под задачу из того, что предлагает компьютер. Для этой задачи, скорее всего, удобным будет что-то типа массива записей или списка записей, или какой-то их комбинации.

29-01-2008 11:11 | Комментарий к предыдущим ответам
>>> если будут появлятся 2 одинаковых сообщения - я не виноват, мышка имеет исскуственный интелект
Ну, на это есть модераторская мышка, которая как раз и питается дублями сообщений ;-)

>>> <...> ибо таких как Geo осталось мало <...>
Спасибо, конечно, за комплимент, но нас еще много ;-)

Все дело в том, что сейчас люди именно программисты. Я бы даже сказал инженеры-программисты. Которые великолепно знают железо, операционную систему и особенности языков программирования. А из нас готовили совсем не программситов. Программирование это так... между делом. Готовили именно научных работников, закладывая прочную базу по математике и физике. Так что это не Ваша вина, а поворот нашей системы образования.

>>> Вчера весь вечер мучался
В общем, Вы особо глубоко в теорию графов не лезьте. Там все же без подготовки тяжеловато. Отталкивайитесь от решения Эйлера. То есть граф можно обойти (ну, или рисунок можно начертить одним росчерком), если количество вершин, в которые входит нечетное количество дуг (нечетных вершин), либо нет, либо ровно две. Если нечетных вершин нет, то можете начинать с любой вершины. Если нечетных вершин две, то начинать нужно с одной нечетной вершины, а заканчивать на другой. При любом другом количестве нечетных вершин соответстующий обход графа невозможен (кстати, насколько я помню, кенигсбергские мосты как раз обойти нельзя ;-)).

Если Вы это поймете... я бы даже сказал прочувствуете, то тогда Вы легко перейдете на свою задачу, сделав поправку на то, что в случае со словами Вы имеете ориентированны граф. То есть, если продолжить аналогию с мостами, то у Вас мосты с односторонним движением.

И рекурсия Вам не потребуется, хотя для определенного класса задач, это очень хороштй прием.

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

29-01-2008 10:59 | Комментарий к предыдущим ответам
кстати, у меня еще один вопрос, тогда как прогнать по графу, узнать, можно ли пройти один раз или нет?

29-01-2008 10:54 | Комментарий к предыдущим ответам
кстати, Geo, не стоило переводить задачу в головоломки, это классика, как задача о мостах :)

29-01-2008 10:47 | Комментарий к предыдущим ответам
P.S. если будут появлятся 2 одинаковых сообщения - я не виноват, мышка имеет исскуственный интелект.

29-01-2008 10:46 | Комментарий к предыдущим ответам
разумеется. Это я о кайфе. Да я думаю. Но против готового решения ничего не скажу. Не в том плане, что хочу проверится, посмотреть свои недоработки, мне важна скорость выполнения и ресурсы занимаемые программой.
Эх. Эта задача ударила по самым больным точкам, которые всегда старался избегать, видимо пришел и их черед. Динамические переменные и рекурсия. Я уже видел алгоритмы и возможности при использовании таких подходов, очень интересно, получаются деревья, если их так можно назвать.

29-01-2008 10:41 | Комментарий к предыдущим ответам
ДА, собсвенно, я сдесь, вы ведь не думаете, что здесь собрались один лишь монстры программирования и профи, профи, в том плане, что это их работа. Я учусь,о а значит этому посвящаю не все свое время, хотя большую его часть.
Полностью поддерживаю Geo, примерно на такой ответ я и расчитывал. Просто суть моя не решить конкретно эту задачу, а набраться опыта, тем более, что о графах я наслышан. Вчера весь вечер мучался. Как разобрался с задачей о мостах, перешел на теорию. Кошмар. Кстати, в последнее время я начал разочаровываться в программистах, ибо таких как Geo осталось мало, все знают языки, но не умеют думать и составлять алгоритмы. Однако, вернусь к задаче.
Мой теска прав, хотя частично, его метод подходить, но только для определения существования цепочки. Объясню, он не учитывает возможность развилки, в примере данном мной все однозначно, а если на одну букву начинаются 2 или 3 слова,притом заканчиваются на разные?
P.S. При этом лучше пользоваться не массивом, а множеством.

29-01-2008 10:41 | Вопрос к автору: запрос дополнительной информации
to Александр Сухинин:
Вы лучше черкните пару слов о том, стоит ли приводить решение, или Вы пока сами "погрызете" задачу с учетом сделанных наводок. А то, с одной стороны, хочется продемонстрировать мастерство и привести решение, а с другой, не хочется обламывать Вам кайф ;-)

29-01-2008 10:21
20!- это факториал 20, формула кол-ва перестановок. а 20!=1*2*3*4*5..*20
В калькуляторе есть такая возможность.

29-01-2008 09:06 | Комментарий к предыдущим ответам
to Schurik:
Хороший Вы себе набор слов подобрали. Удобный ;-)

А если я к Вам в набор еще добавлю артишок, то построите цепочку? :D

29-01-2008 08:51 | Комментарий к предыдущим ответам
некоторая неопределенность в описании.
ну это я давал возможность автору вопроса тоже немного подумать:)

ну и как дополнение к неопределенности описания:
попробовал только что с 20 словами.
Все как я и писал, только с маленькими поправками алгоритма решения. А впрочем Вы ведь и сами знаете, что алгоритм нуждается в доработке после тестирования программы(не всегда но частенько).
В общем можно построить из моих выдуманных слов не 1 цепочку а цепочки 4(ну или уж сколько получится). причем цепочку можно оставлять в покое, если первая и последняя буквы цепочки совпадают, и пробовать строить следующую цепочку. Когда слова закончатся то нужно брать цепочки по очереди и вставлять их в друг друга. Эхх сложно описывать:)
Вот слова:
Лес
Ствол
Лак
ком
маска
арбуз
зона
анаконда
ананас
сироп
перец
цветок
корова
анод
диод
дерево
огород
дом
молоток
козёл

всего 20 слов.

Вот пример составления цепочек:

1: лес ствол лак корова ананас сироп перец цветок козел
2: маска анод дом молоток ком
3: анаконда арбуз зона
4: дерево огород

Берем последнюю  и вставляем в 2 цепочку, получаем:

1: лес ствол лак корова ананас сироп перец цветок козел
2: маска анод дерево огород дом молоток ком
3: анаконда арбуз зона

Берем 3-ю и вставляем в первую

1: лес ствол лак корова анаконда арбуз зона ананас сироп перец цветок козел
2: маска анод дерево огород дом молоток ком

Берем 2 и опа, некуда вставлять, ну тогда мы ее повертим немного

1: лес ствол лак корова анаконда арбуз зона ананас сироп перец цветок козел
2: ком маска анод дерево огород дом молоток

и вот теперь все в порядке:

1: лес ствол лак  ком маска анод дерево огород дом молоток
корова анаконда арбуз зона ананас сироп перец цветок козел

Возможно еще есть неучтенные варианты:)
пишите слова, попробуем найти оптимальный ответ:)

Автор ты с нами еще?:)

С уважением Александр

29-01-2008 07:55 | Комментарий к предыдущим ответам
На мой скромный взгляд у Schurik'а учтено то, что он начинает не с первой буквы, так как цепочка может достраиваться не только вперед, но и назад. Но мне кажется (пардон, детальнее не анализировал), что реалитзовано только для некоего подмножества частных случаев. Плюс некоторая неопределенность в описании.
Ну или там проверки на другие цепочки из оставшихся слов:))
это уж нужно брать слова и сидеть и смотреть, изучать возможные варианты:))


P.S. Куда пропал автор вопроса? Изучает литературу по теории графов? ;-)

29-01-2008 07:43 | Комментарий к предыдущим ответам
Schurik:

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

Вам же объяснили, почему:  Может, надо было начинать не с первой буквы.

29-01-2008 07:00 | Комментарий к предыдущим ответам
Надеюсь, никто не против, что я перевел этот вопрос в разряд головоломок? Больно уж красивая задача. И есть где мозгами пошевелить.

29-01-2008 06:43 | Комментарий к предыдущим ответам
To AlexSku
Конечно, вывод неверный. Может, надо было начинать не с первой буквы.
очень легко сказать, что вывод неверный и промолчать. Если неверный то объясни почему.

29-01-2008 06:17
берем 1-ю букву первого массива и ...
В итоге если у нас осталось по 1 букве в каждом массиве то делаем вывод: цепочка есть, если же осталось больше одной булквы то цепочки нет:)

Конечно, вывод неверный. Может, надо было начинать не с первой буквы. Математику ещё никто не отменил (Geo, MBo)

29-01-2008 06:05
Schurik как раз дал способ обойти дуги
есть еще какой то на бумаге? :)

29-01-2008 06:03
Леонард Эйлер решал задачу, существует ли такой маршрут, чтобы обойти все кенигсбергские мосты, не проходя по одному и тому же мосту двжады. И он ее решил. Причем решение оказалось общезначимым, и сейчас оно известно всем, кто хотя бы более-менее занимается графами. Также его подход применим к такому классу задач, как рисование фигуры одной линией (не отрывая карандаша от бумаги и не проводя по одной линии дважды).

to MBo:
Респект за понимание. А то я уж начал бояться, что народ напрочь классику забыл, погрузившись в программирование.

И еще один респект за указание на ориентированность графа. Я как-то при беглом просмотре этот момент упустил (классический вариант задачи о мостах представляет собой неориентированный граф).

* * *
В общем, ничего пока подробно писать не буду. Дам возможность автору вопроса самому подумать (он еще не высказался). В остальном же... Конечно, современные компьютеры -- это здорово. Современные яхыки программирования -- это здорово. Современные конструкции, в которых реализованы какие-то сверхбыстрые сортировки на сверхбольших объемах данных -- это тоже здорово. Но класссика -- это всегда классика. Я ничуть не преувеличиваю, утверждая, что эта задача решается, например, для сотни слов безо всякого компьютера (только с карандашом и бумагой) за какой-нибудь час максимум. Представляете, для какого количества слов можно решить эту задачу, если задействовать компьютер ;-)

29-01-2008 05:06
Слова - дуги ориентированного графа (точнее, мультиграфа), а буквы, которые встречаются в начале и конце слов - его вершины.
Строится граф - каждое слово образует дугу от начальной буквы-вершины к конечной
Затем найти эйлеров путь в графе - это означает обойти все дуги графа по одному разу.
Вначале можно проверить, выполняются ли условия существования эйлерова пути.

Вот на это и дал прямую наводку Geo

29-01-2008 05:00
при вычеркивании из масива надо вносить в лог какие пары например mas1[1]+mas2[0] вычеркнули и условие, что мы не можем вычеркивать пары типа mas1[1] и mas2[1] по тому, что это одно слово а не два, по этому его нельзя соеденить с самим собой

29-01-2008 04:30
Незнаю, что за Кенигсбергские мосты, наверное что-то интересное, нужно будет почитать.:))
Я бы решил эту задачку так:
создаем 2 массива. В первый массив заносим все первые буквы слов, а во второй все последние буквы слов.
Потом берем 1-ю букву первого массива и сравниваем со 2 массивом, если такая буква встретилась,то вычеркиваем ее из первого и второго массива. и так далее...
В итоге если у нас осталось по 1 букве в каждом массиве то делаем вывод: цепочка есть, если же осталось больше одной булквы то цепочки нет:)
В итоге начинаем цепочку со слова, которое начинается на ту букву,которая у нас осталась в первом массиве, и заканчиавем цепочку тем словом, у которого последняя буква совпадает с оставшейся во 2 массиве.
хотя есть свои недостатки и нужно еще пару проверок сделать.

Первый массив: К А Л М Л С
Второй массив: М З К А С Л

оставшиеся буквы:
первый массив:Л
второй массив:З

Начинаем со слова на букву Л и заканчиваем на слове с буквой З.
Если начнем со слова ЛАК-КОМ-МАСКА-АРБУЗ, то оставшиеся слова добавляем слева в цепочку: Лес-Ствол-ЛАК-КОМ-МАСКА-АРБУЗ.

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

С уважением Александр

29-01-2008 04:23
хотел сказать брод

29-01-2008 04:22
Короче, не буду пудрить мозги. Смотрите решение Леонарда Эйлера для задачи о Кенигсбергских мостах. Если будет непонятно, пишите здесь. Уточню.

Способ же мой является универсальным, так как с его помощью в любом предложенном мне случае этого рода я тотчас могу решить, следует ли строить переход с помощью отдельных мостов или нет, и в первом случае [могу установить], каким образом этот переход следует осуществить.
почитал и не поял что таким образом решает Леонард Эйлер
мост есть мост, если нужна короткая дорога надо строить, иначе искать брад или на пароме-лодке :)

29-01-2008 02:51 | Комментарий к предыдущим ответам
>>> Встречный вопрос: чем 20! считал? :)
Я подозреваю, что обычным виндовским калькулятором в инженерном режиме ;-)

29-01-2008 02:44
Встречный вопрос: чем 20! считал? :)

28-01-2008 12:21
А как Вы задачу решаете? Прсото перебираете все перестановки и смотрите, получается цепочка или нет? ;-)

На самом деле, если немного подумать, то данная задача решается вообще без компьютера. Скажем, для сотни-другой слов я берусь найти решение только с карандашом и бумагой :D

Короче, не буду пудрить мозги. Смотрите решение Леонарда Эйлера для задачи о Кенигсбергских мостах. Если будет непонятно, пишите здесь. Уточню.

Добавьте свое cообщение

Вашe имя:  [Войти]
Ваш адрес (e-mail):На Королевстве все адреса защищаются от спам-роботов
контрольный вопрос:
"Мы с тобой одной крови — ты и я!". Чьи это заветные слова?
в качестве ответа на вопрос или загадку следует давать только одно слово в именительном падеже и именно в такой форме, как оно используется в оригинале.
Надоело отвечать на странные вопросы? Зарегистрируйтесь на сайте.
Тип сообщения:
Текст:
Жирный шрифт  Наклонный шрифт  Подчеркнутый шрифт  Выравнивание по центру  Список  Заголовок  Разделительная линия  Код  Маленький шрифт  Крупный шрифт  Цитирование блока текста  Строчное цитирование
  • вопрос Круглого стола № XXX

  • вопрос № YYY в тесте № XXX Рыцарской Квинтаны

  • сообщение № YYY в теме № XXX Базарной площади
  • обсуждение темы № YYY Базарной площади
  •  
     Правила оформления сообщений на Королевстве

    Страница избранных вопросов Круглого стола.
      
    Время на сайте: GMT минус 5 часов

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

    Web hosting for this web site provided by DotNetPark (ASP.NET, SharePoint, MS SQL hosting)  
    Software for IIS, Hyper-V, MS SQL. Tools for Windows server administrators. Server migration utilities  

     
    © При использовании любых материалов «Королевства Delphi» необходимо указывать источник информации. Перепечатка авторских статей возможна только при согласии всех авторов и администрации сайта.
    Все используемые на сайте торговые марки являются собственностью их производителей.

    Яндекс цитирования