Помогите решить задачу!

← →
Qwee (2006-11-22 14:16) [0]

Помогите решить задачу!
1. Дано множество слов S. Найти цепочку максимальной длины, состоящую из некоторого подмножества S (цепочкой называется последовательность слов s[1]...s[n], в которой последняя буква s[i] равна первой букве s[i+1] для i=1,...,n-1). Использовать перебор с возвратами.
Вход:
В текстовом файле INPUT.TXT записаны слова по одному в строке. Количество слов НЕ записано в файле, но не превосходит 100. Длины слов не превосходят 255 символов. Слова состоят только из маленьких латинских букв.
Выход:
В текстовый файл OUTPUT.TXT записать цепочку максимальной длины. Каждое слово вывести в отдельной строке.
Прмер входа:
prix
pentium
byte
comp
char
bic
Пример выхода:
bic
comp
prix

Вот схема. А как это реализовать! Прошу, помогите!

{ схема перебора с возвратом }

procedure backtracking(k: integer); { k - номер хода }
begin
{ запись варианта }

if { решение найдено } then
{ вывод решения }
else
{ перебор всех вариантов }
if { вариант подходит } then
backtracking(k+1); { рекурсивный вызов }

{ стирание варианта }
end;

begin
backtracking(1);
end.

← →
TUser © (2006-11-22 14:18) [1]

В общем случае задаче не имеет решения - может быть цикл, например
колбаса - ананас - свитч - человек

Поэтому максимальной длины - фиг

← →
Agent13 © (2006-11-22 14:23) [2]

> TUser © (22.11.06 14:18) [1]
> В общем случае задаче не имеет решения - может быть цикл,
> например
> колбаса - ананас - свитч - человек
>
> Поэтому максимальной длины - фиг

Телепатор подсказывает мне, что одно и то же слово несколько раз использовать нельзя :) А вообще, по формату задачи очень напоминает олимпиаду. В таком случае как минимум несколько десятков поучительных постов автору обеспечены :)

← →
Anatoly Podgoretsky © (2006-11-22 14:36) [3]

> Agent13 (22.11.2006 14:23:02) [2]

колбаса это не слово, а еда.
Ананас - лакомство

← →
Qwee (2006-11-22 15:08) [4]

Ну помогите!

← →
Слоник_ (2006-11-22 15:39) [5]

> очень напоминает олимпиаду

да брось, чуть уточнить задачу (TUser © (22.11.06 14:18) [1]) - и всё просто.
обычная лаба, в крайнем случае - курсовик на поиск с возвратом.

> Anatoly Podgoretsky © (22.11.06 14:36) [3]
> колбаса это не слово, а еда.

- Чувак! Это курица!
- Да с какого это курица?!
- Я грю - ку-ри-ца!
- Иди ты! Это жрёцца, а не курицца!

Например:

var s1,s2,s3:TStringlist; ms:set of kol; //в oncreate создаем 3 списка: s1:=tstringlist.Create; s2:=tstringlist.Create; s3:=tstringlist.Create; //По кнопке считаем procedure TForm1.Button1Click(Sender: TObject); var i:integer; begin s1.LoadFromFile("input.txt"); for i:=0 to s1.Count-1 do begin s2.Append(s1.strings[i]); SeekIt(ansilastchar(s1.strings[i])); end; memo1.Lines.AddStrings(s3); s3.SaveToFile("outfile.txt"); end; // рекурсивная процедура... procedure SeekIt(const lastchar:pchar); var i:integer; begin for i:=0 to s1.Count-1 do if (pchar(s1.Strings[i])[0]=lastchar) and (not (i in ms)) then begin include(ms,i); s2.Append(s1.strings[i]); SeekIt(ansilastchar(s1.strings[i])); end; if s2.Count>s3.Count then s3.Assign(s2); ms:=[];s2.Clear; end;

> в крайнем случае - курсовик на поиск с возвратом.

В детском саду стали курсовики делать? 8-0

Помогите решить задачу! Найти похожие ветки