Рубрики

Подсчитайте количество возможных треугольников

Дан несортированный массив натуральных чисел. Найдите количество треугольников, которые могут быть сформированы с тремя различными элементами массива как три стороны треугольников. Чтобы треугольник был возможен из 3 значений, сумма любых двух значений (или сторон) должна быть больше, чем третье значение (или третья сторона).
Например, если входной массив равен {4, 6, 3, 7}, выходное значение должно быть 3. Возможны три треугольника: {3, 4, 6}, {4, 6, 7} и {3, 6, 7}. Обратите внимание, что {3, 4, 7} не является возможным треугольником.
В качестве другого примера рассмотрим массив {10, 21, 22, 100, 101, 200, 300}. Может быть 6 возможных треугольников: {10, 21, 22}, {21, 100, 101}, {22, 100, 101}, {10, 100, 101}, {100, 101, 200} и {101, 200, 300}

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

Сложность времени: O (N ^ 3) где N — размер входного массива.

Метод 2 (хитрый и эффективный)
Пусть a, b и c — три стороны. Приведенное ниже условие должно выполняться для треугольника (сумма двух сторон больше, чем третьей стороны)
я) а + б> в
ii) b + c> a
iii) а + с> б

Ниже приведены шаги для подсчета треугольника.

1. Сортировать массив в порядке убывания.

2. Инициализируйте два указателя 'i' и 'j' на первый и второй элементы соответственно и инициализируйте количество треугольников как 0.

3. Исправьте «i» и «j» и найдите самый правый индекс «k» (или самый большой «arr [k]»), такой что «arr [i] + arr [j]> arr [k]». Число треугольников, которые могут быть образованы с помощью 'arr [i]' и 'arr [j]' в качестве двух сторон, равно 'k — j'. Добавьте «k — j» к числу треугольников.

Давайте рассмотрим 'arr [i]' как 'a', 'arr [j]' как b и все элементы между 'arr [j + 1]' и 'arr [k]' как 'c'. Вышеупомянутые условия (ii) и (iii) выполняются, потому что 'arr [i] <arr [j] <arr [k]'. И мы проверяем условие (I), когда мы выбираем «к»

4. Увеличьте «j», чтобы снова исправить второй элемент.

Обратите внимание, что на шаге 3 мы можем использовать предыдущее значение «k». Причина проста: если мы знаем, что значение «arr [i] + arr [j-1]» больше, чем «arr [k]», то мы можем сказать «arr [i] + arr [j]» также будет больше, чем 'arr [k]', потому что массив сортируется в порядке возрастания.

5. Если 'j' достигло конца, тогда увеличьте 'i'. Инициализируйте «j» как «i + 1», «k» как «i + 2» и повторите шаги 3 и 4.

Ниже приводится реализация вышеуказанного подхода.

C ++

// C ++ программа для подсчета количества треугольников, которые могут быть
// сформирован из заданного массива
#include <bits/stdc++.h>

using namespace std;

  
/ * Следующая функция необходима для библиотечной функции
QSort (). обращаться
http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/ * /

int comp(const void* a, const void* b) 

{ return *(int*)a > *(int*)b ; } 

  
// Функция для подсчета всех возможных треугольников с помощью arr []
// элементы

int findNumberOfTriangles(int arr[], int n) 

    // Сортировка элементов массива в порядке убывания

    qsort(arr, n, sizeof( arr[0] ), comp); 

  

    // Инициализируем количество треугольников

    int count = 0; 

  

    // Исправить первый элемент. Нам нужно бежать до н-3

    // так как два других элемента выбраны из

    // arr [i + 1 ... n-1]

    for (int i = 0; i < n - 2; ++i) 

    

        // Инициализируем индекс самой правой трети

        // элемент

        int k = i + 2; 

  

        // Исправить второй элемент

        for (int j = i + 1; j < n; ++j) 

        

            // Находим самый правый элемент, который

            // меньше суммы двух фиксированных элементов

            // Здесь важно отметить, что мы

            // использовать предыдущее значение k. Если значение

            // arr [i] + arr [j-1] было больше, чем arr [k],

            // тогда arr [i] + arr [j] должно быть больше k,

            // потому что массив отсортирован.

            while (k < n && arr[i] + arr[j] > arr[k]) 

            ++k; 

  

            // Общее количество возможных треугольников, которые могут

            // формируется с двумя фиксированными элементами

            // k - j - 1. Два фиксированных элемента arr [i]

            // и обр [j]. Все элементы между arr [j + 1] / to

            // arr [k-1] может образовывать треугольник с arr [i] и arr [j].

            // один вычитается из k, потому что k увеличивается

            // один дополнительный цикл выше.

            // k всегда будет больше, чем j. Если j становится равным

            // к k, то цикл выше увеличит k, потому что arr [k]

            // + arr [i] всегда больше, чем arr [k]

            if(k > j) 

            count += k - j - 1; 

        

    

  

    return count; 

  
