Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 15.06.2007, 18:28   #1
katya_milovanova
 
Регистрация: 15.06.2007
Сообщений: 4
По умолчанию Помогите!

Помогите пожалуйста... Осталось одну задачу сдать а я не могу ее сделать Все экзамены автоматом а зачет не могу получить...

Подпалиндром
Палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Подпалиндромом данной строки называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом. Например, HELOLEH является подпалиндромом строки HTEOLFEOLEH. Напишите программу, находящую в данной строке подпалиндром максимальной длины.
Формат входных данных
Строка длиной не более 100 символов, состоящая из заглавных букв латинского алфавита.
Формат выходных данных
В первой строке вывести длину максимального подпалиндрома, а во второй строке сам максимальный подпалиндром. Если таких подпалиндромов несколько, то вывести любой из них.
katya_milovanova вне форума Ответить с цитированием
Старый 15.06.2007, 18:47   #2
S.W.A.T.
Пользователь
 
Регистрация: 13.06.2007
Сообщений: 20
По умолчанию

378710771 стучись
www.saprulez.ru - готовые программы, форум.
S.W.A.T. вне форума Ответить с цитированием
Старый 15.06.2007, 20:18   #3
Carbon
JAVA BEAN
Участник клуба
 
Аватар для Carbon
 
Регистрация: 22.04.2007
Сообщений: 1,329
По умолчанию

Цитата:
Все экзамены автоматом


Задача интересная (я уже знаю как решать), сейчас только от сегодняшнего экзамена очухаюсь.

ЗЫ: На каком языке надо? (Предполагаю, Паскаль)
Carbon вне форума Ответить с цитированием
Старый 15.06.2007, 21:02   #4
AVer
Андрей
Форумчанин
 
Аватар для AVer
 
Регистрация: 21.11.2006
Сообщений: 457
По умолчанию

Цитата:
Сообщение от Carbon Посмотреть сообщение


Задача интересная (я уже знаю как решать), сейчас только от сегодняшнего экзамена очухаюсь.

ЗЫ: На каком языке надо? (Предполагаю, Паскаль)
Большинство заданий на этм форуме (В данном разделе) даются на языке Delphi\Pascal. Если нет - указывается в задании.
ICQ: 5311314
[SIGPIC][/SIGPIC]
AVer вне форума Ответить с цитированием
Старый 15.06.2007, 21:14   #5
Carbon
JAVA BEAN
Участник клуба
 
Аватар для Carbon
 
Регистрация: 22.04.2007
Сообщений: 1,329
По умолчанию

Код:
const N=100;
      M=(N*(N+1)) div 2;

type Pair=record
       left,right,prev,count:integer;
     end;

var inp,outp:text;
    line,result:string;
    index:integer;
    list:array [1..M] of Pair;


procedure Find;
var i,j,k,len,item:integer;
begin
  len:=length(line);
  item:=1;
  for i:=1 to len do
    for j:=len downto i do
      if line[i]=line[j] then
      begin
        list[item].left:=i;
        list[item].right:=j;
        list[item].prev:=0;
        list[item].count:=0;
        for k:=1 to item-1 do
        begin
          if (list[k].right>list[item].right) and
             (list[k].left<list[item].left) and
             (list[k].count>=list[item].count) then
          begin
            list[item].prev:=k;
            list[item].count:=list[k].count+1;
            if list[item].count>list[index].count then
              index:=item
          end;
        end;
        item:=item+1
      end;
  i:=index;
  result:=line[list[i].left];
  if list[i].right>i then
    result:=result+line[list[i].left];
  while i>0 do
  begin
    i:=list[i].prev;
    if i>0 then
      result:=line[list[i].left]+result+line[list[i].left];
  end
end;

begin
  assign(inp,'input.txt');
  reset(inp);
  readln(inp,line);
  index:=1;
  Find;
  close(inp);
  assign(outp,'output.txt');
  rewrite(outp);
  writeln(outp,length(result));
  writeln(outp,result);
  close(outp);
end.
Я думаю, пояснения не нужны. При желании можно разобраться. Метод - динамическое программирование.
Предполагается, что данные считываются из файла input.txt и записываются в output.txt, input.txt существует и непуст.
Carbon вне форума Ответить с цитированием
Старый 15.06.2007, 22:53   #6
AVer
Андрей
Форумчанин
 
Аватар для AVer
 
Регистрация: 21.11.2006
Сообщений: 457
По умолчанию

Цитата:
Сообщение от Carbon Посмотреть сообщение

Я думаю, пояснения не нужны. При желании можно разобраться. Метод - динамическое программирование.
Предполагается, что данные считываются из файла input.txt и записываются в output.txt, input.txt существует и непуст.
Дело в том, что входные данные - строка. Выход - тоже. Конечно нет ничего страшного и все просто переписывается, но это не соответствие заданию.
ICQ: 5311314
[SIGPIC][/SIGPIC]
AVer вне форума Ответить с цитированием
Старый 16.06.2007, 02:57   #7
Carbon
JAVA BEAN
Участник клуба
 
Аватар для Carbon
 
Регистрация: 22.04.2007
Сообщений: 1,329
По умолчанию

