А47

Задача:
Даны действительные положительные числа [latex]x[/latex], [latex]y[/latex], [latex]z[/latex].
а) Выяснить существует ли треугольник с длинами сторон [latex]x[/latex], [latex]y[/latex], [latex]z[/latex].
б) Если треугольник существует, то ответить — является ли он остроугольным?

NA — «not acute» — существует, но не остроугольный
A — «acute» — остроугольный
DE — «doesn’t exist» — не существует

[latex]x[/latex] [latex]y[/latex] [latex]z[/latex] Результат Комментарий:
3 4 5 NA Пройден: трегольник прямоугольный
1.30 3.86 5.14 NA Пройден
1.67 2.29 8 NE Пройден: нарушено условие (I)
811 22 790 NA Пройден: треугольник тупоугольный
10 11 12 A Пройден

Алгоритм:
I. Необходимым и достаточным условием существования треугольника с тремя заданными сторонами является условие вида:
[latex] x + y > z[/latex] (вырожденный случай не рассматривается)

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

II. Вид треугольника определяется углом, лежащим против большей стороны:
[latex]\alpha \in [ 0; \frac{ \pi }{ 2 } ]\Leftrightarrow \cos{(\alpha)}>0[/latex]

Знак косинуса угла легко определить через теорему косинусов:
[latex]z^{ 2 }=x^{ 2 }+y^{ 2 }-2xy\cos { (\alpha ) } \\ \cos { (\alpha ) } =\frac { x^{ 2 }+y^{ 2 }-z^{ 2 } }{ 2xy }[/latex]

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

Программное решение состоит из двух этапов:
0. Поиск наибольшей стороны.
1. Проверка условия (I).
2. Проверка условия (II).

Функция swap() взята из заголовочного файла algorithm.
В программе использован тип данных с плавающей точкой и двойной точностью (для отображения действительных чисел).
Для выполнения программы и проверки тестов можно воспользоваться следующим объектом. (реализация на Java)

Related Images:

11 thoughts on “А47

  1. В формулы у Вас закрались: разрыв строки < br / > и * (в мат. формулах умножение обозначается маленькой точкой или опускается).
    «Сортировка» у Вас не сортирует числа.
    Допустим для чисел 3 2 1 будет (шаги выполнения: 2 3 1, 2 1 3), результат 2 1 3. Почти что сортировка пузырьком, но последний шаг неверен. Впрочем Вам он и не нужен, ведь Вам нужно, чтобы z было максимальной из сторон.

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

    • Благодарю за замечания. Сортировку доработал (на ваших данных теперь даёт корректный результат) , формулы скорректировал в соответствии с правилами оформления.

  2. Молодец, повеселил жонглированием значениями переменных. Только один «бросок» в 12-й строке лишний. Объясните почему.

    Мне тоже захотелось пожонглировать. Что Вы скажете про такое условие:
    x + y + z > 2 * max(x, max(y, z))?
    Что оно по Вашему мнению проверяет?

    • То же самое, что и первая половина моей программы. Только в одну строку. ^^’ Спасибо, что показали такой вариант, я совсем забыл о функциях min() и max(). Теперь многие мои программы станут короче.
      Отчет и код программы привел в соответствие с более разумной формой решения.

    • Код по ссылке на ideone отличается от вышеприведенного и вообще не компилируется.

      Код же, который Вы изменили, для 811 22 790 выдает «The triangle is acute.» Похоже мы понемногу подходим к понятию регрессионного тестирования! Даже если первый вариант программы проходил все тесты, то после внесения изменений нужно провести тестирование опять.

      А вообще Игорь Евгеньевич поймал Вас в ловушку. Как Вы думаете для проверки ( x*x + y*y - z*z ) / ( 2*x*y ) важна упорядоченность переменных x,y,z? Или нет? Или важно некоторое условие? И вообще, Вы вычислили косинус, а где Вы его сравнили с нулем?

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

    • Да, я и не думал ловушки ставить. Я не коварный.
      Я подозревал, что может возникнуть желание проверить остроугольность треугольника в таком же ключе. Но так: пусть t = max(x, max(y, z)), тогда ( x*x + y*y + z*z — 2*t*t ) / ( 2*x*y*z)*t решит задачу без «сортировок».
      Я не говорю, что так лучше. Просто продолжаю жонглировать 🙂

  3. Упорядоченность x,y,z в Ваше программе не важна.
    Важно только, чтобы z была большей из сторон.

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

    В Вашем случае, если совсем коротко: строку 12 тоже нужно/можно выбросить.

    • Желание возникало, но к ночи я забыл как думать, к сожалению.
      Реализовал я оба варианта ( http://ideone.com/xAFy92 ), но в отчет вставил тот, который показался мне более очевидным. Обе версии программы прошли все указанные тесты.
      Ваш вариант оказался несколько неожиданным, хотя и красивым, я его запомнил. И почитал о реализации функций из заголовочного файла algorithm, чтобы выяснить, что работает быстрее и почему. В данной задаче заметного приращения в быстродействии я не заметил, но при работе с данными действительно проще найти максимальный элемент.

  4. Я не смотрел, какой вариант быстрее.
    Если есть желание протестировать, то нужно вставить все вычисления в цикл с большим количеством повторений. Можно варьировать исходные данные.
    Перед циклом и после него вывести время наиболее точной функцией.
    Правда останется ещё много неучтённых факторов, но общее представление можно будет получить.
    В будущем мы научимся пользоваться профайлером, что возможно несколько облегчит Вам задачу анализа быстродействия.

  5. Засчитана Java версия.
    Правда, немного странно смотрится сочетание строк import java.util.*; и java.util.Arrays.sort(s);. Т.е. import есть, но не используется.

Добавить комментарий