Un triplete pitagórico es un conjunto de números naturales tales que a < b < c, para los cuales a^2 + b^2 = c^2 . Por ejemplo, 3^2 + 4^2 = 5^2.
Dado un número n, encuentre un triplete pitagórico con suma como dado n.
Ejemplos:
Input : n = 12 Output : 3, 4, 5 Note that 3, 4 and 5 is a Pythagorean Triplet with sum equal to 12. Input : n = 4. Output : No Triplet There does not exist a Pythagorean Triplet with sum equal to 4.
Una solución simple es ejecutar tres bucles anidados para generar todos los tripletes posibles y, para cada triplete, verificar si es un triplete pitagórico y ha dado suma. La complejidad temporal de esta solución es O(n 3 ).
Una solución eficiente es ejecutar dos ciclos, donde el primer ciclo se ejecuta desde i = 1 a n/3, el segundo ciclo se ejecuta desde j = i+1 a n/2. En el segundo bucle, comprobamos si (n – i – j) es igual a i * i + j * j.
C++
// C++ program to find Pythagorean
// Triplet of given sum.
#include <bits/stdc++.h>
using namespace std;
void pythagoreanTriplet(int n)
{
// Considering triplets in
// sorted order. The value
// of first element in sorted
// triplet can be at-most n/3.
for (int i = 1; i <= n / 3; i++)
{
// The value of second
// element must be less
// than equal to n/2
for (int j = i + 1; j <= n / 2; j++)
{
int k = n - i - j;
if (i * i + j * j == k * k)
{
cout << i << ", "
<< j << ", "
<< k;
return;
}
}
}
cout << "No Triplet";
}
// Driver Code
int main()
{
int n = 12;
pythagoreanTriplet(n);
return 0;
}
Java
// Java program to find Pythagorean
// Triplet of given sum.
class GFG
{
static void pythagoreanTriplet(int n)
{
// Considering triplets in
// sorted order. The value
// of first element in sorted
// triplet can be at-most n/3.
for (int i = 1; i <= n / 3; i++)
{
// The value of second element
// must be less than equal to n/2
for (int j = i + 1; j <= n / 2; j++)
{
int k = n - i - j;
if (i * i + j * j == k * k)
{
System.out.print(i + ", "+
j + ", " + k);
return;
}
}
}
System.out.print("No Triplet");
}
// Driver Code
public static void main(String arg[])
{
int n = 12;
pythagoreanTriplet(n);
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python3 program to find
# Pythagorean Triplet of
# given sum.
def pythagoreanTriplet(n):
# Considering triplets in
# sorted order. The value
# of first element in sorted
# triplet can be at-most n/3.
for i in range(1, int(n / 3) + 1):
# The value of second element
# must be less than equal to n/2
for j in range(i + 1,
int(n / 2) + 1):
k = n - i - j
if (i * i + j * j == k * k):
print(i, ", ", j, ", ",
k, sep = "")
return
print("No Triplet")
# Driver Code
n = 12
pythagoreanTriplet(n)
# This code is contributed
# by Smitha Dinesh Semwal
C#
// C# program to find
// Pythagorean Triplet
// of given sum.
using System;
class GFG
{
static void pythagoreanTriplet(int n)
{
// Considering triplets in
// sorted order. The value
// of first element in sorted
// triplet can be at-most n/3.
for (int i = 1; i <= n / 3; i++)
{
// The value of second element
// must be less than equal to n/2
for (int j = i + 1;
j <= n / 2; j++)
{
int k = n - i - j;
if (i * i + j * j == k * k)
{
Console.Write(i + ", "+
j + ", " + k);
return;
}
}
}
Console.Write("No Triplet");
}
// Driver Code
public static void Main()
{
int n = 12;
pythagoreanTriplet(n);
}
}
// This code is contributed by Vt_m.
PHP
<?php
// PHP program to find
// Pythagorean Triplet
// of given sum.
function pythagoreanTriplet($n)
{
// Considering triplets in
// sorted order. The value
// of first element in sorted
// triplet can be at-most n/3.
for ( $i = 1; $i <= $n / 3; $i++)
{
// The value of second
// element must be less
// than equal to n/2
for ( $j = $i + 1; $j <= $n / 2; $j++)
{
$k = $n - $i - $j;
if ($i * $i + $j * $j == $k * $k)
{
echo $i , ", ", $j ,", ", $k;
return;
}
}
}
echo "No Triplet";
}
// Driver Code
$n = 12;
pythagoreanTriplet($n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// JavaScript program to find Pythagorean
// Triplet of given sum.
function pythagoreanTriplet(n)
{
// Considering triplets in
// sorted order. The value
// of first element in sorted
// triplet can be at-most n/3.
for (let i = 1; i <= n / 3; i++)
{
// The value of second element
// must be less than equal to n/2
for (let j = i + 1; j <= n / 2; j++)
{
let k = n - i - j;
if (i * i + j * j == k * k)
{
document.write(i + ", "+
j + ", " + k);
return;
}
}
}
document.write("No Triplet");
}
// Driver Code
let n = 12;
pythagoreanTriplet(n);
// This code is contributed by avijitmondal1998.
</script>
Producción :
3, 4, 5