windows-1251 По просьбе одного пряника.. - Пвфеямв
18.05.2005

По просьбе одного пряника..

Задачка. Написать условие пересечения двух интервалов, используя минимальное количество сравнений. Дабы не было всяких заумностей, сразу скажу, что известно, кто у интервала право, кто лево :)

задачки
18.05.2005 15:58:00 Вовка
Если задача звучит «написать условие вхождения отрезка [AB] в отрезок [CD]», то это обычный двойной if

Если 2 произвольных отрезка и не понятно кто в кого может «входить», то это четверной if
KIM
требуется написать условие пересечения интервалов, а не полного вхождения одного в другой.
18.05.2005 17:04:00 Stalker
Есть мнение (мое), что это можно сделать в одно сравнение (хотя я конечно не уверен).

Пусть a1, a2 — начало и конец первого интервала, а b1, b2 — начало и конец второго. Тогда, если sign(b2-a1)!=sign(b1-a2), то интервалы пересекаются, где функция sign — функция взятия знака у числа.

Без сравнений функция sign может быть приблизительно такой:
int sign(int i) {
    return i & 0x080000000;
}
KIM
принцип, в общем, верный, но работать так будет только для целых чисел. кроме того, где в вопросе сказано про машинную реализацию?
18.05.2005 17:44:00 Stalker
Для отрицательных, а также дробных чисел тоже работает. Без машинной реализации ещё проще: «если разница конца второго и начала первого интервала, отличается знаком от разницы начала второго и конца первого интервала, то интервалы пересекаются».
KIM
спорный момент. определение знака означает сравнение с нулем.
18.05.2005 18:26:00 Stalker
Определение знака вовсе не означает сравнение с нулем. Более того, как было показано выше, это вообще не означает наличия сравнения. С точки зрения человеческой логики, сравнения «не равно» и «отличаются знаком» вообще эквивалентны.

Машинный вариант я привел. Сдавайся. Одно сравнение — это правильный ответ.
KIM
1) машинный вариант не работает с нецелыми числами
2) не равны не значит отличаются знаком
3) не отличаются знаком не означает равенства
4) сравнение чисел эквивалентно определению знака их разности
18.05.2005 19:01:00 Stalker
Мне что сюда шаблон накатать? Слово «приблизительно» ни о чем не говорит? Тот же принцип работает и для дробных чисел.

Кроме того, «где в вопросе сказано про машинную реализацию?»

Остальные пункты вообще не понятны.
KIM
просто было бы неплохо определиться с функцией sign. ты используешь математическую или собственную?
математическое определение функции sign включает в себя сравнения. а твой вариант не работает даже для целых аргументов. ошибка в логике и не связана с реализацией. кто найдет ошибку - 5 в полугодии :) кстати, неплохая задачка для тестеров.
остальные пункты:
2 и 3: если не знашь значения слова
18.05.2005 22:48:00 GSA
И вообще, даже если принять твой вариант (а ошибку мы обязательно найдем, если есть :-)), то он работает только для интервалов (открытых отрезков), а для замкнутых - уже нет. А общепринятый вариант работает всегда.
Stalker
Уважаемый, ты условие то перечитай, да. А потом уже таки ошибку ищи. Я не спорю, может и есть ошибка. Но явно не в том, что вы пишите.
18.05.2005 23:55:00 Stalker
Уважаемый KIM! Надоело дискутировать, чесс-слово. Поверь мне, на данном уровне развития компьютерной техники, независимо от твоих аругментов и значения интервальных ограничений возможно написать функцию (sign), которая будет возвращать знак числа (в том или ином виде) не применяя операции сравнения. Ну так уж компьютеры устроены, я не виноват. Более того, в паскакале вообще эта функция встроена.

Как уже было написано выше, задача вообще не «про машинную реализацию», «человеческую» я написал, тоже в одно сравнение.

Нравится написание «ошибка в логике». Это у программы на C ошибка в логике что-ли? Кроме того (наверное это прозвучало не очень понятно), было написано фраза «приблизительно». Ни что не мешает написать шаблонный класс для любого типа числа, который, сюрприз правда, будет работать по сходному принципу (оставляю в качестве домашнего задания).
KIM
ошибка не в программе, абсолютно не связана ни со средством, ни с приблизительностью реализации. ошибка в методе. мне даже все равно, является определение знака сравнением или нет (хотя остаюсь при своем мнении). ошибка даже не зависит от определения функции sign. готов сделать ставку :)
19.05.2005 12:26:00 gsa
А чего мне условие перечитывать, если я же его и формулировал? :-)
Каюсь, сформулировал не совсем четко. Так вот, повторюсь. Даже если для открытых отрезков твой способ и работает, для замкнутых он работать не будет. Что показывает его несовершенность по сравнению с общепринятым решением.
Stalker
Криво сформулировал значит, учи Албанский. Почему не будет работать — непонятно. Либо пример, либо в Бобруйск.

Термин «интервал» от «отрезка» отличаем, да?
19.05.2005 14:31:00 GSA
Отличаем. :-) Интервал - открытый отрезок. Но изначально задача была для замкнутых.
Пример - пожалуйста. a1=a2=b1=b2.
Stalker
Я тебе поэтому и предлагал вчера перечитать условие. В нем про интервал, а не про отрезок. Поэтому на эту задачу ответ — одно сравнение. То что выше написал тоже будет работать, потому как интервалы, где a1=a2=b1=b2 они того, не пересекаются.
Пожалуйста представьтесь Электропочта Записать