Форум: "Прочее";
Текущий архив: 2006.12.10;
Скачать: [xml.tar.bz2];
ВнизПомогите решить задачу! Найти похожие ветки
← →
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]) - и всё просто.
обычная лаба, в крайнем случае - курсовик на поиск с возвратом.
← →
Курдль © (2006-11-22 15:41) [6]
> Anatoly Podgoretsky © (22.11.06 14:36) [3]
> колбаса это не слово, а еда.
- Чувак! Это курица!
- Да с какого это курица?!
- Я грю - ку-ри-ца!
- Иди ты! Это жрёцца, а не курицца!
← →
Vlad433 © (2006-11-22 18:18) [7]Например:
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;
← →
Плохиш © (2006-11-22 18:31) [8]
> в крайнем случае - курсовик на поиск с возвратом.
В детском саду стали курсовики делать? 8-0
Страницы: 1 вся ветка
Форум: "Прочее";
Текущий архив: 2006.12.10;
Скачать: [xml.tar.bz2];
Память: 0.46 MB
Время: 0.044 c