У нас есть массив A элементы которой являются натуральными числами. Нужно написать функцию которая получает массив A и возвращает массив B из трех элементов так, чтобы тремя элементами массива B нужно было бы построить треугольник с наибольшей плошадью.
Площадь треугольника для сторон a, b, c нужно найти следующим образом
S = Math.sqrt(p * (p - a) * (p - b) * (p - c)), где p = (a + b + c) / 2
Например
если дан массив A = [5, 4, 2, 1, 3, 2] то получим массив B = [5, 4, 3]
function greatAreaTriangle () {}
console.log(greatAreaTriangle ([5, 4, 2, 1, 3, 2])) // [5, 4, 3]
console.log(greatAreaTriangle ([3, 4, 8, 10, 13])) // [8, 10, 13]
console.log(greatAreaTriangle ([0, 12, 0, 0, 15, 0, 10, 0])) // [12, 15, 10]
console.log(greatAreaTriangle ([5, 4, 3, 10, 1, 2])) // [5, 4, 3]
Самый простой (и наверняка не самый эффективный) способ - полным перебором вариантов. Что-нибудь вроде:
const greatAreaTriangle = (array) => {
const triangles = [];
const getTriangle = (currentTriangle, remainingArray) => {
// если currentTriangle содержит три элемента, проверить, является ли он треугольником и добавить в triangles
// если нет, то добавить следующий элемент из массива
}
getTriangle([array[0], array.slice(1)])
// проверить, какой треугольник в массиве triangles самый большой и вернуть его
}
Но мне почему-то кажется, что должен быть способ эффективнее (в этой реализации тебе придется перебрать n^3 элементов и создать столько же массивов).
Для начала отфильтровать массив от нулей. Надеюсь, понятно почему? :)
Для одного набора чисел большую площадь будет иметь тот, у которого больший периметр. Следовательно, можно выполнить эти шаги для быстрого поиска решения
отсортировать массив по убыванию.
взять первые три элемента
проверить возможен ли для выбранных чисел треугольник. Если да, то решение найдено.
Если нет, то сдвинуть “окно” на один. Перейти на шаг 3.
Бывают случаи, когда треугольник имея бо́льший периметр будет иметь меньшую площадь.
Как это повлияет на решение? Почему? Задание для подумать самостоятельно ;)