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

Primary tabs

Submitted by NikSo on Sat, 01/07/2023 - 15:22

Forums:

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

Дан массив длиной N (не более 100 элементов), состоящий из случайно выбранных чисел из диапазона от 0 до k, где 0≤k Найдите в этом массиве длину самого короткого фрагмента, который содержит все числа от от 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;
program u15z20;
type
  massiv = array[1..100] of integer;
var
  m: massiv;
  k,i,x,f,p,t,q: integer;

function f1 (m: massiv; a,b,c: integer): integer;
var
  z,j,q: integer;
begin
  for j:=0 to a do
  begin
    q:=0;
    for z:=b to c do    //проверка на отрезке
    begin
      if j=m[z] then
      q:=1;
    end;
      if q=0 then       //если не встретили число то выходим
        break;
   end;
   result:=q;
end;

procedure p1(var t,p,q,k,f :integer; m:massiv);
var i :integer;
begin
  t := 1;
  p := f;
  for i := low(m) to (high(m) - f) do
  begin
    q := f1(m,k,t,p);
    if q=1 then
    begin
      writeln('m = ', t, ' ', 'p = ', p);
      writeln('Dlina= ',(p-t)+1);  //отличие от задачи 19
      break;
    end
    else
    begin
      t := t + 1;
      p := p + 1;
    end;
  end;
end;

begin
  writeln('Vvedite k');
  readln(k);
  randomize();
  for i:=low(m) to high(m) do
  begin
    m[i] := random(k+1);
    write (m[i], ' ');
  end;
  q:=0;
  writeln;
  f:=k;        //отличие от задачи 19
  for i:=low(m) to (high(m)-f) do      //ищем короткий отрезок,если нет ищем длиннее
  if (q=0) and (f<=(high(m) - k)) then
  begin
    f:=f+1;
    p1(t,p,q,k,f,m);
  end
  else if q=0 then
  begin
    write ('No');
    break;
  end;
  readln();
end.
  • Log in to post comments
  • 914 reads
vedro-compota's picture

vedro-compota

Sun, 01/08/2023 - 14:18

  1. проверить форматирование
  2.   z,j,q: integer;
begin
  for j:=0 to a do
  begin
    q:=0;

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

  3. Оформить решение в виде одной функции + Прокомментировать назначение подпрограмм

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

NikSo

Fri, 01/27/2023 - 13:17 

program u15z20v2;
type
  massiv = array[1..100] of integer;
var
  m: massiv;
  k,i,x,f,p,t: integer;
  q:boolean;

function f1 (m: massiv; a,b,c: integer): boolean;   //ищем все числа в отрезке
var
  z,j: integer;
  q:boolean;
begin
  for j:=0 to a do
  begin
    q:=false;
    for z:=b to c do    //проверка на отрезке
    begin
      if j=m[z] then
        q:=true;
    end;
    if q=false then       //если не встретили число то выходим
      break;
  end;
  result:=q;
end;

procedure p1(var t,p,k,f :integer; q:boolean; m:massiv); //выводим результат либо сдвигаем отрезок для поиска
var i :integer;
begin
  t := 1;
  p := f;
  for i := low(m) to (high(m) - f) do
  begin
    q := f1(m,k,t,p);
    if q=true then                            //если все числа попадают,то выводим результат
    begin
      writeln('m = ', t, ' ', 'p = ', p);
      writeln('Dlina= ',(p-t)+1);
      break;
    end
    else                                   //если нет,то сдвигаем отрезок для поиска
    begin
      t := t + 1;
      p := p + 1;
    end;
  end;
  for i:=low(m) to (high(m)-f) do        //ищем коротнкий отрезок,если нет ищем длиннее
  begin
    if (q=false) and (f<=(high(m) - k)) then
    begin
      f:=f+1;                             //увеличиваем длину отрезка(в который могут попасть числа)
      p1(t,p,k,f,q,m);
    end
    else if q=false then
    begin
      write ('No');                      //если такого отрезка нет
      break;
    end;
  break;
  end;
end;

begin
  writeln('Vvedite k');
  readln(k);
  randomize();
  for i:=low(m) to high(m) do
  begin
    m[i] := random(k+1);
    write (m[i], ' ');
  end;
  writeln;
  q:=false;         //сначала берем самый короткий отрезок
  f:=k+1;
  p1(t,p,k,f,q,m);
  readln();
end.
vedro-compota's picture

vedro-compota

Sun, 01/29/2023 - 13:18

1)

procedure p1(var t,p,k,f :integer; q:boolean; m:massiv);

-- вернуть длину найденного отрезка и признак что он найден, т.е. только 2 переменные
максимум должны меняться по ссылке.

2) Переписать без рекурсивного вызова

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