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

Задача. Міра об’єднання інтервалів. Дано 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 0. Чи знаходяться деякі два числа xi та xj на відстані, меншій за e одне від іншого.

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

Доведення. Побудуємо інтервали [xi, xi + e] для i = 1, 2, ..., N, які будуть входом для процедури міра об’єднання інтервалів. Результатом її роботи буде значення m (міра). Жодні два числа з множини {x1, x2, ..., xN} не будуть знаходитися на відстані, меншій за e одне від іншого тоді і тільки тоді, коли m = N * e.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать

Рефераты по информатике Задача. Міра об’єднання інтервалів. Дано N інтервалів [a1, b1], [a2, b2], ..., [aN, bN] на дійсній прямій. Необхідно знайти їх міру об’єднання.

Оценок: 545 (Средняя 5 из 5)

Наверняка у вас есть товары или услуги, продажа которых приносит вам максимальную прибыль. Для быстрого старта в сети вам необходимо создание посадочной страницы (одностраничного сайта), на которой будет размещена информация о маржинальных товарах/услугах интернет магазина. За 8 лет опыта разработки конверсионных страниц мы выработали оптимальную структуру, которая позволит привлекать через landing page больше продаж. На такую структуру «одевается» ваш контент — фирменный стиль, тексты, фотографии, уникальные торговые предложения, после чего страница выходит в свет. Разработка лендинга и запуск в сети — до 7 рабочих дней. Стоит отметить, что в разработку самой посадочной страницы входит и написание копирайтером продающих текстов для вашего бизнеса, чтобы каждый посетитель страницы захотел совершить покупку именно у вас. Результат: качественно разработаная продающая посадочная страница, которая готова приносить вам новых клиентов.