Разбор решения. Урок 15 Задача 20 - Поиск элементов в массиве, минимальный отрезок

Урок 15 Задача 20

Условие:
Дан массив длиной N (не более 100 элементов), состоящий из случайно выбранных чисел из диапазона от 0 до k, где 0≤k Найдите в этом массиве длину самого короткого фрагмента, который содержит все числа от 0 до k.

Например:

• Для N = 6, k=2:
  $ 2\; \underbrace{0\; 2 \;2 \;1}_{\text{длина=4}}\; 1 $
• Для N = 10, k=2:
  $ 2\; 0\; 2\; 2\; 1\; 1\; 0\; \underbrace{0\; 1\; 2}_{\text{длина=3}} $
• Для N = 15, k=3:
  $ 2\; 0\; 2\; 2\; 3\; 3\; 0\; 0\; 2 \; 3 \; \underbrace{0 \; 3 \; 2 \; 1}_{\text{длина=4}} \; 0 $
• Для N = 7, k=2:
  $ 0\; \underbrace{ 1 \;0 \;0 \;0 \;2}_{\text{длина=5}}\; 0 $

Решение:

type Arr= array[1..10] of integer;  //Объявим тип: массив из десяти чисел.
var bigArr: Arr; k,i,min,l,m: integer;  // Объявим переменные.

Здесь:

• i- счётчик, определяющий порядковый номер элемента массива bigArr в цикле.
• min - понадобится для заполнения массива случайными числами с помощью randomize. В этом примере для удобства проверки массив задаётся вручную, так что она не используется.
• l - результат сравнения текущего значения m с предыдущим: наименьший из рассмотренных участок массива, на котором встречаются все числа промежутка [0,k]. Начальное значение = длина массива+1, сохранится, только если в массиве встречаются не все числа промежутка [0,k].
• m - результат выполнения функции otrezok: участок массива, на котором встречаются все числа промежутка [0,k].

Тело программы:

type Arr= array[1..10] of integer;
var bigArr: Arr; k,i,min,l,m: integer;

function otrezok (b:Arr; first,d:integer):integer;  {функцию 
                                                 рассмотрим ниже}

begin
  k:=3;
  l:=11; //Здесь массив из 10 чисел, задаём такое значение, чтоб l 
            //точно уменьшилась в процессе

  bigArr[1]:= 2;  //Для удобства проверки задаём массив вручную
  bigArr[2]:= 1;
  bigArr[3]:= 0;
  bigArr[4]:= 2;
  bigArr[5]:= 1;
  bigArr[6]:= 0;
  bigArr[7]:= 0;
  bigArr[8]:= 2;
  bigArr[9]:= 1;
  bigArr[10]:= 3;    

  for i:=low(bigArr) to (high(bigArr)-k) do  
{Верхняя граница = high(bigArr)-k, так как функция
будет искать числа [0,k] начиная с i-того элемента, 
нет смысла искать числа от 0 до k на участке меньше k.}
  begin
    m:= otrezok(bigArr,i,k); {В функцию передаётся массив, 
                       порядковый номер элемента, с которого функция 
                       начнёт поиск чисел [0,k] и само число k.}
                        {Для удобства результат выполнения функции 
                         присваивается переменной m.}
    if m=0 then {Если m=0, значит, найдены не все числа 
                         промежутка [0,k]}
      break;   //дальнейшее прохождение цикла лишается смысла
    if m <l then  {значение m сравнивается со значением l, и если 
                       этот участок (m) короче предыдущего (l), 
                      переменной l присваивается новое значение m.}
      l:= m;
  end;
  if l=11 then  {Если в массиве есть все числа [0,k], 
                         l уменьшится хотя бы на единицу}
    write ('net takogo uchastka')
  else
    write ('Otvet: ', l);
  readln();
end.      

Кратчайший участок массива с числами [0,k] находится через сравнение результатов функции.

Функция

Задача функции otrezok - найти в массиве bigArr участок, где встречаются все числа от нуля до k.
Для этого функция будет сравнивать поочерёдно числа от 0 до k с каждым элементом массива bigArr начиная с первого элемента.
Функция принимает аргумент i за точку отсчёта, то есть ищет все числа промежутка [0,k], начиная с i-того элемента массива. То есть, извне передаётся i=1 - ищет числа [0,k] во всём массиве, пока не найдёт k или не переберёт все элементы массива. Потом i=2 - поиск начинается со второго элемента, потом с третьего и так далее.
Функция находит все ближайшие к точке отсчёта числа до k и возвращает расстояние от точки отсчёта до самого дальнего из ближайших чисел [0,k].
Если массив пройден, а одно из искомых чисел не найдено, функция вернёт 0.

type Arr= array[1..10] of integer;
var bigArr: Arr; k,i,min,l,m: integer;

function otrezok(a:Arr; i,k:integer):integer;
var h,j,last:integer;
begin
last:=0;
for j:=0 to k do
begin
for h:= i to high(a) do
if a[h]=j then
begin
if (h-i+1)>last then
last:=(h-i+1);  //когда найдено числ k, внутренний цикл прерывается
   if (h= high(a)) and (a[h]<>j) then {массив пройден, а нужное 
                                число не обнаружено.}
   begin
     last:=0;  {Если массив пройден, а одно из искомых чисел не 
                    найдено - переменная last обнулится.}
     break;  //Внешний цикл прерывается.
   end;
  end;
  result:=last;
end;                  

Код целиком:

type Arr= array[1..10] of integer;
var bigArr: Arr; k,i,min,l,m: integer;

function otrezok(a:Arr; i,k:integer):integer;
var h,j,last:integer;
begin
last:=0;
for j:=0 to k do
begin
for h:= i to high(a) do
if a[h]=j then
begin
if (h-i+1)>last then
last:=(h-i+1);
break;
end;
if (h= high(a)) and (a[h]<>j) then
begin
last:=0;
break;
end;
end;
result:=last;
end;

begin
k:=3;
l:=11;
bigArr[1]:= 2;
bigArr[2]:= 1;
bigArr[3]:= 0;
bigArr[4]:= 2;
bigArr[5]:= 1;
bigArr[6]:= 0;
bigArr[7]:= 0;
bigArr[8]:= 2;
bigArr[9]:= 1;
bigArr[10]:= 3;

for i:=low(bigArr) to (high(bigArr)-k) do
begin
m:= otrezok(bigArr,i,k);
if m=0 then
break;
if m <l then
l:= m;
end;
if l=11 then
write ('net takogo uchastka')
else
write ('Otvet: ', l);
readln();
end.