Питон 3 вопрос по задаче!! спасибо огромное!!
Треугольник
Вам даны 4 отрезка. Выведите YES, если среди них найдутся 3, из которых можно составить треугольник, и NO в противном случае. Для решения напишите функцию triangle(a, b, c), которая будет возвращать True, если из трёх заданных отрезков можно составить треугольник, и False иначе.
Внимание! Не забудьте про отступы при сдаче кода в этой задаче.
Ввод
1
2
3
4
Вывод
YES
Ввод
1
2
3
8
Вывод
NO
Например, так:
def triangle(a, b, c): return a + b > c
ds = sorted(map(int, map(input, ('',) * 4)))
print(('NO','YES')[any(triangle(*ds[:i], *ds[i+1:]) for i in range(len(ds)))])
Асимптотика:
Ввод значений сторон - линейная O(n)
Сортировка - линейно-логарифмическая O(n log n)
Перебор троек - линейная O(n)
Всё это складываем, получаем линейно-логарифмическую функцию.
Внутри функции проверки достаточно проверить одну сумму сторон, т.к. c >= b >= a (список - сортированный).
Если бы чисел было не 4, а больше, то пришлось бы брать все комбинации по 3, а это дало бы на 5 числах квадратичный алгоритм, а на 6 и более - кубический. Но перебор можно было бы укоротить на одну степень свободы, учитывая, что список - сортированный, и таким образом в худшем случае остался бы квадратичный алгоритм.
И отступы в данной реализации не нужны.
def triangle(a, b, c):
return a + b > c
ds = sorted(map(int, input().split()))
print('YES' if any(triangle(*ds[:i], *ds[i+1:]) for i in range(len(ds))) else 'NO')