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

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

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

type
  massiv = array[1..100] of integer;
var
  mass: massiv;
  k, m, p, i, j, a, b: integer;
  q: boolean;

// функция проверяет все ли числа от 0 до k есть на участке массива от m до p
function prov (mass: massiv; k, m, p: integer): boolean;
var
  i, j: integer;
  q: boolean;
begin
  for i:=0 to k do                // внешний цикл (от 0 до k)
  begin
    q:= false;
    for j:=m to p do              // вложенный цикл (фрагмент массива от m до p)
      if i = mass[j] then         // если встретилось число
      begin
        q:=true;                  // переключаем переключатель
        break;                    // выходим из вложенного цикла
      end;
    if q = false then // если переключатель не переключился (не встретилось число)
    begin
      break;          // выходим из внешнего цикла
    end;
  end;
  result:= q;
end;

begin
  randomize();
  for i:=low(mass) to high(mass) do
  begin
    mass[i] := random(23);
    write (mass[i], ' ');
  end;
  writeln;
  writeln;
  k:= 17;
  a:= 0;
  b:= 0;
  for m:=low(mass) to high(mass)-k do  // внешний цикл, двигается левая граница (m) фрагмента массива
  begin
    for p:= m+k to high(mass) do       // вложенный цикл, двигается правая граница (p) фрагмента массива
    begin
      q:= prov(mass, k, m, p);         // вызываем функцию, передаем массив, число k, левую границу, правую границу фрагмента
      if q = true then                   // если во фрагменте есть все числа от 0 до k
      begin
        if (a=0) or ((p-m) < (b-a)) then // проверяем, является ли фрагмент минимальным
        begin
          a:= m;             // начало минимального фрагмента
          b:= p;             // конец минимального фрагмента
        end;
      end;
    end;
  end;
  writeln('Чиcла от 0 до ', k);
  if not (a=0) then
  begin
    writeln('Начало фрагмента: ', a);
    writeln('Конец фрагмента: ', b);
    writeln('Длина: ', b-a+1, ' элем.');
    for i:=a to b do
      write (mass[i], ' ');
  end else
    writeln('Не все числа от 0 до ', k, ' встречаются в массиве');
  readln();
end.

Вывод в консоли:

0 21 2 17 0 0 15 20 18 4 21 3 22 22 18 0 12 5 19 20 2 18 5 7 14 8 5 20 14 9 13 7 1 6 3 1 19 15 16 3 22 13 4 17 1 0 2 6 15 19 5 17 21 4 7 10 20 5 13 19 14 2 19 7 4 0 22 3 1 6 2 0 3 0 11 18 15 10 9 12 6 5 11 6 20 6 15 5 15 6 12 3 16 16 13 21 6 10 3 0 
Чиcла от 0 до 17
Начало фрагмента: 26
Конец фрагмента: 80
Длина: 55 элем.
8 5 20 14 9 13 7 1 6 3 1 19 15 16 3 22 13 4 17 1 0 2 6 15 19 5 17 21 4 7 10 20 5 13 19 14 2 19 7 4 0 22 3 1 6 2 0 3 0 11 18 15 10 9 12