Dado un número positivo n, encuentre el valor de P0 + P1 + P2 + …. + Pn donde pi indica el i-ésimo número de Perrin. Los primeros números de Perrin son 3, 0, 2, 3, 2, 5, 5, 7…….
Ejemplos:
Input : 4 Output : 8 Explanation : 3 + 0 + 2 + 3 Input : 6 Output : 15 Explanation : 3 + 0 + 2 + 3 + 2 + 5
En una publicación anterior, presentamos los Números de Perrin . En términos matemáticos, la secuencia p(n) de los números de Perrin está definida por la relación de recurrencia
P(n) = P(n-2) + P(n-3) for n > 2,
with initial values
P(0) = 3, P(1) = 0, P(2) = 2.
Método 1 (usando la fórmula recursiva del n-ésimo número de Perrin)
Simplemente podemos sumar números usando la fórmula recursiva anterior del n-ésimo número de Perrin.
C++
// C++ program to calculate sum of Perrin Numbers
#include <bits/stdc++.h>
using namespace std;
// function for sum of first n Perrin number.
int calSum(int n)
{
int a = 3, b = 0, c = 2;
if (n == 0) // n=0
return 3;
if (n == 1) // n=1
return 3;
if (n == 2) // n=2
return 5;
// calculate k=5 sum of three previous step.
int sum = 5;
// Sum remaining numbers
while (n > 2) {
int d = a + b; // calculate next term
sum += d;
a = b;
b = c;
c = d;
n--;
}
return sum;
}
// Driver code
int main()
{
int n = 9;
cout << calSum(n);
return 0;
}
Java
// Java program to calculate
// sum of Perrin Numbers
import java.lang.*;
class GFG {
// function for sum of first n Perrin number.
static int calSum(int n)
{
int a = 3, b = 0, c = 2;
if (n == 0) // n=0
return 3;
if (n == 1) // n=1
return 3;
if (n == 2) // n=2
return 5;
// calculate k=5 sum of three previous step.
int sum = 5;
// Sum remaining numbers
while (n > 2) {
// calculate next term
int d = a + b;
sum += d;
a = b;
b = c;
c = d;
n--;
}
return sum;
}
// Driver code
public static void main(String[] args)
{
int n = 9;
System.out.print(calSum(n));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python program to calculate # sum of Perrin Numbers # function for sum of first # n Perrin number. def calSum(n): a = 3 b = 0 c = 2 if (n == 0): # n = 0 return 3 if (n == 1): # n = 1 return 3 if (n == 2): # n = 2 return 5 # calculate k = 5 sum of # three previous step. sum = 5 # Sum remaining numbers while (n > 2): # calculate next term d = a + b sum = sum + d a = b b = c c = d n = n-1 return sum # Driver code n = 9 print(calSum(n)) # This code is contributed # by Anant Agarwal.
C#
// C# program to calculate
// sum of Perrin Numbers
using System;
class GFG {
// function for sum of first n Perrin number.
static int calSum(int n)
{
int a = 3, b = 0, c = 2;
if (n == 0) // n=0
return 3;
if (n == 1) // n=1
return 3;
if (n == 2) // n=2
return 5;
// calculate k=5 sum of three
// previous step.
int sum = 5;
// Sum remaining numbers
while (n > 2) {
// calculate next term
int d = a + b;
sum += d;
a = b;
b = c;
c = d;
n--;
}
return sum;
}
// Driver code
public static void Main()
{
int n = 9;
Console.WriteLine(calSum(n));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to calculate
// sum of Perrin Numbers
// function for sum of
// first n Perrin number.
function calSum($n)
{
$a = 3;
$b = 0;
$c = 2;
if ($n == 0) // n=0
return 3;
if ($n == 1) // n=1
return 3;
if ($n == 2) // n=2
return 5;
// calculate k=5 sum of
// three previous step.
$sum = 5;
// Sum remaining numbers
while ($n > 2)
{
// calculate next term
$d = $a + $b;
$sum += $d;
$a = $b;
$b = $c;
$c = $d;
$n--;
}
return $sum;
}
// Driver code
$n = 9;
echo calSum($n);
// This code is contributed by ajit.
?>
Javascript
<script>
// Javascript program to calculate
// sum of Perrin Numbers
// function for sum of first n Perrin number.
function calSum(n)
{
let a = 3, b = 0, c = 2;
if (n == 0) // n=0
return 3;
if (n == 1) // n=1
return 3;
if (n == 2) // n=2
return 5;
// calculate k=5 sum of three previous step.
let sum = 5;
// Sum remaining numbers
while (n > 2) {
// calculate next term
let d = a + b;
sum += d;
a = b;
b = c;
c = d;
n--;
}
return sum;
}
// Driver code
let n = 9;
document.write(calSum(n));
</script>
Producción:
49
Complejidad de tiempo : O (n) desde que se usa un ciclo while
Complejidad del espacio : O(1) ya que usando variables constantes
Método 2 (usando la fórmula directa)
La idea es encontrar la relación entre la suma de los números de Perrin y el n-ésimo número de Perrin.
p(i) refers to the i’th perrin number.
S(i) refers to sum of perrin numbers till p(i),
We can rewrite the relation P(n) = P(n-2) + P(n-3)
as below :
P(n-3) = P(n) - P(n-2)
Similarly,
P(n-4) = P(n-1) - P(n-3)
P(n-5) = P(n-2) - P(n-4)
. . .
. . .
. . .
P(1) = P(4) - P(2)
P(0) = P(3) - P(1)
-------------------------------
Adding all the equations, on left side, we have
{(n) + P(n-1) - P(1) - P(2) which is S(n-3).
Therefore,
S(n-3) = P(n) + P(n-1) - P(1) - P(2)
S(n-3) = P(n) + P(n-1) - 2
S(n) = P(n+3) + P(n+2) - 2
Para encontrar S(n), podemos simplemente calcular el (n+3)’ésimo y (n+2) número de Perrin y restar 2 del resultado.
Este artículo es una contribución de DANISH_RAZA . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@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