Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Прочее";
Текущий архив: 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
2-1163939550
Yastreb
2006-11-19 15:32
2006.12.10
Canvas


2-1164101702
Cyrax
2006-11-21 12:35
2006.12.10
Объекты сигнального типа...


2-1164378916
Pauchok++
2006-11-24 17:35
2006.12.10
Преобразование типов


2-1164271342
kirillrepin
2006-11-23 11:42
2006.12.10
как в TreeView програмно сделать все узлы развернутыми


2-1164206856
KyRo
2006-11-22 17:47
2006.12.10
Не могу удалить директорию





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский