Пилипчук О. П., вчитель фізики та інформатики Гаврилівської ЗОШ І-ІІІ ступенів Теофіпольського району Хмельницької області

Задача про розрізання квадрата (ООП, Free Pascal)

В шкільних програмах з інформатики останніх років з’явилось поняття “об’єктно-орієнтоване програмування”. Проте для багатьох вчителів, що мають досвід викладання учням основ процедурного програмування, виявляється складно перебудувати виклад так, щоб охопити обидві парадигми.

Спробую проілюструвати, як об’єктноорієнтований підхід можна використати під час розв’язування задачі, що пропонувалась на Хмельницькій обласній Інтернет-олімпіаді 2019 року.

Задача

Вхідні дані. У першому рядку стандартного вхідного потоку записано два цілі числа, відокремлені пропуском, — довжина сторони квадрата L і кількість розрізів N. У наступних N рядках записано по 4 цілі числа x1_i, y1_i, x2_i, y2_i, відокремлені пропусками,— координати кінців i-го розрізу. Розрізи перелічені в довільному порядку.

Вихідні дані. У стандартний вихідний потік вивести одне ціле число — найбільшу площу клаптика.

Ідея

Спочатку ми маємо один квадратний клаптик:

і певний набір відрізків, які далі називатимемо розрізами:

Переглядатимемо список розрізів, перевіряючи щоразу, чи не можна черговим з них розрізати квадрат. Таким чином, зупинимось на третьому розрізі, який розділить початковий клаптик на 2 менші:

А невикористаних розрізів стало на один менше:

Подальший алгоритм дій такий:

Доки не закінчились розрізи, для кожного з клаптиків шукати, чи не можна його розрізати; якщо можна — відрізаний клаптик додати до всіх, а розріз вилучити. Після цього вивести найбільшу площу клаптика.

Мовою Object Pascal це може виглядати так (основна частина):

while RList.Count>0 do

begin

Поки список розрізів RList не порожній...

  for KL in KList do begin

//... для кожного клаптика KL зі списку клаптиків KList...

    for RZ in RList do

//... перебирати розрізи в списку і...

      if KL.Rizaty(RZ,K)

//... якщо поточний розріз RZ підходить до клаптика KL, то
відрізати клаптик K, ...

      then begin

//... після чого...

        KList.Add(K);

//... додати K до списку клаптиків,...

        RList.Remove(RZ);

//... вилучити RZ зі списку розрізів.

      end;

  end;

end;

Примітка 1. Описаний алгоритм можна покращити. Якщо під час перевірки чергового клаптика KL для нього не знайшлося жодного розрізу RZ, то:

• його варто вилучити зі списку KList - це прискорить подальшу роботу;
• перед вилученням слід запам'ятати його площу, оскільки вона може виявитися шуканою найбільшою площею.

Пропоную читачам виконати це вдосконалення програми самостійно.

Звичайно, програма запрацює, тільки якщо належним чином описати класи об’єктів і забезпечити введення та виведення даних, тому розглянемо повний її текст. Програма перевірена в середовищі програмування Lazarus з компілятором Free Pascal версії 3.0.4.

Програма

Якщо з подальшого тексту вилучити нумеровані коментарі, отримаємо працездатну програму (принаймні, так було задумано :).

program project1;

{$mode objfpc}

1. Додаємо необхідні модулі:

uses     fgl, //модуль, що містить шаблон списку TFPGObjectList

            math; //модуль, що містить функції min і max

2. Оголошуємо класи об’єктів для розрізу і клаптика:

type

    rozriz=class //клас Розріз

        //має певні координати кінців

        x1,y1,x2,y2:integer;

        //створюється за 4 числами

        public constructor Create(xx1,yy1,xx2,yy2:integer);

    end;

    klaptik=class //клас Клаптик

        //має певні координати двох протилежних кутів

        x1,y1,x2,y2:integer;

        //створюється за 4 числами

        public constructor Create(xx1,yy1,xx2,yy2:integer);

        //якщо отримує підхожий розріз, то розрізається

        function Rizaty(r:rozriz;var k:klaptik):boolean;

    end;