// Код драйвера

int main() 

    int arr[] = {10, 21, 22, 100, 101, 200, 300}; 

    int size = sizeof( arr ) / sizeof( arr[0] ); 

  

    cout<<"Total number of triangles possible is "<<findNumberOfTriangles( arr, size ); 

  

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

// C программа для подсчета количества треугольников, которые могут быть
// сформирован из заданного массива
#include <stdio.h>
#include <stdlib.h>

  
/ * Следующая функция необходима для библиотечной функции
QSort (). обращаться
http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/ * /

int comp(const void* a, const void* b)

{ return *(int*)a > *(int*)b ; }

  
// Функция для подсчета всех возможных треугольников с помощью arr []
// элементы

int findNumberOfTriangles(int arr[], int n)

{

    // Сортировка элементов массива в порядке убывания

    qsort(arr, n, sizeof( arr[0] ), comp);

  

    // Инициализируем количество треугольников

    int count = 0;

  

    // Исправить первый элемент. Нам нужно бежать до н-3

    // так как два других элемента выбраны из

    // arr [i + 1 ... n-1]

    for (int i = 0; i < n-2; ++i)

    {

        // Инициализируем индекс самой правой трети

        // элемент

        int k = i+2;

  

        // Исправить второй элемент

        for (int j = i+1; j < n; ++j)

        {

            // Находим самый правый элемент, который

            // меньше суммы двух фиксированных элементов

            // Здесь важно отметить, что мы

            // использовать предыдущее значение k. Если значение

            // arr [i] + arr [j-1] было больше, чем arr [k],

            // тогда arr [i] + arr [j] должно быть больше k,

            // потому что массив отсортирован.

            while (k < n && arr[i] + arr[j] > arr[k])

            ++k;

  

            // Общее количество возможных треугольников, которые могут

            // формируется с двумя фиксированными элементами

            // k - j - 1. Два фиксированных элемента arr [i]

            // и обр [j]. Все элементы между arr [j + 1] / to

            // arr [k-1] может образовывать треугольник с arr [i] и arr [j].

            // один вычитается из k, потому что k увеличивается

            // один дополнительный цикл выше.

            // k всегда будет больше, чем j. Если j становится равным

            // к k, то цикл выше увеличит k, потому что arr [k]

            // + arr [i] всегда больше, чем arr [k]

            if(k>j)

            count += k - j - 1;

        }

    }

  

    return count;

}

  
// Программа драйвера для тестирования вышеуказанного функционала [j + 1]

int main()

{

    int arr[] = {10, 21, 22, 100, 101, 200, 300};

    int size = sizeof( arr ) / sizeof( arr[0] );

  

    printf("Total number of triangles possible is %d ",

        findNumberOfTriangles( arr, size ) );

  

    return 0;

}

Джава

// Java-программа для подсчета количества треугольников, которые могут быть
// сформирован из заданного массива

import java.io.*;

import java.util.*;

  

class CountTriangles

{

    // Функция для подсчета всех возможных треугольников с помощью arr []

    // элементы

    static int findNumberOfTriangles(int arr[])