Цитата:
Дело в том, что входные данные - строка. Выход - тоже. Конечно нет ничего страшного и все просто переписывается, но это не соответствие заданию.
Там не было написано, откуда считывается и куда записывается.
Выход - не только строка, а число и строка.
Carbon вне форума Ответить с цитированием
Старый 16.06.2007, 06:38   #8
katya_milovanova
 
Регистрация: 15.06.2007
Сообщений: 4
По умолчанию ---

Цитата:
Сообщение от Carbon Посмотреть сообщение


Задача интересная (я уже знаю как решать), сейчас только от сегодняшнего экзамена очухаюсь.

ЗЫ: На каком языке надо? (Предполагаю, Паскаль)
Паскаль нужно...
katya_milovanova вне форума Ответить с цитированием
Старый 16.06.2007, 07:19   #9
katya_milovanova
 
Регистрация: 15.06.2007
Сообщений: 4
По умолчанию

Цитата:
Сообщение от Carbon Посмотреть сообщение
Код:
const N=100;
      M=(N*(N+1)) div 2;
 
type Pair=record
       left,right,prev,count:integer;
     end;
 
var inp,outp:text;
    line,result:string;
    index:integer;
    list:array [1..M] of Pair;
 
 
procedure Find;
var i,j,k,len,item:integer;
begin
  len:=length(line);
  item:=1;
  for i:=1 to len do
    for j:=len downto i do
      if line[i]=line[j] then
      begin
        list[item].left:=i;
        list[item].right:=j;
        list[item].prev:=0;
        list[item].count:=0;
        for k:=1 to item-1 do
        begin
          if (list[k].right>list[item].right) and
             (list[k].left<list[item].left) and
             (list[k].count>=list[item].count) then
          begin
            list[item].prev:=k;
            list[item].count:=list[k].count+1;
            if list[item].count>list[index].count then
              index:=item
          end;
        end;
        item:=item+1
      end;
  i:=index;
  result:=line[list[i].left];
  if list[i].right>i then
    result:=result+line[list[i].left];
  while i>0 do
  begin
    i:=list[i].prev;
    if i>0 then
      result:=line[list[i].left]+result+line[list[i].left];
  end
end;
 
begin
  assign(inp,'input.txt');
  reset(inp);
  readln(inp,line);
  index:=1;
  Find;
  close(inp);
  assign(outp,'output.txt');
  rewrite(outp);
  writeln(outp,length(result));
  writeln(outp,result);
  close(outp);
end.
Я думаю, пояснения не нужны. При желании можно разобраться. Метод - динамическое программирование.
Предполагается, что данные считываются из файла input.txt и записываются в output.txt, input.txt существует и непуст.
Ничего не понятно, и действительно нужна строка.
katya_milovanova вне форума Ответить с цитированием
Старый 16.06.2007, 10:33   #10
Carbon
JAVA BEAN
Участник клуба
 
Аватар для Carbon
 
Регистрация: 22.04.2007
Сообщений: 1,329
По умолчанию

Всё по задаче. Возвращает количество символов и строку.
Если нужна консоль:

Код:
const N=100; //максимальное количество символов
      M=(N*(N+1)) div 2; //максимальное количество вариантов
                                 //расположений пары символов
 
{Структура Pair описывает расположение пары одинаковых символов:
левый, правый, индекс массива обрамляющей пары, максимальное
количество обрамляющих пар символов, включая текущую.}

type Pair=record
       left,right,prev,count:integer;
     end;
 
var
    line, //Вход
    result:string; //Выход
    index:integer; //Индекс массива, содержащего максимальное
                       //количество пар
    list:array [1..M] of Pair; //Список пар
 
 
procedure Find;
var i,j,k,len,item:integer;
begin
  len:=length(line); //Длина строки
  item:=1;             //Текущий индекс в списке
  for i:=1 to len do  //Пробегаемся по строке, определяя пары
    for j:=len downto i do
      if line[i]=line[j] then //Если найдена
      begin
        //Записываем её данные в массив
        list[item].left:=i;
        list[item].right:=j;
        list[item].prev:=0;
        list[item].count:=0;
        //Пробегаемся по списку пар
        for k:=1 to item-1 do
        begin
          //Если нашли обрамляющую пару и количество пар больше
          //максимального для данной пары, сохраняем ссылку на пару
          if (list[k].right>list[item].right) and
             (list[k].left<list[item].left) and
             (list[k].count>=list[item].count) then
          begin
            list[item].prev:=k; //Сохраняем ссылку
            list[item].count:=list[k].count+1; //Сохраняем количество
            //Если количество больше всех остальных
            if list[item].count>list[index].count then
              index:=item
          end;
        end;
        //Увеличиваем индекс для записи следующей пары
        item:=item+1
      end;
  //После того, как найден индекс пары с максимальным количеством
  //обрамляющих пар, проходим по цепочке через индекс prev
  i:=index;
  result:=line[list[i].left]; //Формируем строку
  if list[i].right>list[i].left then      //Если это не одиночный символ,
                                             //дублируем его
    result:=result+line[list[i].left];
  while i>0 do //Пока ссылка указывает на элемент массива
  begin
    i:=list[i].prev; //Индекс обрамляющей пары
    if i>0 then //Если он не 0, добавляем пару к результату
      result:=line[list[i].left]+result+line[list[i].left];
  end
end;
 
begin
  readln(line);          
  index:=1;
  Find;
  writeln(length(result));
  writeln(result);
end.
Carbon вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц