Поиск элементов [pascal]

[s-andriano]

Сообщение от illuminato

s-andriano, Серия - последовательность повторяющихся элементов.

Когда даете неочевидные трактовки, желательно указывать источник.

Большой Энциклопедичесий словарь
СЕРИЯ - (от лат . series - ряд),1) группа или ряд предметов, однородных или обладающих общим признаком.2) Разряд, категория ценных бумаг (напр., серия облигаций), документов (напр., серия паспорта), обозначаемых цифрами.3) Часть фильма, демонстрируемая самостоятельно.4) В музыке - избираемый композитором ряд из 12 или менее звуков различной высоты, повторения которого образуют всю ткань произведения (см. Додекафония)

В. И. Даль, Толковый словарь живого великорусского языка
СЕРИЯ - ж. франц. денежный процентный, срочный билет госуд. казначейства, из выпускаемых у нас сериями, т. е. порядками

Толковый словарь Ожегова
СЕРИЯ - одна из относительно самостоятельных частей большого фильма E.g. Фильм в двух сериях. <HR> разряд, категория ценных бумаг, документов E.g. С. и номер паспорта. С. облигаций. <HR> последовательный ряд чего-нибудь, что обладает общим признаком, объединено общим назначением, составляет одну группу E.g. С. популярных брошюр. С. опытов. Изделие выпускается малыми сериями.

Как видим, везде употребляется слово "однородные", а не "одинаковые". Символы строки - вполне себе однородные объекты, даже если не одинаковые. А в музыке - вообще, специально указано, что ноты разные (разные ноты - тоже однородные сущности).

[illuminato]

Ну так что, поможет кто-нибудь? В данном случаи серия это повторяющиеся элементы 54543333333.

Задан двунаправленный список, содержащий целочисленные значения. Удалить из указанного списка серии максимальной длины.

[BDA]

поможет кто-нибудь?

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

[s-andriano]

Сообщение от illuminato

Ну так что, поможет кто-нибудь? В данном случаи серия это повторяющиеся элементы 54543333333.

Ваш пример противоречит формулировке из первого поста.

Правда, я обнаружил, что, вопреки заверениям, некоторые участники форума явно обладают телепатией.
Правда, возможно, они рассуждают примерно так:
"Сформулированная задача слишком сложна, поэтому, вероятно, ее условие изложено неправильно. Если так, его нужно откорректировать. Корректировать будем так, чтобы максимально упростить решение."
В принципе, решать не ту задачу, которая предложена, а ту, которая проще - не есть правильно. Но, похоже, по факту это иногда срабатывает.

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

Сообщение от BDA

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

Список не нужен - достаточно хранить одну последовательность - кандидата на максимум, а подсчитывать текущую длину - в другой. Т.е. всего две, которые достаточно сделать простыми переменными - список не нужен.

[BDA]

s-andriano, я имел ввиду случай, когда в списке есть несколько подпоследовательностей максимальной длины. Чтобы их удалить, есть два подхода:
1) Пройти по списку и найти длину максимальной подпоследовательности. Вторым проходом удалить все подпоследовательности такой длины.
2) В одном проходе складывать начала подпоследовательностей нужной длины в список
(Возможно, есть другие подходы, но они не пришли в голову сразу)

по факту это иногда срабатывает.

Именно так. Часто бывает, что формулировка не соответствует ожиданиям преподавателя. Условия составляются с кучей неточностей и двояких трактовок.

[illuminato]

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

Program Spisok_dn;
uses
  crt; 
type
  Tinf=integer;
  List=^TList;  
  TList=record 
    data:TInf;
    next, 
    prev:List; 
  end;
  
procedure AddElem(var nach,ends:List;znach1:TInf);
begin
  if nach=nil then
  begin
    Getmem(nach,SizeOf(TList)); 
    nach^.next:=nil; 
    nach^.prev:=nil; 
    ends:=nach; 
  end
  else 
  begin
    GetMem(ends^.next,SizeOf(Tlist));
    ends^.next^.prev:=ends; 
    ends:=ends^.next;
    ends^.next:=nil; 
  end;
  ends^.data:=znach1;
end;


procedure Print(spis1:List);
begin
  if spis1=nil then
  begin
    writeln('‘¯¨á®ª ¯ãáâ.');
    exit;
  end;
  while spis1<>nil do
  begin
    Write(spis1^.data, ' ');
    spis1:=spis1^.next
  end;
end;



var
 SpisNach, 
  SpisEnd,   
  tmpl:List; 
  znach,a,b:integer;
  ch:char;
  n:integer;
  i:byte;
begin

