П'ятниця, 29.05.2020
Творча лабораторія

Навчальні посібники та робочі зошити з інформатики - якісно і дешево


Меню сайту
Реклама
Категорії каталогу
MS Visual C++ 2005 Express Edition [3]
Середовища програмування [8]
Особливості встановлення та використання різних середовищ програмування
MS Visual Basic 6 [1]
Microsoft Visual Basic
C# [8]
Програмування мовою C#
C++ [3]
Паскаль [5]
ЛОГО [1]
Олімпіадне програмування [0]
Python [1]
Головна » Статті » Програмування » Паскаль

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

Нові статті

[19.02.2020] [C#]
Задача про розрізання квадрата (ООП, C#)
[09.02.2020] [Python]
Задача про розрізання квадрата (ООП, Python)
[06.02.2020] [Паскаль]
Задача про розрізання квадрата (ООП, Free Pascal)

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

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

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

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

Задача

Клаптики. Квадрат, дві сторони якого лежать на координатних осях у першому координатному куті, розрізали в довільному місці по вертикалі або по горизонталі. Після цього з отриманими частинами 0 або більше разів виконали подібну операцію. Яка площа найбільшого клаптика?

 

 

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

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

Зразок вхідних даних Зразок вихідних даних
5 4
0 1 2 1
2 3 5 3
2 0 2 5
4 3 4 0
8

Ідея

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

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

Переглядатимемо список розрізів, перевіряючи щоразу, чи не можна черговим з них розрізати квадрат. Таким чином, зупинимось на третьому розрізі, який розділить початковий клаптик на 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#.


Интернет реклама
Категорія: Паскаль | Додав: teachlab (06.02.2020) | Автор: teachlab
Переглядів: 751 | Рейтинг: 0.0/0
Всього коментарів: 0
Додавати коментарі можуть тільки зареєстровані користувачі.
[ Реєстрація | Вхід ]
Форма входу
Пошук
Друзі сайту

Підтримка
Ви можете підтримати цей проект:

WMR164778923006
WMZ277001591405

Система Orphus

Маєте свій сайт?
Заробіть на ньому грошей!


Не маєте власного сайту?
Заробіть на обміні файлами!
Статистика
Copyright Пилипчук О.П. © 2020
div id=