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

Primary tabs

Submitted by NewDeveloper on Fri, 08/13/2021 - 06:06

Forums:

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

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

Например:

  • Для N = 6, k=2:
    20221⏟длина=41
  • Для N = 10, k=2:
    2022110012⏟длина=3
  • Для N = 15, k=3:
    20223300230321⏟длина=40
  • Для N = 7, k=2:
    010002⏟длина=50

Для быстрой проверки кода через запуск используйте следующий тип массива:

type
    ArrOfInt = array[1..100] of integer;
type
  ArrOfInt = array[1..100] of integer;
var i, n, k, c, x, y, l, h: integer;   
  z: boolean;
  a: ArrOfInt;
begin
  randomize();
  write('Введите длину массива не более 100: ');
  readln(n);
  k := random(n);
  for i := 1 to n do a[i] := random(k + 1);
  write('Массив: ');
  for i := 1 to n do write(a[i], ' ');
  writeln();
  writeln('k=', k);
  x := 1;
  c := k;
  y := k + 1;
  l := k + 1;
  while true do
   begin
    repeat
     z := false;
     for i := x to y do
      if a[i] = c then z := true;
     if z then c -= 1
     else
      begin
       x += 1;
       y += 1;
       c := k;
      end;
    until (c = -1) or (y = n + 1);
    if c = -1 then break
    else l += 1;
    h += 1;
    y := k + 1 + h;
    if y = n + 1 then break;
    x := 1;
   end;
  writeln();
  if c = -1 then writeln('Минимальная длина фрагмента равна: ', l)
  else writeln('Не найдены все числа в диапазоне 0 <= k');
  readln();
end.
  • Log in to post comments
  • 3101 reads
vedro-compota's picture

vedro-compota

Sun, 08/22/2021 - 14:00

разбить на подпрограммы - в частности хотя бы выделить функцию проверки наличия всех чисел на указанном диапазоне

_____________
матфак вгу и остальная классика =)

NewDeveloper

Sun, 08/22/2021 - 17:24

Здесь нельзя выделить функцию проверки наличия всех чисел в указанном диапазоне, можно отделить только функцию поиска фрагмента длиной x...y со всеми числами на всем массиве.

type
  ArrOfInt = array [1..100] of integer;
function chek_length_xy(a1: ArrOfInt; n1, k1: integer;
                              var y1, c1: integer):integer;
var z: boolean;
    i1, x: integer;
begin
 x := 1;
 repeat
  z := false;
  for i1 := x to y1 do
   if a1[i1] = c1 then z := true;
  if z then c1 -= 1
  else
   begin
    x += 1;
    y1 += 1;
    c1 := k1;
   end;
 until (c1 = -1) or (y1 = n1 + 1);
 result := c1;
end;

var i, n, k, c, y, l, h: integer;
  a: ArrOfInt;
begin
  randomize();
  write('Введите длину массива не более 100: ');
  readln(n);
  k := random(n);
  for i := 1 to n do a[i] := random(k + 1);
  write('Массив: ');
  for i := 1 to n do write(a[i], ' ');
  writeln();
  writeln('k=', k);
  c := k;
  y := k + 1;
  l := k + 1;
  while true do
   begin
    chek_length_xy(a, n, k, y, c);
    if c = -1 then break
    else l += 1;
    h += 1;
    y := k + 1 + h;
    if y = n + 1 then break;
   end;
  writeln();
  if c = -1 then writeln('Минимальная длина фрагмента равна: ', l)
  else writeln('Не найдены все числа в диапазоне 0 <= k');
  readln();
end.
vedro-compota's picture

vedro-compota

Sun, 08/22/2021 - 21:35 

function chek_length_xy(a1: ArrOfInt; n1, k1: integer;
                              var y1, c1: integer):integer;

тут подозрительно много переменных на вход
Достаточно передать массив, две границы, ну и там число k, при этом ни одно из этих значений не надо передавать по ссылке
-- т.е. это 4 переменных на вход и все они по значению, а не по ссылке

