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.