    {

        int n = arr.length;

        // Сортировка элементов массива в порядке убывания

        Arrays.sort(arr);

  

        // Инициализируем количество треугольников

        int count = 0;

  

        // Исправить первый элемент. Нам нужно бежать до н-3, как

        // два других элемента выбраны из arr [i + 1 ... n-1]

        for (int i = 0; i < n-2; ++i)

        {

            // Инициализируем индекс самого правого третьего элемента

            int k = i + 2;

  

            // Исправить второй элемент

            for (int j = i+1; j < n; ++j)

            {

                / * Найти самый правый элемент, который меньше

                чем сумма двух фиксированных элементов

                Здесь важно отметить, что мы используем

                предыдущее значение к. Если значение arr [i] +

                arr [j-1] был больше, чем arr [k], затем arr [i] +

                arr [j] должно быть больше k, потому что

                массив отсортирован. * /

                while (k < n && arr[i] + arr[j] > arr[k])

                    ++k;

  

            / * Общее количество возможных треугольников, которые могут быть

                образуется с двумя фиксированными элементами k - j - 1.

                Два фиксированных элемента - это arr [i] и arr [j]. Все

                элементы от arr [j + 1] до arr [k-1] могут образовывать

                треугольник с arr [i] и arr [j]. Один вычитается

                от к, потому что к увеличивается на один лишний в

                пока цикл. k всегда будет больше, чем j. Если J

                становится равным k, тогда вышеуказанный цикл будет увеличиваться

                k, потому что arr [k] + arr [i] всегда / больше чем

                обр [к] * /

                if(k>j)

                count += k - j - 1;

            }

        }

        return count;

    }

  

    public static void main (String[] args)

    {

        int arr[] = {10, 21, 22, 100, 101, 200, 300};

        System.out.println("Total number of triangles is " +

                            findNumberOfTriangles(arr));

    }

}
/ * Этот код предоставлен Девешом Агравалом * /

питон

# Функция Python для подсчета всех возможных треугольников с помощью arr []
# элементы

  

def findnumberofTriangles(arr):

  

    # Сортировать массив и инициализировать счетчик как 0

    n = len(arr)

    arr.sort()

    count = 0

  

    # Исправить первый элемент. Нам нужно бежать до н-3, как

    # два других элемента выбраны из arr [i + 1 ... n-1]

    for i in range(0,n-2):

  

        # Инициализировать индекс самого правого третьего элемента

        k = i + 2

  

        # Исправить второй элемент

        for j in range(i+1,n):

  

            # Найти самый правый элемент, который меньше

            # чем сумма двух фиксированных элементов

            # Важно отметить, что мы используем

            # предыдущее значение k. Если значение arr [i] +

            # arr [j-1] было больше, чем arr [k], затем arr [i] +

            # arr [j] должно быть больше k, потому что массив

            # отсортировано.

            while (k < n and arr[i] + arr[j] > arr[k]):

                k += 1

  

            # Общее количество возможных треугольников, которые могут быть

            #, образованный двумя фиксированными элементами, равен k - j - 1.

            # Два фиксированных элемента - это arr [i] и arr [j]. Все

            # элементы между arr [j + 1] и arr [k-1] могут образовывать

            # треугольник с arr [i] и arr [j]. Один вычитается

            # из k, потому что k увеличивается на один шаг выше

            # время цикла. k всегда будет больше, чем j. Если J

            # становится равным k, тогда вышеуказанный цикл будет увеличивать k,

            # потому что arr [k] + arr [i] всегда больше, чем arr [k]

            if(k>j):

                count += k - j - 1

  

    return count

  
# Функция драйвера для проверки вышеуказанной функции

arr = [10, 21, 22, 100, 101, 200, 300]

print "Number of Triangles:",findnumberofTriangles(arr)

  
# Этот код предоставлен Девешом Агравалом

C #

// C # программа для подсчета числа
// из треугольников, которые могут быть
// сформирован из заданного массива

using System;

  

class GFG

{

    // Функция для подсчета всех

    // возможные треугольники

    // с элементами arr []

    static int findNumberOfTriangles(int []arr)

    {

        int n = arr.Length;

          

        // Сортировка элементов массива

        // в неубывающем порядке

        Array.Sort(arr);

  

        // Инициализировать счет

        // из треугольников

        int count = 0;

  

        // Исправить первый элемент. Мы

        // нужно бежать до n-3 как

        // два других элемента

        // выбрано из arr [i + 1 ... n-1]

        for (int i = 0; i < n - 2; ++i)

        {

            // Инициализируем индекс

            // самый правый третий элемент

            int k = i + 2;

  

            // Исправить второй элемент

            for (int j = i + 1; j < n; ++j)

            {

                / * Найти самый правый элемент

                которая меньше суммы

                из двух неподвижных элементов.

                важно отметить здесь

                есть, мы используем предыдущее значение

                к. Если значение arr [i] +

                arr [j-1] был больше, чем arr [k],

                тогда arr [i] + arr [j] должно быть

                больше, чем к, потому что

                массив отсортирован. * /

                while (k < n && arr[i] + 

                                arr[j] > arr[k])

                    ++k;

  

            / * Общее количество возможных треугольников

                которые могут быть сформированы с двумя

                фиксированные элементы k - j - 1.

                два фиксированных элемента - это arr [i] и

                обр [J]. Все элементы между arr [j + 1]

                обр [к-1] может образовывать треугольник с

                arr [i] и arr [j]. Один вычитается

                от к, потому что к увеличивается на единицу

                дополнительно в цикле выше. K будет

                всегда быть больше, чем j. Если J становится

                равным к, то выше цикл будет

                приращение k, потому что arr [k] + arr [i]

                всегда / больше, чем arr [k] * /

                if(k>j)

                count += k - j - 1;

            }

        }

        return count;

    }

  

    // Код драйвера

    public static void Main ()

    {

        int []arr = {10, 21, 22, 100, 

                    101, 200, 300};

        Console.WriteLine("Total number of triangles is " +

                            findNumberOfTriangles(arr));

    }

}

  
// Этот код предоставлен anuj_67.

PHP

<?php
// PHP программа для подсчета числа
// из треугольников, которые могут быть
// сформирован из заданного массива

  
// Функция для подсчета всех
// возможные треугольники с
// элемент arr []

function findNumberOfTriangles($arr)

{

    $n = count($arr);

      

    // Сортировка элементов массива

    // в неубывающем порядке

    sort($arr);

  

    // Инициализировать счет

    // из треугольников

    $count = 0;

  

    // Исправить первый элемент.

    // Нам нужно бежать до n-3

    // как два других элемента

    // выбраны из

    // arr [i + 1 ... n-1]

    for ($i = 0; $i < $n - 2; ++$i)

    {

        // Инициализируем индекс

        // самый правый третий элемент

        $k = $i + 2;

  

        // Исправить второй элемент

        for ($j = $i + 1; $j < $n; ++$j)

        {

            / * Найти самый правый элемент

            которая меньше суммы

            из двух неподвижных элементов.

            важно отметить здесь

            есть, мы используем предыдущее значение

            к. Если значение arr [i] +

            обр [j-1] было больше, чем

            arr [k], затем arr [i] +

            arr [j] должно быть больше k,

            потому что массив отсортирован. * /

            while ($k < $n && $arr[$i] + 

                            $arr[$j] > $arr[$k])

                ++$k;

  

        / * Общее количество возможных

            треугольники, которые могут быть

            сформирован с двумя фиксированными

            Элементами является k - j - 1.

            Два фиксированных элемента

            arr [i] и arr [j]. Все

            элементы между обр [j + 1]

            к обр [к-1] может образовать

            треугольник с обр

            обр [J]. Один вычитается

            от к, потому что к увеличивается

            один дополнительный цикл выше.

            k всегда будет больше, чем j.

            Если j становится равным k, то

            вышеуказанный цикл будет увеличивать k,

            потому что arr [k] + arr [i]

            всегда / больше чем arr [k] * /

            if($k>$j)

            $count += $k - $j - 1;

        }

    }

    return $count;

}

  
// Код драйвера

$arr = array(10, 21, 22, 100,

            101, 200, 300);

echo"Total number of triangles is " ,

        findNumberOfTriangles($arr);

  
// Этот код предоставлен anuj_67.
?>


Выход:

Total number of triangles possible is 6

Сложность времени: O (n ^ 2). Временная сложность выглядит больше из-за 3-х вложенных циклов. Если мы поближе познакомимся с алгоритмом, то заметим, что k инициализируется только один раз во внешнем цикле. Самый внутренний цикл выполняется не более O (n) времени для каждой итерации самого внешнего цикла, потому что k начинается с i + 2 и повышается до n для всех значений j. Следовательно, сложность по времени равна O (n ^ 2).

Техника двух указателей:
Сложность по времени может быть значительно уменьшена с помощью метода двух указателей всего за два вложенных цикла.
Предположим, что данный массив равен {4,3,5,7,6}. При сортировке массив становится {3,4,5,6,7}.
Мы берем три переменные l, r и i, указывающие на начало, конец-1 и начало элемента массива
от конца массива.
Теперь, если мы можем сформировать треугольник, используя arr [l] и arr [r], тогда мы, очевидно, можем сформировать треугольники
из a [l + 1], a [l + 2]… ..a [r-1], arr [r] и a [i], потому что массив отсортирован
который мы можем напрямую рассчитать, используя (RL). Так что общая сложность итерации
через все элементы массива уменьшается.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация вышеуказанного подхода
#include<bits/stdc++.h>

using namespace std;

  

void CountTriangles(vector <int> A){ 

  

    int n=A.size();

  

    sort(A.begin(), A.end()); 

  

    int count = 0;

      

    for( int i = n-1; i >= 1; i--){

        int l = 0, r = i-1;

        while( l < r){

            if( A[l] + A[r] > A[i]){

  

                // Если это возможно с a [l], a [r]

                // и [i] тогда тоже возможно

                // с [l + 1] .. a [r-1], a [r] и a [i]

                count += r - l ; 

  

                // проверка на более возможные решения

                r--;  

            }

            else 

  

                // если невозможно проверить

                // более высокие значения arr [l]

                l++;  

        }

    }

    cout<<"No of possible solutions: "<<count;

}

int main(){

  

    vector<int> A = { 4, 3, 5, 7, 6 }; 

  

    CountTriangles(A);

    
}    

Джава

// Java реализация вышеуказанного подхода

import java.util.*;

  

class GFG 

{

static void CountTriangles(int[] A)

{

    int n = A.length;

  

    Arrays.sort(A);

  

    int count = 0;

  

    for (int i = n - 1; i >= 1; i--)

    {

        int l = 0, r = i - 1;

        while (l < r)

        {

            if (A[l] + A[r] > A[i])

            {

  

                // Если это возможно с a [l], a [r]

                // и [i] тогда тоже возможно

                // с [l + 1] .. a [r-1], a [r] и a [i]

                count += r - l;

  

                // проверка на более возможные решения

                r--;

            

            else // если невозможно проверить

                 // более высокие значения arr [l]

            {

                l++;

            }

        }

    }

    System.out.print("No of possible solutions: " + count);

}

  
// Код драйвера

public static void main(String[] args) 

{

    int[] A = {4, 3, 5, 7, 6};

  

    CountTriangles(A);

}
}

  
// Этот код предоставлен PrinciRaj1992

python3

# Python реализация вышеуказанного подхода

def CountTriangles( A):

  

    n = len(A);

  

    A.sort(); 

  

    count = 0;

      

    for i in range(n - 1, 0, -1):

        l = 0;

        r = i - 1;

        while(l < r):

            if(A[l] + A[r] > A[i]):

  

                # Если это возможно с [l], a [r]

                # и [я] тогда тоже возможно

                # с [l + 1] .. a [r-1], a [r] и a [i]

                count += r - l; 

  

                # проверка на более возможные решения

                r -= 1

              

            else:

  

                # если невозможно проверить

                # более высокие значения обр [л]

                l += 1

    print("No of possible solutions: ", count);

  
Код водителя

if __name__ == '__main__':

  

    A = [ 4, 3, 5, 7, 6 ]; 

  

    CountTriangles(A);

      
# Этот код предоставлен PrinciRaj1992

C #

// C # реализация вышеуказанного подхода

using System;

      

class GFG 

{

static void CountTriangles(int[] A)

{

    int n = A.Length;

  

    Array.Sort(A);

  

    int count = 0;

  

    for (int i = n - 1; i >= 1; i--)

    {

        int l = 0, r = i - 1;

        while (l < r)

        {

            if (A[l] + A[r] > A[i])

            {

  

                // Если это возможно с a [l], a [r]

                // и [i] тогда тоже возможно

                // с [l + 1] .. a [r-1], a [r] и a [i]

                count += r - l;

  

                // проверка на более возможные решения

                r--;

            

            else // если невозможно проверить

                 // более высокие значения arr [l]

            {

                l++;

            }

        }

    }

    Console.Write("No of possible solutions: " + count);

}

  
// Код драйвера

public static void Main(String[] args) 

{

    int[] A = {4, 3, 5, 7, 6};

  

    CountTriangles(A);

}
}

  
// Этот код предоставлен Rajput-Ji

Выход:

No of possible solutions: 9

Сложность по времени: O (n ^ 2), потому что мы используем два вложенных цикла, но общие итерации по сравнению с
Вышеуказанный метод значительно сокращается.

Источник: http://stackoverflow.com/questions/8110538/total-number-of-possible-triangles-from-n-numbers

http://espressocode.top/two-pointers-technique/

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Подсчитайте количество возможных треугольников

0.00 (0%) 0 votes