_____________
матфак вгу и остальная классика =)

NewDeveloper

Mon, 08/23/2021 - 03:43

Длина массива всегда 100, поэтому функция принимает параметр n, в динамическом можно без n.

type
  ArrOfInt = array [1..100] of integer;
function check_length_xy(a1: ArrOfInt; n1, k1, y1: integer):integer;
var z: boolean;
    i1, x, c1: integer;
begin
 x := 1;
 c1 := k1;
 repeat
  z := false;
  for i1 := x to y1 do
   if a1[i1] = c1 then z := true;
  if z then c1 -= 1
  else
   begin
    x += 1;
    y1 += 1;
    c1 := k1;
   end;
 until (c1 = -1) or (y1 = n1 + 1);
 result := c1;
end;

var i, n, k, c, y, l: integer;
  a: ArrOfInt;
begin
  randomize();
  write('Введите длину массива не более 100: ');
  readln(n);
  k := random(n);
  for i := 1 to n do a[i] := random(k + 1);
  write('Массив: ');
  for i := 1 to n do write(a[i], ' ');
  writeln();
  writeln('k=', k);
  y := k + 1;
  l := k + 1;
  while true do
   begin
    c := check_length_xy(a, n, k, y);
    if c = -1 then break
    else l += 1;
    y += 1;
    if y = n + 1 then break;
   end;
  writeln();
  if c = -1 then writeln('Минимальная длина фрагмента равна: ', l)
  else writeln('Не найдены все числа в диапазоне 0 <= k');
  readln();
end.
vedro-compota's picture

vedro-compota

Tue, 08/24/2021 - 21:14

1)

while true do

-- уйти от такого условия, должно быть явное условие выхода

2) добавить решение с использованием функции, которая принимает на вход: сам массив, левую границу отрезка, правую границу отрезка, число k (значения от 0 до k мы ищем) + используемый выше ограничитель длины массива

3) можно ли в решении выше обойтись без z:

 repeat
  z := false;
  for i1 := x to y1 do
   if a1[i1] = c1 then z := true;
  if z then c1 -= 1
  else
   begin
    x += 1;
    y1 += 1;
    c1 := k1;
   end;
 until (c1 = -1) or (y1 = n1 + 1);

_____________
матфак вгу и остальная классика =)

NewDeveloper

Wed, 08/25/2021 - 19:55

Исправлены первый и второй пункт:

type
  ArrOfInt = array [1..100] of integer;    
function check_xy(a_1: ArrOfInt; x_1, y_1, k_1: integer): boolean;
var z: boolean;
    i, j: integer;
begin
 for i := 0 to k_1 do
  begin
   z := false;
   for j := x_1 to y_1 do
    if i = a_1[j] then
     begin
      z := true;
      break;
     end;
   if z = false then break;
  end;
 result := z;
end;

var n, k, x, y, l: integer;
  c: boolean;
  a: ArrOfInt;
begin
  randomize();
  write('Введите длину массива не более 100: ');
  readln(n);
  k := random(n);
  for x := 1 to n do a[x] := random(k + 1);
  write('Массив: ');
  for x := 1 to n do write(a[x], ' ');
  writeln();
  writeln('k=', k);
  x := 1;
  y := k + 1;
  l := y;
  repeat
   c := check_xy(a, x, y, k);
   if c then break;
   x += 1;
   y += 1;
   if y = n + 1 then
    begin
     l += 1;
     y := l;
     x := 1;
    end;
  until l > n;
  writeln();
  if c then writeln('Минимальная длина фрагмента равна: ', l)
  else writeln('Не найдены все числа в диапазоне 0 <= k');
  readln();
end.
vedro-compota's picture

vedro-compota

Sun, 08/29/2021 - 12:31

решение засчитано

_____________
матфак вгу и остальная классика =)