Serie K-Fibonacci

Dados los números enteros ‘K’ y ‘N’, la tarea es encontrar el término N de la serie K-Fibonacci.
 

En la serie K – Fibonacci, los primeros términos ‘K’ serán ‘1’ y después de eso, cada i-ésimo término de la serie será la suma de los elementos ‘K’ anteriores en la misma serie. 
 

Ejemplos: 
 

Input: N = 4, K = 2
Output: 3
The K-Fibonacci series for K=2 is 1, 1, 2, 3, ...
And, the 4th element is 3.

Input: N = 5, K = 6
Output: 1
The K-Fibonacci series for K=6 is 1, 1, 1, 1, 1, 1, 6, 11, ...

Un enfoque simple: 
 

• Primero, inicialice los primeros elementos ‘K’ a ‘1’.
• Luego, calcule la suma de los elementos ‘K’ anteriores ejecutando un ciclo de ‘i-k’ a ‘i-1’.
• Establezca el valor i-ésimo en la suma.

Complejidad de tiempo: O(N*K)
Un enfoque eficiente: 
 

• Primero, inicialice los primeros elementos ‘K’ a ‘1’.
• Cree una variable llamada ‘suma’ que se inicializará con ‘K’.
• Establezca el valor de (K+1)th elemento en sum.
• Establezca los siguientes valores como Array[i] = sum – Array[ik-1] + Array[i-1] y luego actualice sum = Array[i].
• Al final, muestre el término N de la array.

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that finds the Nth
// element of K-Fibonacci series
void solve(int N, int K)
{
    vector<long long int> Array(N + 1, 0);
 
    // If N is less than K
    // then the element is '1'
    if (N <= K) {
        cout << "1" << endl;
        return;
    }
 
    long long int i = 0, sum = K;
 
    // first k elements are 1
    for (i = 1; i <= K; ++i) {
        Array[i] = 1;
    }
 
    // (K+1)th element is K
    Array[i] = sum;
 
    // find the elements of the
    // K-Fibonacci series
    for (int i = K + 2; i <= N; ++i) {
 
        // subtract the element at index i-k-1
        // and add the element at index i-i
        // from the sum (sum contains the sum
        // of previous 'K' elements )
        Array[i] = sum - Array[i - K - 1] + Array[i - 1];
 
        // set the new sum
        sum = Array[i];
    }
    cout << Array[N] << endl;
}
 
// Driver code
int main()
{
    long long int N = 4, K = 2;
 
    // get the Nth value
    // of K-Fibonacci series
    solve(N, K);
 
    return 0;
}

// Java implementation of above approach
 
public class GFG {
 
    // Function that finds the Nth
    // element of K-Fibonacci series
    static void solve(int N, int K)
    {
        int Array[] = new int[N + 1];
         
 
        // If N is less than K
        // then the element is '1'
        if (N <= K) {
            System.out.println("1") ;
            return;
        }
 
        int i = 0 ;
        int sum = K;
 
        // first k elements are 1
        for (i = 1; i <= K; ++i) {
            Array[i] = 1;
        }
 
        // (K+1)th element is K
        Array[i] = sum;
 
        // find the elements of the
        // K-Fibonacci series
        for (i = K + 2; i <= N; ++i) {
 
            // subtract the element at index i-k-1
            // and add the element at index i-i
            // from the sum (sum contains the sum
            // of previous 'K' elements )
            Array[i] = sum - Array[i - K - 1] + Array[i - 1];
 
            // set the new sum
            sum = Array[i];
        }
        System.out.println(Array[N]);
    }
 
    public static void main(String args[])
    {
          int N = 4, K = 2;
 
            // get the Nth value
            // of K-Fibonacci series
            solve(N, K);
 
    }
    // This code is contributed by ANKITRAI1
}

# Python3 implementation of above approach
 
# Function that finds the Nth
# element of K-Fibonacci series
def solve(N, K) :
    Array = [0] * (N + 1)
     
    # If N is less than K
    # then the element is '1'
    if (N <= K) :
        print("1")
        return
     
    i = 0
    sm = K
     
    # first k elements are 1
    for i in range(1, K + 1) :
        Array[i] = 1
         
    # (K+1)th element is K
    Array[i + 1] = sm
     
    # find the elements of the
    # K-Fibonacci series
    for i in range(K + 2, N + 1) :
         
        # subtract the element at index i-k-1
        # and add the element at index i-i
        # from the sum (sum contains the sum
        # of previous 'K' elements )
        Array[i] = sm - Array[i - K - 1] + Array[i - 1]
 
        # set the new sum
        sm = Array[i]
 
    print(Array[N])
     
     
# Driver code
N = 4
K = 2
 
# get the Nth value
# of K-Fibonacci series
solve(N, K)
 
# This code is contributed by Nikita Tiwari.

// C# implementation of above approach
using System;
 
class GFG {
 
    // Function that finds the Nth
    // element of K-Fibonacci series
    public static void solve(int N, int K)
    {
        int[] Array = new int[N + 1];
 
 
        // If N is less than K
        // then the element is '1'
        if (N <= K)
        {
            Console.WriteLine("1");
            return;
        }
 
        int i = 0;
        int sum = K;
 
        // first k elements are 1
        for (i = 1; i <= K; ++i)
        {
            Array[i] = 1;
        }
 
        // (K+1)th element is K
        Array[i] = sum;
 
        // find the elements of the
        // K-Fibonacci series
        for (i = K + 2; i <= N; ++i)
        {
 
            // subtract the element at index i-k-1
            // and add the element at index i-i
            // from the sum (sum contains the sum
            // of previous 'K' elements )
            Array[i] = sum - Array[i - K - 1] +
                                 Array[i - 1];
 
            // set the new sum
            sum = Array[i];
        }
        Console.WriteLine(Array[N]);
    }
 
    // Main Method
    public static void Main(string[] args)
    {
        int N = 4, K = 2;
 
            // get the Nth value
            // of K-Fibonacci series
            solve(N, K);
 
    }
     
}
 
// This code is contributed
// by Shrikant13

<?php
// PHP implementation of above approach
 
// Function that finds the Nth
// element of K-Fibonacci series
function solve($N, $K)
{
    $Array = array_fill(0, $N + 1, NULL);
 
    // If N is less than K
    // then the element is '1'
    if ($N <= $K)
    {
        echo "1" ."\n";
        return;
    }
 
    $i = 0;
    $sum = $K;
 
    // first k elements are 1
    for ($i = 1; $i <= $K; ++$i)
    {
        $Array[$i] = 1;
    }
 
    // (K+1)th element is K
    $Array[$i] = $sum;
 
    // find the elements of the
    // K-Fibonacci series
    for ($i = $K + 2; $i <= $N; ++$i)
    {
 
        // subtract the element at index i-k-1
        // and add the element at index i-i
        // from the sum (sum contains the sum
        // of previous 'K' elements )
        $Array[$i] = $sum - $Array[$i - $K - 1] +
                            $Array[$i - 1];
 
        // set the new sum
        $sum = $Array[$i];
    }
    echo $Array[$N] . "\n";
}
 
// Driver code
$N = 4;
$K = 2;
 
// get the Nth value
// of K-Fibonacci series
solve($N, $K);
 
// This code is contributed
// by ChitraNayal
?>

<script>
 
//Javascript program to find
// next greater number than N
 
 
// Function that finds the Nth
// element of K-Fibonacci series
function solve(N, K)
{
    var Arr = new Array(N + 1);
 
    // If N is less than K
    // then the element is '1'
    if (N <= K) {
       document.write( "1" + "<br>");
        return;
    }
 
    var i = 0, sum = K;
 
    // first k elements are 1
    for (i = 1; i <= K; ++i) {
        Arr[i] = 1;
    }
 
    // (K+1)th element is K
    Arr[i] = sum;
 
    // find the elements of the
    // K-Fibonacci series
    for (var i = K + 2; i <= N; ++i) {
 
        // subtract the element at index i-k-1
        // and add the element at index i-i
        // from the sum (sum contains the sum
        // of previous 'K' elements )
        Arr[i] = sum - Arr[i - K - 1] + Arr[i - 1];
 
        // set the new sum
        sum = Arr[i];
    }
    document.write( Arr[N] + "<br>");
}
 
var N = 4, K = 2;
 
    // get the Nth value
    // of K-Fibonacci series
    solve(N, K);
         
// This code is contributed by SoumikMondal
 
</script>

3

Complejidad de tiempo: O(N)