Найдите самую длинную возрастающую подпоследовательность. - Turbo Pascal

Узнай цену своей работы

Формулировка задачи:

Дана последовательность n целых чисел. Найдите самую длинную возрастающую подпоследовательность.
Моя программа генерирует все множества из n количества элементов. Не могу найти самую длиннную возраст подпоследовательность. Помогите пожалуиста

Решение задачи: «Найдите самую длинную возрастающую подпоследовательность.»

textual
Листинг программы
uses crt;
const nmax=100;
var a:array[1..nmax] of integer;
      i,j,n,k,p1,max:byte;
begin
clrscr;
repeat
write('Размер массива от 2 до ',nmax,' n=');
readln (n);
until n in [2..nmax];
writeln('Введите ',n,' элементов массива:');
for i:=1 to n do
readln (a[i]);
clrscr;
writeln('Массив:');
for i:=1 to n do
write(a[i],' ');
writeln;
writeln;
{Поиск позиции и длины максимальной цепи}
max:=0;{Первоначальные значения}
i:=2;p1:=0;
while i<=n do
if a[i]>a[i-1] then
  begin
   k:=1;j:=i;
   while (a[j]>a[j-1])and(j<=n) do
    begin
     inc(j);
     inc (k); {Если возрастает - наращиваем счётчик}
    end;
   if k>max then
    begin
     max:=k;
     p1:=i-1;
    end;
   i:=i+k;{перепрыгиваем}
  end
else inc(i);
writeln; {Выводим результат}
if max=0 then write('Участков возрастания нет!')
else
 begin
  writeln('Максимальная длина=',max);
  for i:=p1 to p1+max-1 do
  write (a[i],' ');
 end;
readln
end.

Объяснение кода листинга программы

  1. Создается переменная nmax и присваивается ей значение 100.
  2. Создается массив a типа array[1..nmax] of integer.
  3. Создаются переменные i, j, n, k, p1 и max и присваиваются им начальные значения.
  4. Выводится сообщение с предложением ввести размер массива от 2 до nmax и сам размер массива.
  5. Считывается размер массива n.
  6. Считываются n элементов массива.
  7. Выводится сообщение с предложением ввести n элементов массива.
  8. Запускается цикл while i<=n do, который будет выполняться, пока i меньше или равно n.
  9. Внутри цикла проверяется условие if a[i]>a[i-1] then. Если это условие истинно, то начинаются вложенные циклы while (a[j]>a[j-1])and(j<=n) и if k>max then, которые будут выполняться, пока a[j] больше a[j-1] и k больше max.
  10. Если условие из пункта 9 истинно, то увеличивается значение j и k на единицу, а также обновляется значение max, если k больше max.
  11. После окончания вложенных циклов внутреннего цикла, значение i увеличивается на k.
  12. Если внутренний цикл не выполнялся, то значение i увеличивается на единицу.
  13. Выводится сообщение с предложением вывести результат.
  14. Если max равно нулю, выводится сообщение о том, что участков возрастания нет.
  15. В противном случае выводится сообщение с максимальной длиной возрастающей подпоследовательности.
  16. Для i от p1 до p1+max-1 выводится элемент массива a[i].
  17. Выводится символ новой строки.
  18. Программа завершается.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

14   голосов , оценка 3.643 из 5
Похожие ответы