La m-ésima suma de los primeros n números naturales se define de la siguiente manera.
If m > 1 SUM(n, m) = SUM(SUM(n, m - 1), 1) Else SUM(n, 1) = Sum of first n natural numbers.
Nos dan m y n, necesitamos encontrar SUM(n, m).
Ejemplos:
Input : n = 4, m = 1 Output : SUM(4, 1) = 10 Explanation : 1 + 2 + 3 + 4 = 10 Input : n = 3, m = 2 Output : SUM(3, 2) = 21 Explanation : SUM(3, 2) = SUM(SUM(3, 1), 1) = SUM(6, 1) = 21
Enfoque ingenuo: podemos resolver este problema utilizando dos bucles anidados, donde el bucle externo itera para m y el bucle interno itera para n. Después de completar una sola iteración externa, debemos actualizar n ya que todo el ciclo interno se ejecutó y el valor de n debe cambiarse en ese momento. La complejidad del tiempo debe ser O(n*m).
for (int i = 1;i <= m;i++) { sum = 0; for (int j = 1;j <= n;j++) sum += j; n = sum; // update n }
Enfoque eficiente:
podemos usar una fórmula directa para la suma de los primeros n números para reducir el tiempo.
También podemos usar la recursividad. En este enfoque m = 1 será nuestra condición base y para cualquier paso intermedio SUM(n, m), llamaremos SUM (SUM(n, m-1), 1) y para un solo paso SUM(n, 1) = n * (n + 1) / 2 se utilizará. Esto reducirá nuestra complejidad de tiempo a O(m).
int SUM (int n, int m) { if (m == 1) return (n * (n + 1) / 2); int sum = SUM(n, m-1); return (sum * (sum + 1) / 2); }
A continuación se muestra la implementación de la idea anterior:
C++
// CPP program to find m-th summation #include <bits/stdc++.h> using namespace std; // Function to return mth summation int SUM(int n, int m) { // base case if (m == 1) return (n * (n + 1) / 2); int sum = SUM(n, m-1); return (sum * (sum + 1) / 2); } // driver program int main() { int n = 5; int m = 3; cout << "SUM(" << n << ", " << m << "): " << SUM(n, m); return 0; }
Java
// Java program to find m-th summation. class GFG { // Function to return mth summation static int SUM(int n, int m) { // base case if (m == 1) return (n * (n + 1) / 2); int sum = SUM(n, m - 1); return (sum * (sum + 1) / 2); } // Driver code public static void main(String[] args) { int n = 5; int m = 3; System.out.println("SUM(" + n + ", " + m + "): " + SUM(n, m)); } } // This code is contributed by Anant Agarwal.
C#
// C# program to find m-th summation. using System; class GFG { // Function to return mth summation static int SUM(int n, int m) { // base case if (m == 1) return (n * (n + 1) / 2); int sum = SUM(n, m - 1); return (sum * (sum + 1) / 2); } // Driver Code public static void Main() { int n = 5; int m = 3; Console.Write("SUM(" + n + ", " + m + "): " + SUM(n, m)); } } // This code is contributed by Nitin Mittal.
PHP
<?php // PHP program to find m-th summation // Function to return // mth summation function SUM($n, $m) { // base case if ($m == 1) return ($n * ($n + 1) / 2); $sum = SUM($n, $m - 1); return ($sum * ($sum + 1) / 2); } // Driver Code $n = 5; $m = 3; echo "SUM(" , $n , ", " , $m , "): " , SUM($n, $m); // This code is contributed by vt_m. ?>
Javascript
<script> // javascript program to find m-th summation // Function to return mth summation function SUM( n, m) { // base case if (m == 1) return (n * (n + 1) / 2); let sum = SUM(n, m-1); return (sum * (sum + 1) / 2); } // driver program let n = 5; let m = 3; document.write( "SUM(" + n + ", " + m + "): " + SUM(n, m)); // This code contributed by Rajput-Ji </script>
Producción:
SUM(5, 3): 7260
Este artículo es una contribución de Shivam Pradhan (anuj_charm) . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA