Поиск самой длинной заданной последовательности в массиве

Задача

Код на Паскале ниже создает массив из двадцати элементов. Затем находит самую длинную последовательность из нулей и выводит на экран ее длину и номер ее начала в массиве.

Решение

 

Рассмотрим код программы.

Очевидно, нам требуются переменные для хранения размера самой длинной последовательности нулей массива (len_max) и номера первого элемента этой последовательности (start).

При просмотре массива находится очередная последовательность нулей. Ее длина должна быть сохранена для последующего сравнения с самой длинной последовательностью, найденной до этого. Поэтому вводится еще одна переменная для хранения длины текущей серии последовательных нулей (len_ser).

Всем трем переменным сначала присваивается 0. Что означает, что никаких искомых последовательностей в массиве нет.

Далее массив просматривается поэлементно (в цикле for).

Если значение очередного элемента равно нулю, то длина текущей серии увеличивается. Иначе (когда значение очередного элемента не равно нулю), необходимо проверить, что содержится в переменной len_ser. Если перед этим была серия из нулей и длина этой серии оказалась больше значения len_max, то требуется обновить значение len_max и вычислить значение начала текущей максимальной последовательности нулей (start).

Также нужно обнулить значение len_ser, независимо от того произошла перезаписьlen_max или нет. Ведь предыдущая последовательность все равно закончилась.

Во внешнюю ветку if вложена еще одна инструкция if (в которую вложена еще одна веткаif).

        if i = n then
                if len_ser > len_max then begin
                    len_max := len_ser;
                    start := i - len_ser
                end

Этот код необходим для того, чтобы учитывать последний элемент. Если его значение 0, то обработка этой серии не будет завершена, т.к. ветка else уже не сработает. Поэтому его учет надо произвести отдельно.

Программа на языке Паскаль: 

 

const n = 20;
 
var
    arr: array[1..n] of 0..1;
    i, len_max, len_ser, start: byte;
 
begin
    writeln('Массив: ');
    randomize;
    for i := 1 to n do begin
        arr[i] := random(2);
        write(arr[i]:2);
    end;
    writeln;
 
    len_max := 0;
    len_ser := 0;
    start := 0;
 
    for i := 1 to n do
        if arr[i] = 0 then begin
            len_ser := len_ser + 1;
            if i = n then
                if len_ser > len_max then begin
                    len_max := len_ser;
                    start := i - len_ser
                end
        end
        else begin
            if len_ser > len_max then begin
                len_max := len_ser;
                start := i - len_ser
            end;
            len_ser := 0
        end;
 
    writeln('Длина максимальной серии: ',len_max);
    writeln('Начинается с ', start, '-й позиции');
 
readln
end.

 

Комментарии

Гость (не проверено) 16/12/2014 
type
  mas = array of integer;
  pair = record
    elem:  integer;
    count: integer;
  end;
 
 // функция рандомного задания элементов масива
function fill(num: integer): mas;
var
  i: integer;
begin
  SetLength(Result, num);
  for i := 0 to num - 1 do
    Result[i] := Random(1, 10); // рандомное задание эл-та от  -10 до 10
end;
 
//  функция нахождение элемента максимальное
//  количество раз входящего в массив
//  вывод эдет в тип pair, где
//  pair.elem - элемент массива,
//  pair.count - (количество - 1) раз входящее в массив 
function counter(arr: mas): pair;
var
  i, k: integer;
  count: integer;
begin
  Result.count := -1000;
  for i := 0 to arr.Length - 2 do
  begin
    count := 1;
    for k := i + 1 to arr.Length - 2 do
      if arr[i] = arr[k] then
        inc(count);
    if(result .count < count)    
    then
    begin
      Result.count := count; 
      Result.elem := arr[i];  
    end;
  end;
end;
 
//процедура вывода массива
procedure output(arr: mas);
var
  j: integer;
begin
  for j := 0 to arr.Length - 1 do
    Write('[', arr[j], ']', #9);
  writeln();
end;
 
var
  arr: mas;
  n: integer;
  p: pair;
 
begin
  Writeln('введите количество элементов массива: '); Readln(n);
  Randomize();
  arr := (fill(n));   output(arr);
  p := counter(arr);
  writeln(p.elem, ' = >', p.count);
 
end.

gene 28/10/2012

Найти в массиве самую длинную последовательность, состоящую из одинаковых элементов. Вывести на экран количество элементов самой длиной последовательности и номер элемента, который является ее началом.

Например, если массив выгдядит так:
0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0
, то количество элементов самой длинной последовательности, состоящей из одинаковых элементов, равно 5, а начинается она с 9-го элемента.

const
    N = 30;
var
    arr: array[1..N] of byte;
    i: byte;
    start_max, len_max, start_current, len_current: byte;
 
begin
    randomize;
    for i:=1 to N do begin
        arr[i] := random(2);
        write(arr[i],' ');
    end;
    writeln;
 
    len_max := 1;
    len_current := 1;
    start_current := 1;
    for i:=1 to N-1 do
        if arr[i] = arr[i+1] then
            len_current := len_current + 1
        else begin
            if len_current > len_max then begin
                len_max := len_current;
                start_max := start_current;
            end;
            len_current := 1;
            start_current := i+1;
        end;
 
    if len_current > len_max then begin
        len_max := len_current;
        start_max := start_current;
    end;
 
    writeln('Начало последовательности (номер элемента): ', start_max);
    writeln('Длина последовательности: ', len_max);
readln;
end.

 

gene 17/06/2017

Посчитать максимальное количество подряд идущих четных элементов в целочисленном массиве длины 30.

const M = 30;
var   
    a: array[1..M] of byte;
    i, max, count: byte;
begin
    randomize;
    for i:=1 to M do begin
        a[i] := random(100);
        write(a[i]:3);
    end;
    writeln;
 
    max := 0;
    count := 0;
    for i:=1 to M do begin
        if a[i] mod 2 = 0 then
            count := count + 1
        else begin
            if count > max then
                max := count;
            count := 0;
        end;
    end;
    writeln(max);    
end.