Dadas dos arrays A y B del mismo tamaño m. Tienes que encontrar la suma de los enésimos términos de la serie de Fibonacci (el valor de cada término es la suma de los dos términos anteriores) formada por cada elemento de A como primero y cada elemento de B como segundo.
Ejemplos:
Input : {1, 2, 3}, {4, 5, 6}, n = 3
Output : 63
Explanation :
A[] = {1, 2, 3};
B[] = {4, 5, 6};
n = 3;
All the possible series upto 3rd terms are:
We have considered every possible pair of A
and B and generated third term using sum of
previous two terms.
1, 4, 5
1, 5, 6
1, 6, 7
2, 4, 6
2, 5, 7
2, 6, 8
3, 4, 7
3, 5, 8
3, 6, 9
sum = 5+6+7+6+7+8+7+8+9 = 63
Input : {5, 8, 10}, {6, 89, 5}
Output : 369
El enfoque ingenuo es tomar cada par de la array A y B y hacer una serie de Fibonacci con ellos.
Un enfoque eficiente se basa en la siguiente idea.
Guarde la serie original de Fibonacci en una array y multiplique el primer término por original_fib[n-2] y el segundo término por original_fib[n-1].
Cada elemento de la array A, así como B, vendrá m veces, así que multiplícalos por m.
(m * (B[i] * original_fib[n-1]) ) + (m * (A[i] * original_fib[n-2]) )
Usando el método eficiente se puede escribir como
original_fib[]={0, 1, 1, 2, 3, 5, 8};
A[] = {1, 2, 3};
B[] = {4, 5, 6};
n = 3;
for (i to m)
sum = sum + 3*(B[i]*original_fib[2]) + 3*(A[i]*original_fib[1])
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find sum of n-th terms
// of a Fibonacci like series formed using
// first two terms of two arrays.
#include <bits/stdc++.h>
using namespace std;
int sumNth(int A[], int B[], int m, int n)
{
int res = 0;
// if sum of first term is required
if (n == 1) {
for (int i = 0; i < m; i++)
res = res + A[i];
}
// if sum of second term is required
else if (n == 2) {
for (int i = 0; i < m; i++)
res = res + B[i] * m;
}
else {
// fibonacci series used to find the
// nth term of every series
int f[n];
f[0] = 0, f[1] = 1;
for (int i = 2; i < n; i++)
f[i] = f[i - 1] + f[i - 2];
for (int i = 0; i < m; i++) {
// as every b[i] term appears m times and
// every a[i] term also appears m times
res = res + (m * (B[i] * f[n - 1])) +
(m * (A[i] * f[n - 2]));
}
}
return res;
}
int main()
{
// m is the size of the array
int A[] = { 1, 2, 3 };
int B[] = { 4, 5, 6 };
int n = 3;
int m = sizeof(A)/sizeof(A[0]);
cout << sumNth(A, B, m, n);
return 0;
}
Java
// Java program to find sum of n-th terms
// of a Fibonacci like series formed using
// first two terms of two arrays.
public class GFG {
static int sumNth(int A[], int B[], int m, int n)
{
int res = 0;
// if sum of first term is required
if (n == 1) {
for (int i = 0; i < m; i++)
res = res + A[i];
}
// if sum of second term is required
else if (n == 2) {
for (int i = 0; i < m; i++)
res = res + B[i] * m;
}
else {
// fibonacci series used to find the
// nth term of every series
int f[] = new int[n];
f[0] = 0;
f[1] = 1;
for (int i = 2; i < n; i++)
f[i] = f[i - 1] + f[i - 2];
for (int i = 0; i < m; i++) {
// as every b[i] term appears m times and
// every a[i] term also appears m times
res = res + (m * (B[i] * f[n - 1])) +
(m * (A[i] * f[n - 2]));
}
}
return res;
}
public static void main(String args[])
{
// m is the size of the array
int A[] = { 1, 2, 3 };
int B[] = { 4, 5, 6 };
int n = 3;
int m = A.length;
System.out.println(sumNth(A, B, m, n));
}
// This code is contributed by ANKITRAI1
}
Python3
# Python3 program to find sum of # n-th terms of a Fibonacci like # series formed using first two # terms of two arrays. def sumNth(A, B, m, n): res = 0; # if sum of first term is required if (n == 1): for i in range(m): res = res + A[i]; # if sum of second term is required elif (n == 2): for i in range(m): res = res + B[i] * m; else: # fibonacci series used to find # the nth term of every series f = [0] * n; f[0] = 0; f[1] = 1; for i in range(2, n): f[i] = f[i - 1] + f[i - 2]; for i in range(m): # as every b[i] term appears m # times and every a[i] term also # appears m times res = (res + (m * (B[i] * f[n - 1])) + (m * (A[i] * f[n - 2]))); return res; # Driver code # m is the size of the array A = [1, 2, 3 ]; B = [4, 5, 6 ]; n = 3; m = len(A); print(sumNth(A, B, m, n)); # This code is contributed by mits
C#
// C# program to find sum of
// n-th terms of a Fibonacci
// like series formed using
// first two terms of two arrays.
using System;
class GFG
{
static int sumNth(int[] A, int[] B,
int m, int n)
{
int res = 0;
// if sum of first term is required
if (n == 1)
{
for (int i = 0; i < m; i++)
res = res + A[i];
}
// if sum of second term is required
else if (n == 2)
{
for (int i = 0; i < m; i++)
res = res + B[i] * m;
}
else
{
// fibonacci series used to find
// the nth term of every series
int[] f = new int[n];
f[0] = 0;
f[1] = 1;
for (int i = 2; i < n; i++)
f[i] = f[i - 1] + f[i - 2];
for (int i = 0; i < m; i++)
{
// as every b[i] term appears m
// times and every a[i] term also
// appears m times
res = res + (m * (B[i] * f[n - 1])) +
(m * (A[i] * f[n - 2]));
}
}
return res;
}
// Driver Code
public static void Main(String[] args)
{
// m is the size of the array
int[] A = { 1, 2, 3 };
int[] B = { 4, 5, 6 };
int n = 3;
int m = A.Length;
Console.WriteLine(sumNth(A, B, m, n));
}
}
// This code is contributed
// by Kirti_Mangal
PHP
<?php
// PHP program to find sum of n-th terms
// of a Fibonacci like series formed using
// first two terms of two arrays.
function sumNth(&$A, &$B, &$m, &$n)
{
$res = 0;
// if sum of first term is required
if ($n == 1)
{
for ($i = 0; $i < $m; $i++)
$res = $res + $A[$i];
}
// if sum of second term is required
else if ($n == 2)
{
for ($i = 0; $i < $m; $i++)
$res = $res + $B[$i] * $m;
}
else
{
// fibonacci series used to find
// the nth term of every series
$f = array();
$f[0] = 0;
$f[1] = 1;
for ($i = 2; $i < $n; $i++)
$f[$i] = $f[$i - 1] + $f[$i - 2];
for ($i = 0; $i < $m; $i++)
{
// as every b[i] term appears m times
// and every a[i] term also appears m times
$res = $res + ($m * ($B[$i] * $f[$n - 1])) +
($m * ($A[$i] * $f[$n - 2]));
}
}
return $res;
}
// Driver code
// m is the size of the array
$A = array(1, 2, 3 );
$B = array(4, 5, 6 );
$n = 3;
$m = sizeof($A);
echo (sumNth($A, $B, $m, $n));
// This code is contributed
// by Shivi_Aggarwal
?>
Javascript
<script>
// javascript program to find sum of n-th terms
// of a Fibonacci like series formed using
// first two terms of two arrays.
function sumNth(A , B , m , n)
{
var res = 0;
// if sum of first term is required
if (n == 1)
{
for (let i = 0; i < m; i++)
res = res + A[i];
}
// if sum of second term is required
else if (n == 2)
{
for (let i = 0; i < m; i++)
res = res + B[i] * m;
}
else
{
// fibonacci series used to find the
// nth term of every series
var f = Array(n).fill(0);
f[0] = 0;
f[1] = 1;
for (let i = 2; i < n; i++)
f[i] = f[i - 1] + f[i - 2];
for (i = 0; i < m; i++)
{
// as every b[i] term appears m times and
// every a[i] term also appears m times
res = res + (m * (B[i] * f[n - 1])) + (m * (A[i] * f[n - 2]));
}
}
return res;
}
// m is the size of the array
var A = [ 1, 2, 3 ];
var B = [ 4, 5, 6 ];
var n = 3;
var m = A.length;
document.write(sumNth(A, B, m, n));
// This code is contributed by aashish1995
</script>
Producción:
63
Complejidad de tiempo: O(M + N), donde M y N representan el tamaño de las dos arrays dadas.
Espacio auxiliar: O(N), donde N representa el tamaño de la array dada.
Publicación traducida automáticamente
Artículo escrito por Bhashkar_P y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA