Последовательность, Рекурсия Опции

[sheka]

Дана последовательность целых чисел. Путем удаления некоторых элементов (не переставляя элементы) получить неубывающую последовательность максимальной длины.
Думаю сделать так: найти самую длинную цепочку, запомнить с какого элемента она начинается и уже потом вывести.2й и 3й пункт сложности не представляют, а с первым проблемки...можно конечно кучей циклов фор...но мы не знаем количество элементов массива. Поэтому надо рекурсией. Вот мое чудо, которое в мозгах работает на отлично, а Паскаль не понимает))):

const
  n=8;
                          {1 2 3 4 5 6 7 8 9 0 1}
  m:array[1..n]of integer=(2,0,7,5,3,6,6,5);

var
  p:integer;
  nac:integer;
  max:integer;

procedure find(p:integer;curr:integer);
var
  i:integer;
  qq:byte;
begin
  for i:=p+1 to n do
    begin
      if m[p]<=m[i] then
        begin
          inc(curr);
          if max<curr then
            begin
              max:=curr;
              nac:=p;
            end;
          find(i,curr);
        end;

  for qq:=1 to n do write(qq,' '); writeln;
  for qq:=1 to n do write(m[qq],' '); writeln;
  writeln('p=',p);
  writeln('i=',i);
  writeln('m[',p,']=',m[p]);
  writeln('m[',i,']=',m[i]);
  writeln('curr=',curr);
  writeln('nac=',nac);
  writeln('max=',max);

  readln;

    end;
end;

begin
  nac:=1;
  find(1,1);
  writeln('max=',max);
  readln;
end.

ЗЫ А Watches работает только с глобальными переменными?

[volvo]

можно конечно кучей циклов фор...но мы не знаем количество элементов массива. Поэтому надо рекурсией.

Правда что-ли? А если удобнее без рекурсии, что делать? Обязательно хочется написать рекурсивно? Вообще эта задача решается так, если не ошибаюсь:

const
  n = 8;
type
  Arr = array[0 .. pred(n)] of integer;

const
  A: Arr = (2, 0, 7, 5, 3, 6, 6, 5);

var
  B, C: Arr;
  i, j, imax, ref: integer;

begin
  imax := 0;
  for i := pred(n) downto 0 do
  begin
    B[i]:=1;
    for j := i+1 to pred(n) do
    begin

      if (A[j] >= A[i]) and (B[i] < B[j] + 1) then
      begin
        B[i] := B[j]+1;
        C[i] := j;
        if B[j] = imax then break;
      end;
    end;
    if B[i] > imax then imax := B[i];
   end;

   for i := 0 to pred(n) do
     if B[i] = imax then break;

   ref := i;
   for j := 0 to pred(imax) do
   begin
      write(A[ref]:4); ref := C[ref];
   end;
end.

А Watches работает только с глобальными переменными?

С чего ты взял? С любыми работает... А еще есть Call Stack, тоже очень удобно отлаживать рекурсию...

[sheka]

Напишите, пожалуйста, логику Вашего решения.
И, если не тяжело, посмотрите что у меня не так. уже часов 5 на нее убил.
у меня watches вообще проскакивает рекурсивную процедуру, вот и приходилось выводить все данные)

Сообщение отредактировано: sheka - 5.11.2009 16:03

[volvo]

Напишите, пожалуйста, логику

АлгоЛист: Рекуррентные соотношения и динамическое программирование см. задачу №20

у меня watches вообще проскакивает рекурсивную процедуру

Watches - это окно просмотра переменных при отладке. Оно не может ничего проскакивать. Используй Трассировку (F7), а не F8, тогда не будет ничего проскакивать. Ссылка в тему