Я пытаюсь найти количество возможных треугольников, которые можно сформировать с помощью набора чисел здесь:
https://www.geeksforgeeks.org/find-number-of-triangles-possible/
Я написал его версию на javaScript. однако я не совсем понимаю одну часть решения:
// Total number of possible triangles that can
// be formed with the two fixed elements is
// k - j - 1. The two fixed elements are arr[i]
// and arr[j]. All elements between arr[j+1]/ to
// arr[k-1] can form a triangle with arr[i] and arr[j].
// One is subtracted from k because k is incremented
// one extra in above while loop.
// k will always be greater than j. If j becomes equal
// to k, then above loop will increment k, because arr[k]
// + arr[i] is always greater than arr[k]
Проблема:
Я до сих пор не понимаю этой логики. Как k-j
появился на свет?
Как такое количество треугольников, которое можно сформировать с помощью arr [i], arr [j] и arr [k] (с arr [i] <arr [j] <arr [k]), дает счет как k-j
? неясно с этой стороны.
Может кто меня просветить?
JS-решение проблемы:
var triangleNumber = function(arr) {
let count = 0, n = arr.length;
//Sort the array in ascending order.
arr.sort((a,b) => { return a-b; });
// Set three pointers, i, j = i+1 and k=i+2
for(let i=0; i<n-2; i++) {
let k = i+2;
for(let j=i+1; j<n; j++) {
// If sum of two sides > third side
/* Find the rightmost element which is smaller
than the sum of two fixed elements
The important thing to note here is, we use
the previous value of k. If value of arr[i] +
arr[j-1] was greater than arr[k], then arr[i] +
arr[j] must be greater than k, because the
array is sorted. */
while (k <n && arr[i] + arr[j] > arr[k]) {
++k;
}
/* Total number of possible triangles that can be
formed with the two fixed elements is k - j - 1.
The two fixed elements are arr[i] and arr[j]. All
elements between arr[j+1] to arr[k-1] can form a
triangle with arr[i] and arr[j]. One is subtracted
from k because k is incremented one extra in above
while loop. k will always be greater than j. If j
becomes equal to k, then above loop will increment
k, because arr[k] + arr[i] is always/ greater than
arr[k] */
count += k-j-1;
}
}
return count<0? 0: count;
};
const arr = [2,2,3,4];
console.info(triangleNumber(arr));
Вы прочитали шаг 3 метода на странице, на которую ведет ссылка? Это объясняет, как k-j
появляется на сцене.
@Barmar Я сделал. Однако я все еще не могу представить себе следующее утверждение Fix ‘i’ and ‘j’ and find the rightmost index ‘k’ (or largest ‘arr[k]’) such that ‘arr[i] + arr[j] > arr[k]’. The number of triangles that can be formed with ‘arr[i]’ and ‘arr[j]’ as two sides is ‘k – j’. Add ‘k – j’ to count of triangles.
. Как мы можем доказать, что k-j - это счетчик? Цени свое время.
Элементы k-j
начинаются от элемента после j
до элемента k
. Все они являются действительными третьими сторонами треугольника с arr[i]
и arr[j]
в качестве первых двух сторон.
Например. если первые две стороны - это arr[2]
и arr[4]
, а наибольшая - k
, где arr[i] + arr[j] > arr[k]
- это 10
, вы можете составить треугольник из k = 5, 6, 7, 8, 9, or 10
. Там 6 индексов и 10 - 4 = 6
.
Ваш вопрос по математике или программе? Если дело в математике, Математика было бы лучшим местом.