2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Определить принадлежность точки отрезку.
Сообщение30.07.2011, 20:01 
Даны x1, x2 - начало и конец отрезка. Неупорядочены, т.е. может быть x1 > x2, а может быть и наоборот, а может быть и равенство. Также дан x3.
Определить, входит ли x3 в отрезок с концами в x1 и x2 за наименьшее количество операций, используя простые функции типа суммы, разности, сравнения, может быть модуля. (Подразумевается, что это в программе все делается на каком-то языке).
Какое наименьшее количество операций сравнения потребуется для выполнения задачи? Как найти наименьшее кол-во операций сравнения и обосновать? - это больше всего интересует.
Разумеется, интересует какой-нибудь не очевидный способ.

 
 
 
 Re: Определить принадлежность точки отрезку.
Сообщение30.07.2011, 21:50 
Аватара пользователя
Используется синтаксис Pascal
if (x1<x2)xor(x1<x3) then writeln('Принадлежит');

 
 
 
 Re: Определить принадлежность точки отрезку.
Сообщение30.07.2011, 22:23 
Используется синтаксис C++
if( (x3 - x1 ) * ( x3 - x2 ) <= 0 ) printf( "Принадлежит" );

меньше чем одним сравнением, наверное, уже не обойтись.

 
 
 
 Re: Определить принадлежность точки отрезку.
Сообщение30.07.2011, 22:30 
Аватара пользователя
Переехали в "Программирование".

 
 
 
 Re: Определить принадлежность точки отрезку.
Сообщение31.07.2011, 00:12 
ИСН в сообщении #472276 писал(а):
Используется синтаксис Pascal
if (x1<x2)xor(x1<x3) then writeln('Принадлежит');

Если даже не обращать внимания на то, что перепутаны x1 и x3, правая точка отрезка все равно пропадает - можно заменить на $(x3\leqslant x1<x2) \vee (x2\leqslant x1<x3)$:
x1=2,
x2=1,
x3=2
(2<1)xor(2<2) будет 0(FALSE)

 
 
 
 Re: Определить принадлежность точки отрезку.
Сообщение31.07.2011, 11:38 
Да, с граничными точками проблема в любом случае будет. Простейший вариант исправления:

Используется синтаксис Pascal
if ((x3<x2)<>(x3<x2)) OR (x3=x1) OR (x3=x2)
    then writeln('Принадлежит');

С умножением, конечно, выглядит короче. Однако бог знает, сколько лишнего времени отнимет само умножение. Кроме того, это зависит от реализации транслятора. Статистически вариант с арифметикой менее выгоден: в нём всегда будут необходимы четыре операции, а в лигическом варианте -- почти всегда три, и лшь изредка пять или семь. Можно ещё попробовать с ассемблером поковыряться, да чего-то лень.

 
 
 
 Re: Определить принадлежность точки отрезку.
Сообщение31.07.2011, 14:26 
ewert в сообщении #472365 писал(а):
С умножением, конечно, выглядит короче. Однако бог знает, сколько лишнего времени отнимет само умножение.

Можно и не умножать , просто сравнить "знаки" чисел. Получается наглядно и умножения не нужно.
Используется синтаксис Pascal
if(((sgn(x1-x2))<>(sgn(x1-x3)))then OK

 
 
 
 Re: Определить принадлежность точки отрезку.
Сообщение31.07.2011, 14:45 
PPrivett в сообщении #472397 писал(а):
Можно и не умножать , просто сравнить "знаки" чисел.

А что такое функция sgn?...

Если она возвращает только значения плюс-минус единичка, то это ровно то же самое, что и использование только логических выражений. Если возвращает ещё и ноль, то всё равно будет работать неверно для отрезка нулевой длины. И в любом случае: сколько дополнительно ресурсов сожрёт обращение к этой функции?...

 
 
 
 Re: Определить принадлежность точки отрезку.
Сообщение31.07.2011, 19:13 
ewert в сообщении #472401 писал(а):
PPrivett в сообщении #472397 писал(а):
Можно и не умножать , просто сравнить "знаки" чисел.

А что такое функция sgn?...

Если она возвращает только значения плюс-минус единичка, то это ровно то же самое, что и использование только логических выражений. Если возвращает ещё и ноль, то всё равно будет работать неверно для отрезка нулевой длины. И в любом случае: сколько дополнительно ресурсов сожрёт обращение к этой функции?...

Да, с нулевым отрезком плохо вышло :(

(Оффтоп)

sgn будет возвращать -1 0 +1, или 0 1 2 (главное чтобы 3 неравных числа). ресурсов сожрет меньше, чем умножение(реализовать можно через логические выражения,
либо используя двоичное представление числа - одно сравнение на равенство 0 и несколько битовых сдвигов. - учитывая, что первый бит знакового числа означает знак числа)
Хотя не факт, что будет работать быстрее. Для разных процессоров\компиляторов разные результаты будут

 
 
 
 Re: Определить принадлежность точки отрезку.
Сообщение01.08.2011, 21:47 
PPrivett в сообщении #472443 писал(а):
Да, с нулевым отрезком плохо вышло :(

(Оффтоп)

Нулевого отрезка не существует по определению http://ru.wikipedia.org/wiki/%D0%9E%D1% ... 0%BE%D0%BA

 
 
 
 Re: Определить принадлежность точки отрезку.
Сообщение01.08.2011, 22:41 

(Оффтоп)

Dmitriy_M в сообщении #472663 писал(а):
Нулевого отрезка не существует по определению http://ru.wikipedia.org/wiki/%D0%9E%D1% ... 0%BE%D0%BA

Вы прочитали из двух тамошних определений или неподходящее к данному случаю, или подходящее, но прочитали неверно.

 
 
 [ Сообщений: 11 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group