|
|
« Предыдущая тема | Следующая тема » |
Опции темы | Опции просмотра |
|
|
|||||
Регистрация: Feb 2012
Сообщений: 36
|
Вхождение числового диапазона в другой числовой диапазон.
Подскажите, как проверить "пересекаются" ли числовые диапозоны А и В ? Скажем, A(5-8) B(6-10) == true, A(-1-4) B(-12 - -3) == false и .т.д
|
|
|||||
[+4 06.05.14]
|
что из себя прдеставляет числовой диапазон? Наверное массив или вектор, а занчит
__________________
Марк Tween |
|
|||||
Регистрация: Feb 2012
Сообщений: 36
|
in4core
Все гораздо примитивней Диапозон представлен двумя числами началом и концом. Первое число всегда меньше другого. Это, если угодно, отрезки на числовой оси и нужно проверить пересекаются ли они. Т.е. нужно условие для if(). |
|
|||||
Modus ponens
|
На самом деле задача решается за O(1), а не за O(n^2), как было предложено выше
На сравнение диапазонов можно посмотреть так: если нижняя граница одного из диапазонов больше верхней границы другого диапазона - тогда они не пересекаются. Во всех остальных случаях - пересекаются. Т.е. пусть диапазоны будут AB и A'B', тогда: A < B' ⋏ A' < B → диапазоны пересекаются. Для ваших примеров: 5 < 10 и 6 < 8 → истина -1 < -3 → ложь.
__________________
Hell is the possibility of sanity Последний раз редактировалось wvxvw; 07.07.2012 в 14:47. |
|
|||||
или как предложил wvxvw
что, конечно, правильней
__________________
Будь проще. Последний раз редактировалось KBAC; 07.07.2012 в 14:43. |
|
|||||
Регистрация: Jul 2007
Сообщений: 393
|
Еще надо проверить на то, что интервалы заданы верно, то есть (нижняя граница, верхняя граница)
Иначе не сработает. Второй вариант, который предложил KBAC, неверный. Последний раз редактировалось Krusty; 07.07.2012 в 20:22. |
|
|||||
Lorem ipsum
|
__________________
Поймай яблоко 2! |
|
|||||
Modus ponens
|
Чтобы опровергнуть формально валидное утверждение нужно продемонстрировать хтоя бы один случай, когда это утверждение не верно. Для этого рассмотрим все возможные случаи для интервалов AB и A'B'. В условии задачи уже было сказано, что A < B и A' < B', поэтому учитывать варианты, где это не происходит нам не нужно. Остается:
(1) Интервал AB целиком расположен перед A'B', другими словами: B < A'. (2) Интервал AB частично совпадает с A'B' таким образом, что A' принадлежит интервалу AB, другими словами: A' ≥ A && A' ≤ B. (3) Интервал AB полностью принадлежит интервалу A'B', другими словами: A ≥ A' && B ≤ B'. (4) Интервал AB полностью включает в себя интервал A'B', другими словами: A ≤ A' && B ≥ B'. (5) Интервал AB частично совпадает с интервалом A'B' таким образом, что B' принадлежит интервалу AB, а A' - нет. Другими словами, B' ≥ A && B' ≤ B. (6) Интервал AB полностью расположен за интервалом A'B', другими словами A > B'. Теперь мы можем объединить все случаи (не обращая внимание на то, что они симметричны, и нам нужна только половина - для простоты). У нас есть всего два случая, когда интервалы не имеют общих точек (1) и (6): (B < A') || (A > B') Воспользовавшись преобразованием де Моргана: !((B < A') || (A > B')) = (B ≥ A') && (A ≤ B') Что и требовалось доказать.
__________________
Hell is the possibility of sanity Последний раз редактировалось wvxvw; 08.07.2012 в 15:33. |
|
|||||
Цитата:
ну и имелись в виду диапазоны (a1, a2) и (b1, b2)
__________________
Будь проще. |
Часовой пояс GMT +4, время: 20:29. |
|
« Предыдущая тема | Следующая тема » |
|
|