3. Оголошуємо типи списків для клаптиків і розрізів на основі шаблонів

    //тип — список клаптиків

    TKList=specialize TFPGObjectList<klaptik>;

    //тип — список розрізів

    TRList=specialize TFPGObjectList<rozriz>;

4. Реалізуємо метод-конструктор “Створення примірника класу rozriz”. Для подальшого використання упорядковуємо кінці розрізів, спрямувавши розрізи: горизонтальний - зліва направо, вертикальний - знизу вгору:

constructor rozriz.Create(xx1,yy1,xx2,yy2:integer);

begin

    x1:=min(xx1,xx2);

    y1:=min(yy1,yy2);

    x2:=max(xx1,xx2);

    y2:=max(yy1,yy2);

end;

5. Реалізуємо метод-конструктор “Створення примірника класу klaptik”:

constructor klaptik.Create(xx1,yy1,xx2,yy2:integer);

begin

    x1:=xx1;

    y1:=yy1;

    x2:=xx2;

    y2:=yy2;

end;

6. Реалізуємо метод “Розрізання клаптика”. Вхідними параметрами для нього є розріз R і посилання на змінну K для відрізаного клаптика:

function klaptik.Rizaty(R:rozriz;var K:klaptik):boolean;

var rez:boolean; //змінна-прапорець “Чи вдалось розрізати?”

begin

    rez:=false;

    //перевіряємо, чи підходить розріз до цього клаптика.

    //ГОРИЗОНТАЛЬНИЙ розріз?

    if (R.x1=x1) and (R.x2=x2) and (R.y1>y1) and (R.y1<y2)

    then begin

        //записуємо в K відрізаний клаптик

        K:=klaptik.Create(x1,y1,x2,R.y2);

        //зменшуємо клаптик, який різали

        y1:=R.y1;

        //встановлюємо прапорець “Відрізано”

        rez:=true

    end

    //ВЕРТИКАЛЬНИЙ розріз?

    else if (R.y1=y1) and (R.y2=y2) and (R.x1>x1) and (R.x1<x2)

        then begin

            k:=klaptik.Create(x1,y1,R.x2,y2);

            x1:=R.x1;

            rez:=true

        end;

    //повідомляємо на місце виклику, чи вдалось розрізати

    Rizaty:=rez

end;

7. Оголошуємо змінні, зокрема списки для клаптиків і розрізів:

var L,N,i,x1,y1,x2,y2,S:integer;

    //список клаптиків

    Klist:TKList;

    //список розрізів

    Rlist:TRList;

    K,KL:klaptik;

    RZ:rozriz;

8. Вводимо дані:

begin

    readln(L,N);

    //Створюємо порожній список для клаптиків...

    Klist:=TKList.Create;

    //...і додаємо до нього початковий квадрат.

    Klist.Add(klaptik.Create(0,0,L,L));

    //Створюємо порожній список для розрізів...

    RList:=TRList.Create;

    for i:=1 to N do begin

        readln(x1,y1,x2,y2);

        //... і почергово додаємо до нього введені розрізи.

        Rlist.Add(rozriz.Create(x1,y1,x2,y2));

    end;

9. Реалізуємо розглянутий вище алгоритм:

    while RList.Count>0 do begin

        for KL in KList do begin

            for RZ in RList do

                if KL.Rizaty(RZ,K)

                then begin

                    KList.Add(K);

                    RList.Remove(RZ);

                end;

        end;

    end;

10. Знаходимо в списку клаптик з найбільшою площею:

    S:=0;

    for KL in KList do

        S:=max(S,(KL.x2-KL.x1)*(KL.y2-KL.y1));

11. Виводимо результат :) :

    writeln(S);

end.

Перегляньте також розбір цієї ж задачі, проілюстрований мовами Пайтон (Python 3) і C#.