Главная

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

сб, 02/12/2011 - 20:50 — tech
Темы учебника
Массивы в Паскале. Одномерные массивы
Общее представление о массивах
Задача: 

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

Алгоритм решения задачи: 

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

Очевидно, нам требуются переменные для хранения размера самой длинной последовательности нулей массива (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.

  • Добавить комментарий

Комментарии

сб, 12/13/2014 - 16:44 — Гость

Подскажите,пожалуйста,как будет выглядеть программа если:

Если нужно определить самую длинную серию одинаковых элементов и указать из каких элементов она состоит?

  • ответить
Втр, 12/16/2014 - 02:28 — Гость

определить самую длинную серию одинаковых элементов

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 )    
    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.

  • ответить
вс, 10/28/2012 - 12:53 — tech

Такая же задача. Удалена. Решение немного отличается. Сравнить

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

Например, если массив выгдядит так:
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.

  • ответить