Найти самые длинные последовательности чисел, упорядоченные по возрастанию
Задача
Заполнить массив случайными числами, вывести его на экран. Найти самую длинную последовательность чисел, упорядоченную по возрастанию. Вывести ее на экран. Если таких последовательностей несколько (самых длинных с одинаковой длиной), то вывести их все.
Решение
Описание переменных:
- i - индекс текущего элемента массива;
- l - длина текущей последовательности, упорядоченной по возрастанию;
- lmax - длина самой длинной последовательности, упорядоченной по возрастанию;
- j - индекс текущего элемента выводимой на данный момент последовательности.
Алгоритм решения задачи:
Задачу можно разбить на три подзадачи:
- Заполнение и вывод массива.
- Определение длины самой длинной последовательности чисел, упорядоченных по возрастанию.
- Вывод всех упорядоченных по возрастанию последовательностей с найденной в п. 2 длинной.
Алгоритм определения длины:
- Присвоить переменным lmax и l значение 1.
- В цикле перебирать элементы массива, начиная со второго:
- если очередной элемент больше предыдущего, то увеличивать на 1 значение l;
- иначе:
- если l больше lmax, то присвоить lmax значение l,
- снова присвоить l единицу.
Вывод всех самых длинных последовательностей, упорядоченных по возрастанию:
- Снова просматриваем массив и находим длину текущей последовательности, упорядоченной по возрастанию.
- Если эта длина равна lmax, то выводим элементы массива, начиная с i-l до i-1 (с начала последовательности до предыдущего элемента).
Программа на языке Паскаль:
const N = 45; var arr: array[1..N] of byte; i, j, l, lmax: byte; begin randomize; for i:=1 to N do begin arr[i] := random(100); write(arr[i]:3); end; writeln; lmax := 1; l := 1; for i:=2 to N do if arr[i] > arr[i-1] then l := l + 1 else begin if l > lmax then lmax := l; l := 1; end; writeln(lmax); if lmax = 1 then exit; l := 1; for i:=2 to N do if arr[i] > arr[i-1] then l := l + 1 else begin if l = lmax then begin for j:=i-l to i-1 do write(arr[j]:3); writeln; end; l := 1; end; end.
Пример выполнения программы:
62 6 11 2 78 37 99 8 80 3 59 71 85 59 46 66 1 43 89 67 48 72 88 57 82 62 51 14 6 88 47 79 96 98 97 58 50 60 58 84 98 69 2 46 12 4 3 59 71 85 47 79 96 98
Комментарии
Неверное решение
Неверное решение! Второй цикл работает верно, если только наибольшая последовательность не находится в конце. К примеру если взять последовательность {1,2,3,4,5,3,2,5,7,9,10,11}, то явно максимальная последовательность будет состоять из 6 элементов, однако, дойдя до последнего элемента l=6, но в else цикл не перейдет, т.к. не выполнится условие arr[i] > arr[i-1], потому что последний элемент сравнить не с чем. Тут нужно еще условие на проверку конца цикла....
подправил проверки, теперь и последний тоже считает
Ответ на Неверное решение от Гость (не проверено)