i:=1;
While LowCase(ch)<>chr(110) do begin
write('Введите элемент:  ',i,' : ');
readln(znach);
AddElem(SpisNach,SpisEnd,znach);
Writeln('Продолжить ввод(Y/N): ');
read(ch);
inc(i);
Writeln;
end;
Writeln('Вывод:');
print(SpisNach);


     
 end.

[BDA]

type
  Tinf = integer;
  List = ^TList;

  TList = record
    data: Tinf;
    next, prev: List;
  end;

procedure AddElem(var nach, ends: List; znach1: Tinf);
begin
  if nach = nil then
  begin
    new(nach);
    nach^.next := nil;
    nach^.prev := nil;
    ends := nach;
  end
  else
  begin
    new(ends^.next);
    ends^.next^.prev := ends;
    ends := ends^.next;
    ends^.next := nil;
  end;
  ends^.data := znach1;
end;

procedure Print(spis1: List);
begin
  if spis1 = nil then
  begin
    writeln('Empty');
    exit;
  end;
  while spis1 <> nil do
  begin
    Write(spis1^.data, ' ');
    spis1 := spis1^.next
  end;
end;

procedure del_seq(var SpisNach, spisend: List);
var
  max_count, count: integer;
  tmp, nach, tmp2: List;
begin
  max_count := 0;
  count := 0;
  tmp := SpisNach;
  nach := SpisNach;
  while tmp <> nil do
  begin
    while (tmp <> nil) and (tmp^.data = nach^.data) do
    begin
      tmp := tmp^.next;
      inc(count);
    end;
    if count > max_count then
      max_count := count;
    count := 0;
    nach := tmp;
  end;
  tmp := SpisNach;
  nach := SpisNach;
  count := 0;
  while tmp <> nil do
  begin
    while (tmp <> nil) and (tmp^.data = nach^.data) do
    begin
      tmp := tmp^.next;
      inc(count);
    end;
    if count = max_count then
    begin
      if nach^.prev <> nil then
        nach^.prev^.next := tmp
      else
        SpisNach := tmp;
      if tmp <> nil then
        tmp^.prev := nach^.prev
      else
        spisend := nach^.prev;
      while nach <> tmp do
      begin
        tmp2 := nach;
        nach := nach^.next;
        dispose(tmp2);
      end;
    end;
    count := 0;
    nach := tmp;
  end;
end;

procedure del(var sp: List);
var
  tmp: List;
begin
  while sp <> nil do
  begin
    tmp := sp;
    sp := sp^.next;
    dispose(tmp);
  end;
end;

var
  SpisNach, spisend, tmpl: List;
  znach, a, b: integer;
  ch: char;
  n: integer;
  i: byte;

begin
  i := 1;
  ch := 'Y';
  While LowerCase(ch) <> chr(110) do
  begin
    write('Input item:  ', i, ' : ');
    readln(znach);
    AddElem(SpisNach, spisend, znach);
    writeln('Continue input (Y/N): ');
    read(ch);
    inc(i);
    writeln;
  end;
  writeln('Output:');
  Print(SpisNach);
  del_seq(SpisNach, spisend);
  writeln;
  writeln('Output:');
  Print(SpisNach);
  del(SpisNach);
  readln;
  readln;
end.

Мог ошибиться где-нибудь в логике.
Это вариант с 2 проходами по списку.

[illuminato]

BDA, спасибо большое. Вы мне очень помогли и сохранили моё время.

[s-andriano]

Сообщение от BDA

s-andriano, я имел ввиду случай, когда в списке есть несколько подпоследовательностей максимальной длины. Чтобы их удалить, есть два подхода:
1) Пройти по списку и найти длину максимальной подпоследовательности. Вторым проходом удалить все подпоследовательности такой длины.
2) В одном проходе складывать начала подпоследовательностей нужной длины в список

Сложность указанных алгоритмов:
1) O(N) по времени, O(1) по памяти.
2) O(N) по времени, O(N) по памяти.

Именно так. Часто бывает, что формулировка не соответствует ожиданиям преподавателя. Условия составляются с кучей неточностей и двояких трактовок.

Я так не умею.

*Кстати, до прохода мо массиву мы не знаем "нужно длины", так что сначала придется помещать в список все последовательности (как смещение, так и длину) с длиной не меньше уже обнаруженной, а потом дополнительно просматривать список для нахождения последовательностей нужной длины.

[s-andriano]

Сообщение от illuminato

BDA, спасибо большое. Вы мне очень помогли и сохранили моё время.

Ну да.
Очевидно, Ваше время намного дороже времени BDA.