Cuente el número de triángulos posibles con una longitud de lados que no exceda N

Dado un número entero N , la tarea es encontrar el número total de triángulos en ángulo recto que se pueden formar de manera que la longitud de cualquier lado del triángulo sea como máximo N .

Un triángulo rectángulo satisface la siguiente condición: X 2 + Y 2 = Z 2 donde Z representa la longitud de la hipotenusa y X e Y representan las longitudes de los dos lados restantes. 

Ejemplos: 

Entrada: N = 5 
Salida:
Explicación: 
La única combinación posible de lados que forman un triángulo rectángulo es {3, 4, 5}.

Entrada: N = 10 
Salida:
Explicación: 
Las posibles combinaciones de lados que forman un triángulo rectángulo son {3, 4, 5} y {6, 8, 10}.

Enfoque ingenuo: la idea es generar todas las combinaciones posibles de tripletes con números enteros del rango [1, N] y, para cada una de esas combinaciones, verificar si es un triángulo rectángulo o no. 

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ implementation of
// the above approach
 
#include<bits/stdc++.h>
using namespace std;
 
// Function to count total
// number of right angled triangle
int right_angled(int n)
{
    // Initialise count with 0
    int count = 0;
 
    // Run three nested loops and
    // check all combinations of sides
    for (int z = 1; z <= n; z++) {
        for (int y = 1; y <= z; y++) {
            for (int x = 1; x <= y; x++) {
 
                // Condition for right
                // angled triangle
                if ((x * x) + (y * y) == (z * z)) {
 
                    // Increment count
                    count++;
                }
            }
        }
    }
 
    return count;
}
 
// Driver Code
int main()
{
    // Given N
    int n = 5;
 
    // Function Call
    cout << right_angled(n);
    return 0;
}

Java

// Java implementation of 
// the above approach
import java.io.*;
 
class GFG{
     
// Function to count total
// number of right angled triangle
static int right_angled(int n)
{
     
    // Initialise count with 0
    int count = 0;
     
    // Run three nested loops and
    // check all combinations of sides
    for(int z = 1; z <= n; z++)
    {
        for(int y = 1; y <= z; y++)
        {
            for(int x = 1; x <= y; x++)
            {
                 
                // Condition for right
                // angled triangle
                if ((x * x) + (y * y) == (z * z))
                {
                     
                    // Increment count
                    count++;
                }
            }
        }
    }
    return count;
}
 
// Driver code
public static void main (String[] args)
{
     
    // Given N
    int n = 5;
 
    // Function call
    System.out.println(right_angled(n));
}
}
 
// This code is contributed by code_hunt

Python3

# Python implementation of 
# the above approach
 
# Function to count total
# number of right angled triangle
def right_angled(n):
     
    # Initialise count with 0
    count = 0
 
    # Run three nested loops and
    # check all combinations of sides
    for z in range(1, n + 1):
        for y in range(1, z + 1):
            for x in range(1, y + 1):
 
                # Condition for right
                # angled triangle
                if ((x * x) + (y * y) == (z * z)):
 
                    # Increment count
                    count += 1
                 
    return count
 
# Driver Code
 
# Given N
n = 5
 
# Function call
print(right_angled(n))
 
# This code is contributed by code_hunt

C#

// C# implementation of
// the above approach
using System;
 
class GFG{
     
// Function to count total
// number of right angled triangle
static int right_angled(int n)
{
     
    // Initialise count with 0
    int count = 0;
     
    // Run three nested loops and
    // check all combinations of sides
    for(int z = 1; z <= n; z++)
    {
        for(int y = 1; y <= z; y++)
        {
            for(int x = 1; x <= y; x++)
            {
                 
                // Condition for right
                // angled triangle
                if ((x * x) + (y * y) == (z * z))
                {
 
                    // Increment count
                    count++;
                }
            }
        }
    }
    return count;
}
     
// Driver Code
public static void Main(string[] args)
{
     
    // Given N
    int n = 5;
 
    // Function call
    Console.Write(right_angled(n));
}
}
 
// This code is contributed by rutvik_56

Javascript

<script>
// javascript implementation of 
// the above approach
    
// Function to count total
// number of right angled triangle
function right_angled(n)
{
     
    // Initialise count with 0
    var count = 0;
     
    // Run three nested loops and
    // check all combinations of sides
    for(z = 1; z <= n; z++)
    {
        for(y = 1; y <= z; y++)
        {
            for(x = 1; x <= y; x++)
            {
                 
                // Condition for right
                // angled triangle
                if ((x * x) + (y * y) == (z * z))
                {
                     
                    // Increment count
                    count++;
                }
            }
        }
    }
    return count;
}
 
// Driver code
//Given N
var n = 5;
 
// Function call
document.write(right_angled(n));
 
// This code is contributed by Amit Katiyar
</script>
Producción: 

1

 

Complejidad temporal: O(N 3
Espacio auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar en función de la idea de que se puede encontrar el tercer lado del triángulo, si se conocen los dos lados de los triángulos. Siga los pasos a continuación para resolver el problema: 

  1. Iterar hasta N y generar pares de longitud posible de dos lados y encontrar el tercer lado usando la relación x 2 + y 2 = z 2
  2. Si se encuentra que sqrt(x 2 +y 2 ) es un número entero, almacene los tres números enteros en cuestión en un Conjunto en orden ordenado, ya que pueden formar un triángulo rectángulo.
  3. Imprima el tamaño final del conjunto como el conteo requerido.

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ implementation of the
// above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count total
// number of right angled triangle
int right_angled(int n)
{
    // Consider a set to store
    // the three sides
    set<pair<int, pair<int, int> > > s;
 
    // Find possible third side
    for (int x = 1; x <= n; x++) {
        for (int y = 1; y <= n; y++) {
 
            // Condition for a right
            // angled triangle
            if (x * x + y * y <= n * n) {
                int z = sqrt(x * x + y * y);
 
                // Check if the third side
                // is an integer
                if (z * z != (x * x + y * y))
                    continue;
 
                vector<int> v;
 
                // Push the three sides
                v.push_back(x);
                v.push_back(y);
                v.push_back(sqrt(x * x + y * y));
 
                sort(v.begin(), v.end());
 
                // Insert the three sides in
                // the set to find unique triangles
                s.insert({ v[0], { v[1], v[2] } });
            }
            else
                break;
        }
    }
 
    // return the size of set
    return s.size();
}
 
// Driver code
int main()
{
    // Given N
    int n = 5;
 
    // Function Call
    cout << right_angled(n);
    return 0;
}

Java

// Java implementation of the
// above approach
import java.util.*;
 
class Pair<F, S>
{
     
    // First member of pair
    private F first;
     
    // Second member of pair
    private S second;
 
    public Pair(F first, S second)
    {
        this.first = first;
        this.second = second;
    }
}
 
class GFG{
 
// Function to count total
// number of right angled triangle    
public static int right_angled(int n)
{
     
    // Consider a set to store
    // the three sides
    Set<Pair<Integer,
        Pair<Integer,
             Integer>>> s = new HashSet<Pair<Integer,
                                        Pair<Integer,
                                             Integer>>>();
  
    // Find possible third side
    for(int x = 1; x <= n; x++)
    {
        for(int y = 1; y <= n; y++)
        {
             
            // Condition for a right
            // angled triangle
            if (x * x + y * y <= n * n)
            {
                int z = (int)Math.sqrt(x * x + y * y);
  
                // Check if the third side
                // is an integer
                if (z * z != (x * x + y * y))
                    continue;
  
                Vector<Integer> v = new Vector<Integer>();
                 
                // Push the three sides
                v.add(x);
                v.add(y);
                v.add((int)Math.sqrt(x * x + y * y));
  
                Collections.sort(v);
  
                // Add the three sides in
                // the set to find unique triangles
                s.add(new Pair<Integer,
                          Pair<Integer,
                               Integer>>(v.get(0),
                      new Pair<Integer,
                               Integer>(v.get(1),
                                        v.get(2))));
            }
            else
                break;
        }
    }
     
    // Return the size of set
    return s.size() - 1;
}
  
// Driver code
public static void main(String[] args)
{
     
    // Given N
    int n = 5;
  
    // Function call
    System.out.println(right_angled(n));
}
}
 
// This code is contributed by grand_master

Javascript

// JavaScript implementation of the
// above approach
 
// Function to count total
// number of right angled triangle
function right_angled(n)
{
    // Consider a set to store
    // the three sides
    let s = new Set();
 
    // Find possible third side
    for (let x = 1; x <= n; x++) {
        for (let y = 1; y <= n; y++) {
 
            // Condition for a right
            // angled triangle
            if (x * x + y * y <= n * n) {
                let z = Math.floor(Math.sqrt(x * x + y * y));
 
                // Check if the third side
                // is an integer
                if (z * z != (x * x + y * y))
                    continue;
 
                let v = new Array();
 
                // Push the three sides
                v.push(x);
                v.push(y);
                v.push(Math.floor(Math.sqrt(x * x + y * y)));
 
                v.sort();
 
                // Insert the three sides in
                // the set to find unique triangles
                s.add([v[0],[v[1], v[2]]].join());
            }
            else
                break;
        }
    }
 
    // return the size of set
    return s.size;
}
 
// Driver code
// Given N
let n = 5;
 
// Function Call
console.log(right_angled(n));
 
// The code is contributed by Gautam goel (gautamgoel962)
Producción: 

1

 

Complejidad temporal: O(N 2
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por harsh2608 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *