Урок 15 (Решенная задача номер 15) - поиск фрагмента, отрезка в массиве, содержащего все числа

Primary tabs

Romakip's picture
Submitted by Romakip on Tue, 10/20/2020 - 16:22

Forums:

Урок 15 (Решенная задача номер 15)

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

type
    ArrOfInt = array[1..100] of integer;

var  N, k, m, p, i, o : integer;
        massiv : ArrOfInt;

function PoiskMinimalDlini(x : ArrOfInt; k, LevayGran, PravayGran : integer): integer;

var g, l, d : integer;
    Flag : boolean;
begin
  result := 0;
  Flag := false;
  d := - 1;
  for l := 0 to k do
    for g := LevayGran to PravayGran do
      if (x[g] = l) then
      begin
        Inc(d);
        break;
      end;
  Flag := d = k;
  g := 0;
  if (Flag = True) then
  for g := LevayGran to PravayGran do
    Inc(result);
end;

begin
  N := 10;
  k := 2;
  m := 0;
  p := k;
  o := 2;
  massiv[1] := 1;
  massiv[2] := 1;
  massiv[3] := 2;
  massiv[4] := 2;
  massiv[5] := 1;
  massiv[6] := 1;
  massiv[7] := 1;
  massiv[8] := 0;
  massiv[9] := 1;
  massiv[10] := 2;
  for i := 1 to N do
  write(massiv[i], ' ');
  while ((PoiskMinimalDlini(massiv, k, m, p) = 0)) do
  begin
    Inc(m);
    Inc(p);
    PoiskMinimalDlini(massiv, k, m, p);
    if (p = N) then
    begin
      m := 1;
      p := k + o;
      Inc(o);
    end;
  end;
  writeln('Minimalnay dlina ravna ', PoiskMinimalDlini(massiv, k, m, p));
end.

Key Words for FKN + antitotal forum (CS VSU):

  • Log in to post comments
  • 5695 reads

math2

Wed, 10/21/2020 - 21:29

Неправильно работает. Выводит

1 1 2 2 1 1 1 0 1 2 Minimalnay dlina ravna 5

Отрезок содержит все целые числа от 0 до 2:

0 1 2

Здесь минимальная длина равна 3.

Не обрабатывается ситуация, когда не все цифры от 0 до k содержатся в массиве.

Romakip's picture

Romakip

Thu, 10/22/2020 - 15:57 

type
    ArrOfInt = array[1..100] of integer;

var  N, k, m, p, i, o : integer;
        massiv : ArrOfInt;

function PoiskMinimalDlini(x : ArrOfInt; k, LevayGran, PravayGran : integer): integer;

var g, l, d : integer;
    Flag : boolean;
begin
  result := 0;
  Flag := false;
  d := - 1;
  for l := 0 to k do
    for g := LevayGran to PravayGran do
      if (x[g] = l) then
      begin
        Inc(d);
        break;
      end;
  Flag := d = k;
  g := 0;
  if (Flag = True) then
  for g := LevayGran to PravayGran do
    Inc(result);
end;

begin
  N := 10;
  k := 2;
  m := 0;
  p := k;
  o := 2;
  massiv[1] := 1;
  massiv[2] := 1;
  massiv[3] := 2;
  massiv[4] := 2;
  massiv[5] := 1;
  massiv[6] := 1;
  massiv[7] := 1;
  massiv[8] := 0;
  massiv[9] := 1;
  massiv[10] := 0;
  for i := 1 to N do
  write(massiv[i], ' ');
  while ((PoiskMinimalDlini(massiv, k, m, p) = 0)) do
  begin
    Inc(m);
    Inc(p);
    PoiskMinimalDlini(massiv, k, m, p);
    if (p > N) then
    begin
      m := 1;
      p := k + o;
      Inc(o);
    end;
  end;
  writeln('Minimalnay dlina ravna ', PoiskMinimalDlini(massiv, k, m, p));
end.

math2

Thu, 10/22/2020 - 16:25

Не обрабатывается ситуация, когда в массиве не все целые числа от 0 до k.

type
    ArrOfInt = array[1..100] of integer;
 
var  N, k, m, p, i, o : integer;
        massiv : ArrOfInt;
 
function PoiskMinimalDlini(x : ArrOfInt; k, LevayGran, PravayGran : integer): integer;
 
var g, l, d : integer;
    Flag : boolean;
begin
  PoiskMinimalDlini := 0;
  Flag := false;
  d := - 1;
  for l := 0 to k do
    for g := LevayGran to PravayGran do
      if (x[g] = l) then
      begin
        Inc(d);
        break;
      end;
  Flag := d = k;
  g := 0;
  if (Flag = True) then
  for g := LevayGran to PravayGran do
    Inc(PoiskMinimalDlini);
