UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75843
останнє поновлення: 2016-12-04
за 7 днів додано 15

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваМіра та периметр об’єднання прямокутників (реферат)
Авторdimich
РозділМатематика, алгебра, геометрія, статистика
ФорматWord Doc
Тип документуРеферат
Продивилось908
Скачало255
Опис
ЗАКАЧКА
Замовити оригінальну роботу

Реферат на тему:

 

Міра та периметр об’єднання прямокутників

 

Задача. Міра об’єднання інтервалів. Дано N інтервалів [a1, b1], [a2,

b2], ..., [aN, bN] на дійсній прямій. Необхідно знайти їх міру

об’єднання.

 

Відсортуємо абсциси a1, b1, a2, b2, ..., aN, bN у масиві X[1 : 2N], при

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

такою ж абсцисою: якщо ai розташовано в X[h], bj – в X[k] і ai = bj, то

h < k. Далі за лінійний час преглядається масив і обчислюється міра

об’єднання інтервалів.

 

Приклад. Нехай дано 5 інтервалів: {3,7},{2,5},{5,12}, {14,20},{5,13}.

 

Вони покривають інтервали від 2 до 13 та від 14 до 20, отже їх міра

дорівнює 11 + 6 = 17.

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14

15 16 17 18 19 20

 

Міра об’єднання інтервалів на осі

 

X[0] ? X[1];

 

m ? 0; /* міра об’єднання */

 

C ? 0; /* кількість інтервалів що перетинаються */

 

for i ? 1 to 2*N do

 

begin

 

if (C ??0) then m ? m + X[i] - X[i - 1];

 

if (X[i] – ліва кінцева точка) then C ? C + 1;

 

else C ? C - 1;

 

end;

 

Задача. e -близькість. Дано N + 1 дійсне число x1, x2, ..., xN та e > 0.

Чи знаходяться деякі два числа xi та xj на відстані, меншій за e одне

від іншого.

 

Теорема. Задача e -близькість лінійно зводиться до задачі міра

об’єднання інтервалів.

 

Доведення. Побудуємо інтервали [xi, xi + e] для i = 1, 2, ..., N, які

будуть входом для процедури міра об’єднання інтервалів. Результатом її

роботи буде значення m (міра). Жодні два числа з множини {x1, x2, ...,

xN} не будуть знаходитися на відстані, меншій за e одне від іншого тоді

і тільки тоді, коли m = N * e.

 

0

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