Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Динамическое програмирование. Подпалендром. [D7, WinXP]

Страницы: < 1 2 ... 5 6 7 8 9 10 11 12 13 14 >
rodion © (2010-05-07 07:30:00)
Палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Подпалиндромом данной строки называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом. Например, HELOLEH является подпалиндромом строки HTEOLFEOLEH. Напишите программу, находящую в данной строке подпалиндром максимальной длины.

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

program Project6;

{$APPTYPE CONSOLE}

uses
SysUtils;
var
Mat:array[1..100,1..100]of integer;
s:string;
s1:string;
i,j,n,d,j1,k,maxj,maxi:integer;

Function F(i, j : Integer) : Integer;
var Ch : Char; R1, R2 : Integer; k : byte;
begin
if Mat[i, j] = -1 then
BEGIN
k := j;
while s[i] <> s[k] do dec(k);
R1 := F(i + 1, j);
if i <> k then R2 := F(i + 1, k - 1) + 2 else R2 := 1;
if R1 > R2 then Mat[i, j] := R1 else Mat[i, j] := R2
END;
F := Mat[i, j]
end;

begin
try
{ TODO -oUser -cConsole Main : Insert code here }
except
on E:Exception do
Writeln(E.Classname, ': ', E.Message);
end;
readln(s);
for I:=1 to length(s) do
for j := 1 to length(s) do
if i=j then Mat[i,j]:=1
else if i>j then Mat[i,j]:=0
else mat[i,j]:=-1;
maxi:=0;maxj:=0;
for i:=1 to length(s) do
for j:=1 to length(s) do
begin
Mat[i,j]:=f(i,j);
if (j-i+1>maxj-maxi+1)and(j-i+1=Mat[i,j]) then
begin
maxi:=i;
maxj:=j;
end;
end;
writeln(maxj-maxi+1);
writeln(copy(s,maxi,maxj-maxi+1));
readln;
end.

Заранее спасибо!

xayam (2010-05-10 17:47:00) [201]

> KilkennyCat © (10.05.10 17:36) [77]
> но там гораздо уникальнее решения

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

> а в твоем случае достаточно сосчитать сколько каких букв

я подумаю, может быть можно приспособить [32] под вычеркивание, скорей всего это возможно.

KilkennyCat (2010-05-10 17:36:00) [202]
но там гораздо уникальнее решения, а в твоем случае достаточно сосчитать сколько каких букв.

xayam (2010-05-10 17:28:00) [203]

> KilkennyCat © (10.05.10 17:22) [75]
> не идущие подряд и порядок - это разные вещи.

ну может быть, но я могу и так и так трактовать

> во-вторых появляется множество решений, раз можно переставлять
> буквы.

Мы и первоисточники читаем.
http://comp-science.narod.ru/WebPage/lesson2.htm
Подпалиндром Палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Подпалиндромом данной строки называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом. Например, HELOLEH является подпалиндромом строки HTEOLFEOLEH. Напишите программу, находящую в данной строке подпалиндром максимальной длины. Формат входных данных Строка длиной не более 100 символов, состоящая из заглавных букв латинского алфавита. Формат выходных данных В первой строке вывести длину максимального подпалиндрома, а во второй строке сам максимальный подпалиндром. Если таких подпалиндромов несколько, то вывести любой из них.
А Вы нет? Тогда мы идем к Вам :)

KilkennyCat (2010-05-10 17:22:00) [204]

> xayam © (10.05.10 16:54) [69]
> а где в условии это вычеркивание упоминается? Написано -
> порядок не имеет значения.

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

xayam (2010-05-10 17:13:00) [205]

> Sha © (10.05.10 17:06) [73]
> > я бы два алгоритма преподу отнес
> И продемонстрировал, что не понимаешь условия задачи, которую
> решаешь 4 месяца?

4 месяца это конечно круто, справился примерно за 2 часа вместе с составлением алгоритма.

> В слове последовательность.
> Последовательность подразумевает важность сохранения порядка.
> Из вычеркивания следует сохранение порядка и наоборот.

ну да последовательность, при не подряд идущих символах - это крутая формулировка, по-моему неточность в задании.

Sha (2010-05-10 17:06:00) [206]
> xayam © (10.05.10 16:54) [69]
> а где в условии это вычеркивание упоминается?

В слове последовательность.
Последовательность подразумевает важность сохранения порядка.
Из вычеркивания следует сохранение порядка и наоборот.

> я бы два алгоритма преподу отнес

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

> Родион (10.05.10 16:54) [70]
> что делает IntToStr?

О существовании справки, которая вызывается по клавише F1 тебе известно?
читать пробовал?
что из прочитанного неясно?