end;
 
begin
  N := 10;
  k := 2;
  m := 0;
  p := k;
  o := 2;
  massiv[1] := 1;
  massiv[2] := 1;
  massiv[3] := 1;
  massiv[4] := 1;
  massiv[5] := 1;
  massiv[6] := 1;
  massiv[7] := 1;
  massiv[8] := 1;
  massiv[9] := 1;
  massiv[10] := 1;
  for i := 1 to N do
  write(massiv[i], ' ');
  while ((PoiskMinimalDlini(massiv, k, m, p) = 0)) do
  begin
    Inc(m);
    Inc(p);
    PoiskMinimalDlini(massiv, k, m, p);
    if (p > N) then
    begin
      m := 1;
      p := k + o;
      Inc(o);
    end;
  end;
  writeln('Minimalnay dlina ravna ', PoiskMinimalDlini(massiv, k, m, p));
end.

Результат:
1 1 1 1 1 1 1 1 1 1 Minimalnay dlina ravna 105

Romakip's picture

Romakip

Thu, 10/22/2020 - 16:47 

type
    ArrOfInt = array[1..100] of integer;

var  N, k, m, p, i, o : integer;
        massiv : ArrOfInt;

function ProverkaNaNalicieVsehHicel( x : ArrOfInt; D, u : integer): boolean;

var g, l, m : integer;

begin
  m := - 1;
  for l := 0 to u do
    for g := 1 to D do
      if (x[g] = l) then
      begin
        Inc(m);
        break
      end;
  if (m = u) then
    result := true
  else result := false;
end;

function PoiskMinimalDlini(x : ArrOfInt; k, LevayGran, PravayGran : integer): integer;

var g, l, d : integer;
    Flag : boolean;
begin
  PoiskMinimalDlini := 0;
  Flag := false;
  d := - 1;
  for l := 0 to k do
    for g := LevayGran to PravayGran do
      if (x[g] = l) then
      begin
        Inc(d);
        break;
      end;
  Flag := d = k;
  g := 0;
  if (Flag = True) then
  for g := LevayGran to PravayGran do
    Inc(PoiskMinimalDlini);
end;

begin
  N := 10;
  k := 2;
  m := 0;
  p := k;
  o := 2;
  massiv[1] := 1;
  massiv[2] := 1;
  massiv[3] := 1;
  massiv[4] := 1;
  massiv[5] := 1;
  massiv[6] := 1;
  massiv[7] := 1;
  massiv[8] := 1;
  massiv[9] := 1;
  massiv[10] := 1;
  for i := 1 to N do
  write(massiv[i], ' ');
  if (ProverkaNaNalicieVsehHicel(massiv, N, k) = true) then
    while ((PoiskMinimalDlini(massiv, k, m, p) = 0)) do
    begin
      Inc(m);
      Inc(p);
      if (p > N) then
      begin
        m := 1;
        p := k + o;
        Inc(o);
      end;
    end
  else writeln('Ne vse cisla ot 0 do k');
  writeln('Minimalnay dlina ravna ', PoiskMinimalDlini(massiv, k, m, p));
end.

math2

Thu, 10/22/2020 - 17:10 

type
    ArrOfInt = array[1..100] of integer;
 
var  N, k, m, p, i, o : integer;
        massiv : ArrOfInt;
 
function ProverkaNaNalicieVsehHicel( x : ArrOfInt; D, u : integer): boolean;
 
var g, l, m : integer;
 
begin
  m := - 1;
  for l := 0 to u do
    for g := 1 to D do
      if (x[g] = l) then
      begin
        Inc(m);
        break
      end;
  if (m = u) then
    result := true
  else result := false;
end;
 
function PoiskMinimalDlini(x : ArrOfInt; k, LevayGran, PravayGran : integer): integer;
 
var g, l, d : integer;
    Flag : boolean;
begin
  PoiskMinimalDlini := 0;
  Flag := false;
  d := - 1;
  for l := 0 to k do
    for g := LevayGran to PravayGran do
      if (x[g] = l) then
      begin
        Inc(d);
        break;
      end;
  Flag := d = k;
  g := 0;
  if (Flag = True) then
  for g := LevayGran to PravayGran do
    Inc(PoiskMinimalDlini);
end;
 
begin
  N := 10;
  k := 2;
  m := 0;
  p := k;
  o := 2;
  massiv[1] := 1;
  massiv[2] := 2;
  massiv[3] := 1;
  massiv[4] := 1;
  massiv[5] := 1;
  massiv[6] := 1;
  massiv[7] := 1;
  massiv[8] := 1;
  massiv[9] := 1;
  massiv[10] := 0;
  for i := 1 to N do
  write(massiv[i], ' ');
  if (ProverkaNaNalicieVsehHicel(massiv, N, k) = true) then
    while ((PoiskMinimalDlini(massiv, k, m, p) = 0)) do
    begin
      Inc(m);
      Inc(p);
      if (p > N) then
      begin
        m := 1;
        p := k + o;
        Inc(o);
      end;
    end
  else writeln('Ne vse cisla ot 0 do k');
  writeln('Minimalnay dlina ravna ', PoiskMinimalDlini(massiv, k, m, p));
end.

Выводит

1 2 1 1 1 1 1 1 1 0 Minimalnay dlina ravna 3

Здесь минимальная длина равна 9.

Romakip's picture

Romakip

Thu, 10/22/2020 - 17:16 

type
    ArrOfInt = array[1..100] of integer;

var  N, k, m, p, i, o : integer;
        massiv : ArrOfInt;

function ProverkaNaNalicieVsehHicel( x : ArrOfInt; D, u : integer): boolean;

var g, l, m : integer;

begin
  m := - 1;
  for l := 0 to u do
    for g := 1 to D do
      if (x[g] = l) then
      begin
        Inc(m);
        break
      end;
  if (m = u) then
    result := true
  else result := false;
end;

function PoiskMinimalDlini(x : ArrOfInt; k, LevayGran, PravayGran : integer): integer;

var g, l, d : integer;
    Flag : boolean;
begin
  PoiskMinimalDlini := 0;
  Flag := false;
  d := - 1;
  for l := 0 to k do
    for g := LevayGran to PravayGran do
      if (x[g] = l) then
      begin
        Inc(d);
        break;
      end;
  Flag := d = k;
  g := 0;
  if (Flag = True) then
  for g := LevayGran to PravayGran do
    Inc(PoiskMinimalDlini);
end;

begin
  N := 10;
  k := 2;
  m := 1;
  p := k+1;
  o := 2;
  massiv[1] := 1;
  massiv[2] := 2;
  massiv[3] := 1;
  massiv[4] := 1;
  massiv[5] := 1;
  massiv[6] := 1;
  massiv[7] := 1;
  massiv[8] := 1;
  massiv[9] := 1;
  massiv[10] := 0;
  for i := 1 to N do
  write(massiv[i], ' ');
  if (ProverkaNaNalicieVsehHicel(massiv, N, k) = true) then
    while ((PoiskMinimalDlini(massiv, k, m, p) = 0)) do
    begin
      Inc(m);
      Inc(p);
      if (p > N) then
      begin
        m := 1;
        p := k + o;
        Inc(o);
      end;
    end
  else writeln('Ne vse cisla ot 0 do k');
  writeln('Minimalnay dlina ravna ', PoiskMinimalDlini(massiv, k, m, p));
end.
Romakip's picture

Romakip

Fri, 10/23/2020 - 13:41 

type
    ArrOfInt = array[1..100] of integer;

var  N, k, m, p, i, o : integer;
        massiv : ArrOfInt;

function ProverkaNaNalicieVsehHicel( x : ArrOfInt; D, u : integer): boolean;

var g, l, m : integer;

begin
  m := - 1;
  for l := 0 to u do
    for g := 1 to D do
      if (x[g] = l) then
      begin
        Inc(m);
        break
      end;
    result := m = u;
end;

function PoiskMinimalDlini(x : ArrOfInt; k, LevayGran, PravayGran : integer): integer;

var g, l, d : integer;
    Flag : boolean;
begin
  PoiskMinimalDlini := 0;
  Flag := false;
  d := - 1;
  for l := 0 to k do
    for g := LevayGran to PravayGran do
      if (x[g] = l) then
      begin
        Inc(d);
        break;
      end;
  Flag := d = k;
  if (Flag = True) then
  PoiskMinimalDlini := PravayGran - LevayGran + 1;
end;

begin
  N := 10;
  k := 2;
  m := 1;
  p := k+1;
  o := 2;
  massiv[1] := 1;
  massiv[2] := 1;
  massiv[3] := 1;
  massiv[4] := 1;
  massiv[5] := 1;
  massiv[6] := 2;
  massiv[7] := 1;
  massiv[8] := 1;
  massiv[9] := 1;
  massiv[10] := 0;
  for i := 1 to N do
  write(massiv[i], ' ');
  if (ProverkaNaNalicieVsehHicel(massiv, N, k) = true) then
    while ((PoiskMinimalDlini(massiv, k, m, p) = 0)) do
    begin
      Inc(m);
      Inc(p);
      if (p > N) then
      begin
        m := 1;
        p := k + o;
        Inc(o);
      end;
    end
  else writeln('Ne vse cisla ot 0 do k');
  writeln('Minimalnay dlina ravna ', PoiskMinimalDlini(massiv, k, m, p));
end.