Задача:
Даны действительные положительные числа [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 | Пройден |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include #include using namespace std; int main() { double x, y, z; scanf( "%lf %lf %lf", &x, &y, &z ); //find the longest side if ( x > y ) swap( x, y ); if ( y > z ) swap( y, z ); //if the triangle exists if( x + y > z ) { //if it is acute double COS_VALUE = ( x*x + y*y - z*z ) / ( 2*x*y ); if( COS_VALUE > 0 ) printf( "The triangle is acute." ); else printf( "The triangle is not acute." ); } else printf( "The triangle doesn't exist." ); return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
import java.util.*; import java.lang.*; import java.io.*; import java.math.*; import java.text.*; class Triangles { public static double square(double num){ return num*num; } public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); double s[] = new double[3]; for(int i = 0; i < 3; i++) s[i] = in.nextDouble(); java.util.Arrays.sort(s); if(s[0] + s[1] <= s[2]){ System.out.println("The triangle doesn't exist."); } else{ double cosValue = Math.cos((square(s[0]) + square(s[1]) + square(s[2]))/(2*s[0]*s[1])); if(cosValue > 0) System.out.println("The triangle is acute."); else System.out.println("The triangle is not acute."); } } } |
Алгоритм:
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)
В формулы у Вас закрались: разрыв строки < br / > и * (в мат. формулах умножение обозначается маленькой точкой или опускается).
«Сортировка» у Вас не сортирует числа.
Допустим для чисел 3 2 1 будет (шаги выполнения: 2 3 1, 2 1 3), результат 2 1 3. Почти что сортировка пузырьком, но последний шаг неверен. Впрочем Вам он и не нужен, ведь Вам нужно, чтобы z было максимальной из сторон.
Кстати, предложение «вырожденный случай не рассматривается» меня немного сбило, мне показалось, что Вы его вообще не рассматриваете, а Вы просто не считаете вырожденный треугольник корректно заданным треугольником (что логично).
Благодарю за замечания. Сортировку доработал (на ваших данных теперь даёт корректный результат) , формулы скорректировал в соответствии с правилами оформления.
Молодец, повеселил жонглированием значениями переменных. Только один «бросок» в 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 решит задачу без «сортировок».
Я не говорю, что так лучше. Просто продолжаю жонглировать 🙂
Упорядоченность x,y,z в Ваше программе не важна.
Важно только, чтобы z была большей из сторон.
Т.е. Вы отсортировали стороны () по возрастанию .
А нужно было только найти максимум.
Задача нахождения максимума существенно легче в реализации и заметно быстрее в работе чем задача сортировки. Не в Вашем случае, а для наборов данных.
В Вашем случае, если совсем коротко: строку 12 тоже нужно/можно выбросить.
Желание возникало, но к ночи я забыл как думать, к сожалению.
Реализовал я оба варианта ( http://ideone.com/xAFy92 ), но в отчет вставил тот, который показался мне более очевидным. Обе версии программы прошли все указанные тесты.
Ваш вариант оказался несколько неожиданным, хотя и красивым, я его запомнил. И почитал о реализации функций из заголовочного файла algorithm, чтобы выяснить, что работает быстрее и почему. В данной задаче заметного приращения в быстродействии я не заметил, но при работе с данными действительно проще найти максимальный элемент.
Я не смотрел, какой вариант быстрее.
Если есть желание протестировать, то нужно вставить все вычисления в цикл с большим количеством повторений. Можно варьировать исходные данные.
Перед циклом и после него вывести время наиболее точной функцией.
Правда останется ещё много неучтённых факторов, но общее представление можно будет получить.
В будущем мы научимся пользоваться профайлером, что возможно несколько облегчит Вам задачу анализа быстродействия.
Засчитана Java версия.
Правда, немного странно смотрится сочетание строк import java.util.*; и java.util.Arrays.sort(s);. Т.е. import есть, но не используется.