ты хоть понял для чего матрица нужна?
чему равны ее элементы?
как по ним подстрока восстанавливается в списанном примере?
расскажи.

xayam (2010-05-10 17:02:00) [207]
или Sha проси, наверно и код набросает, раз столько знает :)

xayam (2010-05-10 17:00:00) [208]

> Родион (10.05.10 16:54) [70]
> кк.. ну что то же надо показать

как бы это... второй вариант алгоритма сам... Не?

xayam (2010-05-10 16:54:00) [209]

> Sha © (10.05.10 16:29) [66]

а где в условии это вычеркивание упоминается? Написано - порядок не имеет значения. Конечно, если методом вычеркивания, то алгоритм другой будет. Тут кажется неоднозначно условие задачи, поэтому я бы два алгоритма преподу отнес, а он сам пусть выбирает. Иначе может придраться.

> Родион (10.05.10 16:40) [67]
> что делает IntToStr?

ну как бы это... переводит целый тип в строковый :)

Родион (2010-05-10 16:54:00) [210]
кк.. ну что то же надо показать

Sha (2010-05-10 16:42:00) [211]
> Родион (10.05.10 16:40) [67]
> возьму код [32]

очень не советую

Родион (2010-05-10 16:40:00) [212]
ребят, завтра пойду пробовать сдавать. возьму код [32].

зы: что делает IntToStr?
зыы: не закрывайте тему плз

Sha (2010-05-10 16:29:00) [213]
Вот смотри берем HTEOLFEEOLEH вычеркиваем X X X X остается H E L EE LEH а как из HTEOLFEEOLEH получить H EOLETELOEH вычеркиванием?

xayam (2010-05-10 16:22:00) [214]

> Sha © (10.05.10 16:17) [63]
> > xayam ©
> > Если не согласен, то пиши входные данные, что выводит
> алгоритм и что должно быть на самом деле по-твоему
> Уже написал в [51].

ну так правильно выдает же, внимательно прочитай свое [51], буква "О" в исходной строке встречается два раза + центр T (без пары). Так и должно быть.

xayam (2010-05-10 16:19:00) [215]

> нахождение подпоследовательности- частный случай алгоритма [32]

конечно имеется ввиду подпоследовательности, являющейся палендромом

Sha (2010-05-10 16:17:00) [216]
>> Ключевое слово здесь подпоследовательность.

> xayam © (10.05.10 16:11) [62]
> такого слова в условии вообще нет

Подпоследовательность = последовательность символов из данной строки, не обязательно идущих подряд

> Если не согласен, то пиши входные данные, что выводит алгоритм и что должно быть на самом деле по-твоему

Уже написал в [51].

Если бы можно было пересталять символы,
задача элементарно решалась бы при помощи массива 256 счетчиков.

xayam (2010-05-10 16:11:00) [217]

> Ключевое слово здесь подпоследовательность.

такого слова в условии вообще нет. К тому же, если ты не заметил, нахождение подпоследовательности - частный случай алгоритма [32], поскольку при этом важен порядок символов, [32] же не зависит от порядка символов, поскольку ищутся только пары одинаковых символов, поэтому как бы ты не упорядочил символы - алгоритм будет работать. Если не согласен, то пиши входные данные, что выводит алгоритм и что должно быть на самом деле по-твоему. [51] правильно выводит, ошибки нет.

Sha (2010-05-10 16:04:00) [218]
> xayam © (10.05.10 15:56) [60]
> слушай мы щас вроде не про автора говорим

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

Ключевое слово здесь подпоследовательность.
Конечно, ответ может получаться любым способом,
но результат должен быть подпоследовательностью и палиндромом.

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

xayam (2010-05-10 15:56:00) [219]
слушай мы щас вроде не про автора говорим и его заморочки с скопипастенной функцией, у меня ее вообще в алгоритме нет. Даже нет двумерного массива 100х100 и он вроде бы тоже не обязателен в использовании, а только два массива в сумме 2х100 + несколько вспомогательных переменных, так что в памяти явно выигрывается [32], и в скорости по-моему претензий не должно быть со стороны препода, только [32] вряд ли является динамическим алгоритмом, хотя можно попытаться доказать обратное преподу, если он упрется, все таки полного перебора тоже нет, к тому же на строке до 100 символов летает.

Sha (2010-05-10 15:48:00) [220]
> xayam © (10.05.10 15:32) [57]

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

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

От автора требуется найти способ восстановить
подпоследовательность по той же матрице,
если он до сих по не догадался.

Страницы: < 1 2 ... 5 6 7 8 9 10 11 12 13 14 >

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »