Mif 17.17

Условие :

Принадлежит ли точка [latex](x[/latex];[latex]y)[/latex] фигуре на рисунке? Варианты 1-20. Пожалуйста повторите в своём отчёте рисунок, выполнив его в формате SVG.

Рисунок :

picture

Тесты :

[latex]x[/latex] 4 -5 0 3 -2.5 1 -3 2 -1.3
[latex]y[/latex] 3 0 -5 -2 -2.5 5 3 -4 2.7
Вывод : Yes Yes Yes Yes Yes No No No Yes

Решение :

Во [latex]II[/latex], [latex]III[/latex] и [latex]IV[/latex] координатных четвертях данная фигура удовлетворяет неравенству [latex]|x| + |y| \leq 5[/latex], а в [latex]IV[/latex] — неравенству [latex]x^2 + y^2 \leq 25[/latex]. Программа должна проверять, подходят ли числа [latex]x[/latex] и [latex]y[/latex] соответствующему неравенству (в зависимости от координатной четверти, в которой они находятся).

Код :

Рабочая версия кода на Ideone.

Mif 17.4

Настя Ивасенко
Настя Ивасенко

Latest posts by Настя Ивасенко (see all)

Условие задачи (17.4)

Условие

Принадлежит ли точка [latex](x;y)[/latex] фигуре на рисунке? Пожалуйста повторите в своём отчёте рисунок, выполнив его в формате SVG.

123

Тесты

x y Ответ
4 3 yes
1 4 yes
2 2 no
6 2 no
-1 0 no

Решение

Точки, которые принадлежат ромбу, находятся между линиями, которые создают этот ромб.

Можно заметить, что эти сумма координат этих точек находится в сегменте между [latex]5[/latex] и [latex]11[/latex]:

  •  [latex]5\leq x+y\leq 11[/latex];

Их разность в сегменте  от  [latex]-3[/latex]  до [latex]3[/latex]:

  •   [latex]-3\leq x-y\leq 3[/latex];

Если сумма или разность данных координат больше или меньше заданых чисел, то точка не принадлежит ромбу.

 

Код

Код на IDEONE

А58г

Швандт Максим Альбертович
Швандт Максим Альбертович

Latest posts by Швандт Максим Альбертович (see all)

 Задача: Дано действительное число  [latex]a[/latex]. Для функции  [latex]f(x)[/latex], график которой представлен на рисунке, вычислить  [latex]f(a)[/latex].
График:
a
Тесты:

a f(a)
1 1
3.2 -0.015371
6 -0.027469
0 0
-1 1
-2.5 2.5
1.5 1
1.8 1
1.001 1

Код программы:

Код программы на языке Java:

Ссылка:http://ideone.com/e6UFys

Результат вычисляем по формуле:
[latex]y = ka + b[/latex] Программа состоит из следующих частей:

  1. Объявление переменных a, y, k, b типа float для хранения данных
  2. Ввод пользователем значений переменной а с помощью scanf
  3. Вычисление и вывод результата по формуле с предварительным сравнением значения а
  4. Завершение программы

Программа сравнивает значение переменной [latex]a[/latex] с значениями переменной [latex]x[/latex] на четырёх диапазонах, и в зависимости от диапазона использует для функции [latex]y = ka + b[/latex] нужные значения [latex]k[/latex] и [latex]b[/latex]. Так вычисляется [latex]f(a)[/latex].
Ссылка на ideone.com : http://ideone.com/N2toyp

Образец: Принадлежит ли точка треугольнику?

Мазурок Игорь Евгеньевич

Мазурок Игорь Евгеньевич

Разработчик программного и информационного обеспечения.
Доцент Одесского национального университета имени И.И.Мечникова
Учёный в области защиты и противодейтствия в интеллектуальных информационных системах
Мазурок Игорь Евгеньевич

Latest posts by Мазурок Игорь Евгеньевич (see all)

Задача. Даны три попарно не совпадающие и не лежащие на одной прямой точки [latex]A, B[/latex] и [latex]C[/latex], заданные своими координатами. Определить принадлежит ли точка [latex]D(x_d,y_d)[/latex] треугольнику [latex]ABC[/latex].
Сразу заметим, что задача легко обобщается для любого выпуклого многоугольника.

Тесты

В тестах нужно обязательно отразить следующие случаи:

  1. Точка строго вне треугольника
  2. Точка строго внутри треугольника
  3. Точка совпадает с одной из вершин треугольника
  4. Точка лежит на одной из сторон треугольника
  5. Точка лежит на продолжении одной из сторон треугольника
  6. Одна из сторон треугольника параллельна одной из осей координат
  7. Две стороны треугольника параллельны осям координат
xa ya xb yb xc yc xd yd Принадлежит?
-1 -1 1 -1 0 1 2 2 нет
-2 -2 1 -1 0 1 0 0 да
-1 -1 1 -1 0 1 0 1 да
-1 -1 1 -1 0 1 0.5 0 да
-1 -1 1 -1 0 1 1 3 нет
-1 -1 1 -1 0 1 0 0 да
0 0 2 0 0 2 1 1 да
0 0 2 0 0 2 5 5 нет

Плохое решение

В школьных учебниках такие задачи часто рекомендуют решать проверкой условия [latex]S_{ABC}=S_{ABD}+S_{BCD}+S_{CAD}[/latex]. При компьютерной реализации это приводит к необходимости сравнения двух действительных чисел на равенство. Эта крайне неприятная операция может быть проделана только с определённой степенью достоверности. Т.е. придётся проверять не превышает ли некоторого «с потолка» выбранного малого числа абсолютное [latex] \left| S_{ABD}+S_{BCD}+S_{CAD}-S_{ABC} \right| < \varepsilon[/latex] или относительное [latex]\left| 1-\frac{S_{ABD}+S_{BCD}+S_{CAD}}{S_{ABC}} \right| < \varepsilon[/latex] отклонение. Оставим эти вопросы для курса численных методов и методов приближённых вычислений и не будем идти по этому пути.

Неплохое решение

Начнём с простого наблюдения:

Все точки треугольника (и любого выпуклого многоугольника) должны лежать по одну сторону от прямой, проходящей через каждую его сторону.

Запишем уравнение прямой, проходящей, например, через точки [latex]A[/latex] и [latex]B[/latex]. Получим [latex] \left( x-x_A \right) \left( y_B-y_A \right)-\left( y-y_A \right) \left( x_B-x_A \right) = 0[/latex]. Уравнение я записал в такой форме, чтобы не приходилось выполнять деление и переживать о нуле в знаменателе.

Неважно как называть стороны, важно научиться их различать.

Неважно как называть стороны, важно научиться их различать.

Теперь для любой точки [latex] \left( x;y \right)[/latex] мы можем вычислить левую часть приведенного равенства. Для точек, лежащих на прямой мы должны получать ноль. В тоже время прямая разобьёт плоскость на две полуплоскости. Точки лежащие в одной полуплоскости будут давать положительные значения. А точки из другой полуплоскости — отрицательные.
Мы готовы проверить первое условие — принадлежит ли точка [latex]D \left( x_d,y_d \right) [/latex] той же полуплоскости, что и точка [latex]C \left( x_c,y_c \right) [/latex] относительно прямой [latex] \left( AB \right) [/latex]? Для этого подставим обе точки в левую часть приведенного выше уравнения прямой и убедимся, что получены значения одного и того же знака. А если одна из точек даст точно ноль? Это означает, что точка лежит на прямой. По условию задачи это может быть только точка [latex]D[/latex]. Тогда она принадлежит треугольнику независимо от знака выражения, вычисленного для точки [latex]C[/latex].

Обратите внимание, что мы не утверждаем, что для любой точки на прямой наши приближённые вычисления обязаны дать точный ноль. Это было бы неверно. Мы только утверждаем, что если проведенные с доступной нам точностью вычисления всё же дали точный ноль, то мы вынуждены считать данную точку лежащей на данной прямой.

Естественно, что нам придётся записать аналогичные условия для двух оставшихся сторон треугольника (или для всех оставшихся сторон выпуклого многоугольника).

Плохой код

Начнём с того, что объявим переменные и прочитаем их значения. После этого запишем одно очень громоздкое условие, которое и проверяет принадлежность.

Нажмите здесь, чтобы выполнить этот код.

Приведенный код имеет существенные недостатки. Нам пришлось трижды записывать уравнение прямой проходящей через две точки и дважды подставлять в каждое из них координаты, чтобы проверить знак. Это значит, что нам пришлось шесть раз написать некоторую формулу с различными подстановками. При том подходе, что мы использовали имеем две проблемы. Во-первых, условие стало слишком сложным, чтобы его можно было легко воспринять. Во-вторых, и это гораздо хуже, такой код в [latex]\frac { 1-{ \left( 1-p \right) }^{ 6 } }{ p }[/latex] раз увеличивает вероятность совершить ошибку. Забавно, но это означает, что вероятность ошибки начинающего программиста увеличивается вдвое, а у опытного — в шесть раз. Хорошо, что опытные программисты не пишут такой код.

Неплохой код

Воспользуемся тем, что мы уже умеем создавать собственные функции для того, чтобы несколько сократить объём кода и сделать его более лёгким для восприятия.
Запишем условие на языке программирования С++:

Нажмите здесь, чтобы выполнить этот код.
Трудно сказать, стал ли код боле понятным или лаконичным. Однако можно точно сказать, что в нём отсутствуют повторяющиеся алгоритмические блоки. Все участки кода написаны строго по одному разу. Это уменьшает вероятность ошибки.

Чеширский код

Этот код содержит пока не изученные вами конструкции. Из-за этого он может показаться немного загадочным. Но если продолжать грызть гранит науки, то всё легко освоите. Или можно подождать...

Этот код содержит пока не изученные вами конструкции. Из-за этого он может показаться немного загадочным. Но если продолжать грызть гранит науки, то всё легко освоите. Или можно подождать…

Возможно слишком смело называть это хорошим кодом, но мы сделаем ещё один шаг в нужном направлении. В прошлом коде мы избавились от повторов в кодировании алгоритма. Однако остались повторы в кодировании данных. Вы заметили, что у нас четыре пары переменных? Т.е. просматривается структура состоящая из пары координат x и y, которую стоит объединить и назвать «точкой». Такие структуры в программировании на Си описывают с помощью ключевого слова struct. Это полезная промежуточная структура перед переходом к объектно-ориентированному программированию при помощи классов.

Нажмите здесь, чтобы выполнить этот код.
Вы заметили как забавно увеличивается размер программы по мере того, как мы пытаемся сделать его более логичным и наглядным? Это характерно для маленьких программ. Такие дополнительные структуры становятся всё более оправданными для больших и огромных программ.

А59г

Танащук Григорій Русланович
Танащук Григорій Русланович

Latest posts by Танащук Григорій Русланович (see all)

ЗАДАЧА: Даны действительные числа [latex]{x},{y}[/latex]. Определить принадлежит ли точка с координатами [latex]{x},{y}[/latex] заштрихованной части плоскости.

А59гЗаштрихован  ромб с координатами [latex]{A}(1.0),{B}(0.1),{C}(-1.0),{D}(0.-1)[/latex]

27 41 не принадлежит
0.1 -0.2 принадлежит
-2 -3 не принадлежит
    1. Задали значения через scanf;
    2. Вывели на печать проверку принадлежности точки;
    3. Получили ответ принадлежит ли точка ромбу.
      ссылка на программу http://ideone.com/x1p0Dp