Encuentra el número de triángulos en el paso N.
Reglas: dibuja un triángulo equilátero al principio. En el i-ésimo movimiento, toma los triángulos sin color, divide cada uno de ellos en 4 partes de áreas iguales y colorea la parte central. Mantenga una cuenta de triángulos hasta el paso N.
Ejemplos:
Input : 1 Output : 5 Explanation: In 1st move we get
Input : 2 Output : 17 Explanation: In 2nd move we get
Enfoque ingenuo:
el número de triángulos en la n-ésima figura es 3 veces el número de triángulos en la (n-1)-ésima figura+2. Podemos ver por observación que la n-ésima figura se forma colocando 3 triángulos similares al de la figura (n-1) y un triángulo invertido. También tenemos en cuenta el triángulo más grande que se ha formado. Por lo tanto, el número de triángulos en la n-ésima figura se convierte en (número de triángulos en la (n-1)-ésima figura)*3 + 2.
C++
// C++ program to calculate the number of equilateral
// triangles
#include <bits/stdc++.h>
using namespace std;
// function to calculate number of triangles in Nth step
int numberOfTriangles(int n)
{
int answer[n + 1] = { 0 };
answer[0] = 1;
for (int i = 1; i <= n; i++)
answer[i] = answer[i - 1] * 3 + 2;
return answer[n];
}
// driver program
int main()
{
int n = 2;
cout << numberOfTriangles(n);
return 0;
}
Java
// Java program to find middle of three
// distinct numbers to calculate the
// number of equilateral triangles
import java.util.*;
class Triangle
{
// function to calculate number of
// triangles in Nth step
public static int numberOfTriangles(int n)
{
int[] answer = new int[n+1];
answer[0] = 1;
for (int i = 1; i <= n; i++)
answer[i] = answer[i - 1] * 3 + 2;
return answer[n];
}
// driver code
public static void main(String[] args)
{
int n = 2;
System.out.println(numberOfTriangles(n));
}
}
// This code is contributed by rishabh_jain
Python3
# Python3 code to calculate the # number of equilateral triangles # function to calculate number # of triangles in Nth step def numberOfTriangles (n) : answer = [None] * (n + 1); answer[0] = 1; i = 1 while i <= n: answer[i] = answer[i - 1] * 3 + 2; i = i + 1 return answer[n]; # Driver code n = 2 print(numberOfTriangles(n)) # This code is contributed by "rishabh_jain".
C#
// C# program to find middle of three
// distinct numbers to calculate the
// number of equilateral triangles
using System;
class Triangle
{
// function to calculate number of
// triangles in Nth step
public static int numberOfTriangles(int n)
{
int[] answer = new int[n+1];
answer[0] = 1;
for (int i = 1; i <= n; i++)
answer[i] = answer[i - 1] * 3 + 2;
return answer[n];
}
// Driver code
public static void Main()
{
int n = 2;
Console.WriteLine(numberOfTriangles(n));
}
}
// This code is contributed by vt_m
PHP
<?php
// PHP program to calculate
// the number of equilateral
// triangles
// function to calculate number
// of triangles in Nth step
function numberOfTriangles($n)
{
$answer = array();
$answer[0] = 1;
for ($i = 1; $i <= $n; $i++)
$answer[$i] = $answer[$i - 1] *
3 + 2;
return $answer[$n];
}
// Driver Code
$n = 2;
echo numberOfTriangles($n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to calculate
// the number of equilateral
// triangles
// Function to calculate number
// of triangles in Nth step
function numberOfTriangles(n)
{
let answer = new Uint8Array(n + 1);
answer[0] = 1;
for(let i = 1; i <= n; i++)
answer[i] = answer[i - 1] * 3 + 2;
return answer[n];
}
// Driver code
let n = 2;
document.write(numberOfTriangles(n));
// This code is contributed by Mayank Tyagi
</script>
Producción:
17
Complejidad de tiempo: O(n)
Una solución eficiente será derivar una fórmula para el paso N-ésimo:
si seguimos el enfoque ingenuo para cada paso, entonces obtenemos para el paso N-ésimo el número de triángulos a ser
(2*(3^n))-1.
C++
// C++ program to calculate the number of
// equilateral triangles
#include <bits/stdc++.h>
using namespace std;
// function to calculate number of triangles
// in Nth step
int numberOfTriangles(int n)
{
int ans = 2 * (pow(3, n)) - 1;
return ans;
}
// driver program
int main()
{
int n = 2;
cout << numberOfTriangles(n);
return 0;
}
Java
// Java program to find middle of three
// distinct numbers to calculate the
// number of equilateral triangles
import java.util.*;
import static java.lang.Math.pow;
class Triangle
{
// function to calculate number
// of triangles in Nth step
public static double numberOfTriangles(int n)
{
double ans = 2 * (pow(3, n)) - 1;
return ans;
}
// driver code
public static void main(String[] args)
{
int n = 2;
System.out.println(numberOfTriangles(n));
}
}
// This code is contributed by rishabh_jain
Python3
# Python3 code to calculate the # number of equilateral triangles # function to calculate number # of triangles in Nth step def numberOfTriangles (n) : ans = 2 * (pow(3, n)) - 1; return ans; # Driver code n = 2 print (numberOfTriangles(n)) # This code is contributed by "rishabh_jain".
C#
//C# program to find middle of three
// distinct numbers to calculate the
// number of equilateral triangles
using System;
class Triangle
{
// function to calculate number
// of triangles in Nth step
public static double numberOfTriangles(int n)
{
double ans = 2 * (Math.Pow(3, n)) - 1;
return ans;
}
// Driver code
public static void Main()
{
int n = 2;
Console.WriteLine(numberOfTriangles(n));
}
}
// This code is contributed by vt_m
PHP
<?php
// PHP program to calculate the
// number of equilateral triangles
// function to calculate
// number of triangles
// in Nth step
function numberOfTriangles($n)
{
$ans = 2 * (pow(3, $n)) - 1;
return $ans;
}
// Driver Code
$n = 2;
echo numberOfTriangles($n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// javascript program to find middle of three
// distinct numbers to calculate the
// number of equilateral triangles
// function to calculate number
// of triangles in Nth step
function numberOfTriangles(n)
{
var ans = 2 * (Math.pow(3, n)) - 1;
return ans;
}
// Driver code
var n = 2;
document.write(numberOfTriangles(n));
// This code is contributed by aashish1995
</script>
Producción:
17
Complejidad de tiempo: O(log n), se necesita log n para calcular 3^n.