Пилипчук О. П., вчитель фізики та інформатики Гаврилівської ЗОШ І-ІІІ ступенів Теофіпольського району Хмельницької області
Задача про розрізання квадрата (ООП, C#)
В шкільних програмах з інформатики останніх років з’явилось поняття “об’єктно-орієнтоване програмування”. Проте для багатьох вчителів, що мають досвід викладання учням основ процедурного програмування, виявляється складно перебудувати виклад так, щоб охопити обидві парадигми.
Спробую проілюструвати, як об’єктноорієнтований підхід можна використати під час розв’язування задачі, що пропонувалась на Хмельницькій обласній Інтернет-олімпіаді 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 менші:
А невикористаних розрізів стало на один менше:
Подальший алгоритм дій такий:
Доки не закінчились розрізи, для кожного з клаптиків шукати, чи не можна його розрізати; якщо можна — відрізаний клаптик додати до всіх, а розріз вилучити. Після цього вивести найбільшу площу клаптика.
Мовою C# це може виглядати так (основна частина):
while (RList.Count>0)
|
// Поки список розрізів RList не порожній...
|
foreach (Klaptik KL in KList.ToArray())
|
//... для кожного клаптика KL зі списку клаптиків KList...
|
foreach (Rozriz RZ in RList.ToArray())
|
//... перебирати розрізи в списку і...
|
if (KL.Rizaty(RZ, KList))
|
//... якщо поточний розріз RZ підходить до клаптика KL, то
відрізати клаптик K, ...
|
RList.Remove(RZ);
|
//... і вилучити RZ зі списку розрізів.
|
Примітка 1. В описаному вище алгоритмі списки клаптиків і розрізів у процесі їх перегляду зазнають змін (додаються нові клаптики, вилучаються використані розрізи). Оскільки список .NET не може бути змінений під час опрацювання в циклі foreach, для "обходу" цього обмеження в заголовках циклів створюються масиви копій елементів відповідних списків викликом метода ToArray.
Примітка 2. Описаний алгоритм можна покращити. Якщо під час перевірки чергового клаптика KL для нього не знайшлося жодного розрізу RZ, то:
- його варто вилучити зі списку KList - це прискорить подальшу роботу;
- перед вилученням слід запам'ятати його площу, оскільки вона може виявитися шуканою найбільшою площею.
Пропоную читачам виконати це вдосконалення програми самостійно.
Звичайно, програма запрацює, тільки якщо належним чином описати класи об’єктів і забезпечити введення та виведення даних, тому розглянемо повний її текст. Програма перевірена в середовищі програмування MonoDevelop версії 7.8.4.
Програма
Якщо з подальшого тексту вилучити нумеровані коментарі, отримаємо працездатну програму (принаймні, так було задумано :).
1. Додаємо необхідні простори назв:
using System;
using System.Collections.Generic; //простір назв, що містить шаблони списків
2. Відкриваємо простір назв нашої програми:
namespace klaptiki
{
3. Описуємо клас об’єктів для розрізів:
class Rozriz //клас Розріз
{
public readonly int x1, y1, x2, y2; //має певні координати кінців
4. У методі-конструкторі “Створення примірника класу Rozriz” для подальшого використання упорядковуємо кінці розрізів, спрямувавши розрізи: горизонтальний - зліва направо, вертикальний - знизу вгору:
public Rozriz(int xx1, int yy1, int xx2, int yy2) //створюється за 4 числами
{
x1= Math.Min(xx1, xx2);
y1= Math.Min(yy1, yy2);
x2= Math.Max(xx1, xx2);
y2= Math.Max(yy1, yy2);
}
}
5. Описуємо клас об’єктів для клаптиків:
class Klaptik //клас Клаптик
{
//має певні координати двох протилежних кутів
public int x1, y1, x2, y2;
//створюється за 4 числами
public Klaptik(int xx1, int yy1, int xx2, int yy2)
{
x1= xx1;
y1= yy1;
x2= xx2;
y2= yy2;
}
//якщо отримує підхожий розріз, то розрізається
//Вхідними параметрами метода “Розрізання клаптика” є розріз R і посилання на список для додання відрізаного клаптика:
public bool Rizaty(Rozriz R, List<Klaptik> Klst)
{
bool rez = false;//змінна-прапорець “Чи вдалось розрізати?”
//перевіряємо, чи підходить розріз до цього клаптика.
//ГОРИЗОНТАЛЬНИЙ розріз?
if ((R.x1 == x1) && (R.x2 == x2) && (R.y1 > y1) && (R.y1 < y2)) //горизонтальний розріз
{
//додаємо до Klst відрізаний клаптик
Klst.Add (new Klaptik(x1, y1, x2, R.y2));
//зменшуємо клаптик, який різали
y1 = R.y1;
//встановлюємо прапорець “Відрізано”
rez = true;
}
//ВЕРТИКАЛЬНИЙ розріз?
else if ((R.y1 == y1) && (R.y2 == y2) && (R.x1 > x1) && (R.x1 < x2)) //вертикальний розріз
{
Klst.Add (new Klaptik(x1, y1, R.x2, y2));
x1 = R.x1;
rez = true;
}
//повідомляємо на місце виклику, чи вдалось розрізати
return rez;
}
}
6. Основний клас:
class MainClass
{
public static void Main(string[] args)
{
7. Вводимо дані:
//вводимо довжину сторони квадрата і кількість розрізів
string[] P = Console.ReadLine().Split();
int L, N;
L = int.Parse(P[0]);
N = int.Parse(P[1]);
//Створюємо порожній список для клаптиків...
List<Klaptik> KList = new List<Klaptik>();
//...і додаємо до нього початковий квадрат.
KList.Add(new Klaptik(0, 0, L, L));
//Створюємо порожній список для розрізів...
for (int i=0; i< N; i++)
{
P = Console.ReadLine().Split();
//... і почергово додаємо до нього введені розрізи.
RList.Add(new Rozriz(int.Parse(P[0]), int.Parse(P[1]), int.Parse(P[2]), int.Parse(P[3])));
}
8. Реалізуємо розглянутий вище алгоритм:
while (RList.Count > 0)
foreach (Klaptik KL in KList.ToArray())
foreach (Rozriz RZ in RList.ToArray())
if (KL.Rizaty(RZ, KList))
RList.Remove(RZ);
9. Знаходимо в списку клаптик з найбільшою площею:
int S = 0;
foreach (Klaptik KL in KList)
S = Math.Max(S, (KL.x2 - KL.x1) * (KL.y2 - KL.y1));
10. Виводимо результат :) :
Console.WriteLine(S.ToString());
}
}
}
Перегляньте також розбір цієї ж задачі, проілюстрований мовами Pascal і Python.
Интернет реклама
