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

Primary tabs

Submitted by Aleksandr on Sun, 08/22/2021 - 12:01

Forums:

Задача 16 Урок 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 lesson15_16;
type
    myArr = array[1..9] of integer;

function check(a: myArr; k: integer): integer;
var
    b: boolean;
    i, j, p, q, l: integer;
begin
    for l := k to high(a) do            // увеличение [p,q] на 1
    begin
        p := 1;
        while p <= high(a) - l do       // сдвик [p,q] на 1
        begin
            q := p + l;
            for i := 0 to k do          // числа 0 до k
            begin
                b := false;
                for j := p to q do      // поиск числа из k в [p,q]
                    if i = a[j] then
                    begin
                        b := true;
                        break;
			        end;

			    if not b then
                begin
                    p := p + 1;
                    break;
		        end;
	        end;
            if b then
            begin
                result := l + 1;
                exit;
		    end
	    end;
    end;
    result := 0;
end;

var
    arr: myArr;
    k, i: integer;
begin
    k := 3;
    randomize();
    for i := low(arr) to high(arr) do
        arr[i] := random(3);

    for i := low(arr) to high(arr) do
        write(arr[i], '|');

    writeln();
    for i := 0 to k - 1 do
        write(i, '|');

    writeln();

    writeln(check(arr, k - 1));
    readln();
end.
  • Log in to post comments
  • 2734 reads
vedro-compota's picture

vedro-compota

Sun, 08/22/2021 - 12:15

  • Функция проверки конкретного отрезка

-- должна быть

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

Aleksandr

Tue, 08/24/2021 - 20:18 

program lesson15_16;
type
    myArr = array[1..10] of integer;

function check(a: myArr; k, q: integer; var p: integer): boolean;
var
    i, j: integer;
begin
    for i := 0 to k do          // числа 0 до k
    begin
        result := false;
        for j := p to q do      // поиск числа из k в [p,q]
            if i = a[j] then
            begin
                result := true;
                break;
            end;

        if not result then
        begin
            p := p + 1;
            break;
        end;
    end;
end;

var
    arr: myArr;
    k, i, p, q, result: integer;
begin
    k := 3;
    randomize();
    for i := low(arr) to high(arr) do
        arr[i] := random(k);

    for i := low(arr) to high(arr) do
        write(arr[i], '|');

    writeln();
    for i := 0 to k - 1 do
        write(i, '|');

    writeln();

    result := 0;
    for i := k - 1 to high(arr) do            // увеличение [p,q] на 1
    begin
        p := 1;
        while p <= high(arr) - i do           // сдвиг [p,q] на 1
        begin
            q := p + i;
            if check(arr, k - 1, q, p) then
            begin
                result := i + 1;
                break;
		    end;
	    end;
        if result > 0 then
            break;
    end;
    writeln(result);

    readln();
end.
vedro-compota's picture

vedro-compota

Tue, 08/24/2021 - 20:56 

function check(a: myArr; k, q: integer; var p: integer): boolean;

переделать без ссылки

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

Aleksandr

Sun, 08/29/2021 - 12:33 

program lesson15_16;
type
    myArr = array[1..10] of integer;

function check(a: myArr; k, p, q: integer): boolean;
var
    i, j: integer;
begin
    for i := 0 to k do          // числа 0 до k
    begin
        result := false;
        for j := p to q do      // поиск числа из k в [p,q]
            if i = a[j] then
            begin
                result := true;
                break;
            end;

        if not result then
            break;
    end;
end;

var
    arr: myArr;
    k, i, p, q, result: integer;
begin
    k := 3;
    randomize();
    for i := low(arr) to high(arr) do
        arr[i] := random(k);

    for i := low(arr) to high(arr) do
        write(arr[i], '|');

    writeln();
    for i := 0 to k - 1 do
        write(i, '|');

    writeln();

    result := 0;
    for i := k - 1 to high(arr) do            // увеличение [p,q] на 1
    begin
        for p := 1 to high(arr) - i do           // сдвиг [p,q] на 1
        begin
            q := p + i;
            if check(arr, k - 1, p, q) then
            begin
                result := i + 1;
                break;
		    end;
	    end;
        if result > 0 then
            break;
    end;
    writeln(result);

    readln();
end.
vedro-compota's picture

vedro-compota

Sun, 08/29/2021 - 12:38

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

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