Найдите самую длинную возрастающую подпоследовательность. - 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.
Объяснение кода листинга программы
- Создается переменная
nmax
и присваивается ей значение 100. - Создается массив
a
типаarray[1..nmax] of integer
. - Создаются переменные
i
,j
,n
,k
,p1
иmax
и присваиваются им начальные значения. - Выводится сообщение с предложением ввести размер массива от 2 до
nmax
и сам размер массива. - Считывается размер массива
n
. - Считываются
n
элементов массива. - Выводится сообщение с предложением ввести
n
элементов массива. - Запускается цикл
while i<=n do
, который будет выполняться, покаi
меньше или равноn
. - Внутри цикла проверяется условие
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
. - Если условие из пункта 9 истинно, то увеличивается значение
j
иk
на единицу, а также обновляется значениеmax
, еслиk
большеmax
. - После окончания вложенных циклов внутреннего цикла, значение
i
увеличивается наk
. - Если внутренний цикл не выполнялся, то значение
i
увеличивается на единицу. - Выводится сообщение с предложением вывести результат.
- Если
max
равно нулю, выводится сообщение о том, что участков возрастания нет. - В противном случае выводится сообщение с максимальной длиной возрастающей подпоследовательности.
- Для
i
отp1
доp1+max-1
выводится элемент массиваa[i]
. - Выводится символ новой строки.
- Программа завершается.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д