Números N-bonacci

Te dan dos números enteros N y M, e imprimes todos los términos de la serie hasta M-términos de los N-Números de Bonacci. Por ejemplo, cuando N = 2, la secuencia se convierte en Fibonacci , cuando n = 3, la secuencia se convierte en Tribonacci .

En general, en la sucesión de N-bonacci, usamos la suma de los N números anteriores del siguiente término. Por ejemplo, una secuencia de 3 bonacci es la siguiente: 
0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81

La sucesión de Fibonacci es un conjunto de números que comienza con uno o cero, seguido de un uno, y se basa en la regla de que cada número es igual a la suma de los dos números anteriores 0, 1, 1, 2, 3, 5, 8…..

Ejemplos:  

Input : N = 3, M = 8
Output : 0, 0, 1, 1, 2, 4, 7, 13
We need to print first M terms.
First three terms are 0, 0 and 1.
Fourth term is 0 + 0 + 1 = 1
Fifth term is 0 + 1 + 1 = 2
Sixth terms is 1 + 1 + 2 = 4
Seventh term is 7 (1 + 2 + 4) and eighth
term is 13 (7 + 4 + 2).

Input : N = 4, M = 10
Output : 0 0 0 1 1 2 4 8 15 29 

Método 1 (Simple) 

Inicialice los primeros N-1 términos como 0 y el N-ésimo término como 1. Ahora, para encontrar términos desde (N+1)-ésimo a M-ésimo, simplemente calculamos la suma de los N términos anteriores. 

Ejemplo: N = 4, M = 9

Los tres primeros términos son 0, 0, 0 

El cuarto término es 1. 

Los términos restantes se calculan sumando 

4 términos anteriores. 
0 0 0 1 
0 0 0 1 1 
0 0 0 1 1 2 
0 0 0 1 1 2 4 
0 0 0 1 1 2 4 8
0 0 0 1 1 2 4 8 15
0 0 0 1 1 2 4 8 15 29

// CPP program print first M terms of
// N-bonacci series.
#include <bits/stdc++.h>
using namespace std;
  
// Function to print bonacci series
void bonacciseries(long n, int m)
{
    // Assuming m >= n.
    int a[m] = { 0 };
    a[n - 1] = 1;
  
    // Computing every term as sum of previous
    // n terms.
    for (int i = n; i < m; i++)
        for (int j = i - n; j < i; j++)
            a[i] += a[j];
  
    for (int i = 0; i < m; i++)
        cout << a[i] << "  ";
}
  
// Driver's Code
int main()
{
    int N = 5, M = 15;
    bonacciseries(N, M);
    return 0;
}

// Java program print first M 
// terms of N-bonacci series.
import java.io.*;
  
class GFG
{
    // Function to print
    // bonacci series
    static void bonacciseries(int n, 
                              int m)
    {
        // Assuming m >= n.
        int []a = new int[m];
        a[n - 1] = 1;
       
        // Computing every term as 
        // sum of previous n terms.
        for (int i = n; i < m; i++)
            for (int j = i - n; j < i; j++)
                a[i] += a[j];
       
        for (int i = 0; i < m; i++)
            System.out.print(a[i] + " ");
    }
       
    // Driver Code
    public static void main(String args[])
    {
        int N = 5, M = 15;
        bonacciseries(N, M);
    }
}
   
// This code is contributed by 
// Manish Shaw(manishshaw1)

# Python program print first M 
# terms of N-bonacci series.
  
# Function to print bonacci series
def bonacciseries(n, m) :
  
    # Assuming m >= n.
    a = [0] * m
    a[n - 1] = 1
  
    # Computing every term as 
    # sum of previous n terms.
    for i in range(n, m) :
        for j in range(i - n, i) :
            a[i] = a[i] + a[j]
  
    for i in range(0, m) :
        print (a[i], end = " ")
  
# Driver Code
N = 5
M = 15
bonacciseries(N, M)
  
# This code is contributed 
# by Manish Shaw(manishshaw1)

// C# program print first M 
// terms of N-bonacci series.
using System;
  
class GFG
{
    // Function to print
    // bonacci series
    static void bonacciseries(int n, 
                              int m)
    {
        // Assuming m >= n.
        int []a = new int[m];
        Array.Clear(a, 0, a.Length);
        a[n - 1] = 1;
      
        // Computing every term as 
        // sum of previous n terms.
        for (int i = n; i < m; i++)
            for (int j = i - n; j < i; j++)
                a[i] += a[j];
      
        for (int i = 0; i < m; i++)
            Console.Write(a[i] + " ");
    }
      
    // Driver Code
    static void Main()
    {
        int N = 5, M = 15;
        bonacciseries(N, M);
    }
}
  
// This code is contributed by 
// Manish Shaw(manishshaw1)

<?php
// PHP program print first M 
// terms of N-bonacci series.
  
// Function to print bonacci series
function bonacciseries($n, $m)
{
    // Assuming m >= n.
    $a = array_fill(0, $m, 0);
    $a[$n - 1] = 1;
  
    // Computing every term as 
    // sum of previous n terms.
    for ($i = $n; $i < $m; $i++)
        for ($j = $i - $n; 
             $j < $i; $j++)
            $a[$i] += $a[$j];
  
    for ($i = 0; $i < $m; $i++)
        echo ($a[$i]." ");
}
  
// Driver Code
$N = 5; $M = 15;
bonacciseries($N, $M);
  
// This code is contributed 
// by Manish Shaw(manishshaw1)
?>

<script>
  
// Javascript program print first M 
// terms of N-bonacci series.
  
    // Function to print
    // bonacci series
    function bonacciseries(n , m) 
    {
        // Assuming m >= n.
        var a = Array(m).fill(0);
        a[n - 1] = 1;
  
        // Computing every term as
        // sum of previous n terms.
        for (i = n; i < m; i++)
            for (j = i - n; j < i; j++)
                a[i] += a[j];
  
        for (i = 0; i < m; i++)
            document.write(a[i] + " ");
    }
  
    // Driver Code
      
        var N = 5, M = 15;
        bonacciseries(N, M);
  
// This code contributed by Rajput-Ji 
  
</script>

0  0  0  0  1  1  2  4  8  16  31  61  120  236  464

Complejidad de tiempo: O (M * N) 

Espacio Auxiliar : O(M)

Método 2 (Optimizado) 

Podemos optimizar para valores grandes de N. La idea se basa en una ventana deslizante. El término actual a[i] se puede calcular como a[i-1] + a[i-1] – a[in-1] 

// CPP program print first M terms of
// N-bonacci series.
#include <bits/stdc++.h>
using namespace std;
  
// Function to print bonacci series
void bonacciseries(long n, int m)
{
  
    // Assuming m > n.
    int a[m] = { 0 };
    a[n - 1] = 1;
    a[n] = 1;
  
    // Uses sliding window
    for (int i = n + 1; i < m; i++)
        a[i] = 2 * a[i - 1] - a[i - n - 1];
  
    // Printing result
    for (int i = 0; i < m; i++)
        cout << a[i] << " ";
}
  
// Driver's Code
int main()
{
    int N = 5, M = 15;
    bonacciseries(N, M);
    return 0;
}

// Java program print first M terms of
// N-bonacci series.
class GFG {
      
    // Function to print bonacci series
    static void bonacciseries(int n, int m)
    {
      
        // Assuming m > n.
        int a[] = new int[m];
        for(int i = 0; i < m; i++)
            a[i] = 0;
              
        a[n - 1] = 1;
        a[n] = 1;
      
        // Uses sliding window
        for (int i = n + 1; i < m; i++)
            a[i] = 2 * a[i - 1] - a[i - n - 1];
      
        // Printing result
        for (int i = 0; i < m; i++)
            System.out.print(a[i] + " ");
    }
      
    // Driver's Code
    public static void main(String args[])
    {
        int N = 5, M = 15;
        bonacciseries(N, M);
    }
}
  
// This code is contributed by JaideepPyne.

# Python3 program print first M terms of
# N-bonacci series.
  
# Function to print bonacci series
def bonacciseries(n, m):
  
    # Assuming m > n.
    a = [0 for i in range(m)]
    a[n - 1] = 1
    a[n] = 1
  
    # Uses sliding window
    for i in range(n + 1, m):
        a[i] = 2 * a[i - 1] - a[i - n - 1]
  
    # Printing result
    for i in range(0, m):
        print(a[i], end=" ")
  
  
# Driver's Code
if __name__=='__main__':
    N, M = 5, 15
    bonacciseries(N, M)
  
# This code is contributed by
# Sanjit_Prasad

// Java program print 
// first M terms of
// N-bonacci series.
using System;
  
class GFG 
{
      
    // Function to print
    // bonacci series
    static void bonacciseries(int n, 
                              int m)
    {
      
        // Assuming m > n.
        int []a = new int[m];
        for(int i = 0; i < m; i++)
            a[i] = 0;
              
        a[n - 1] = 1;
        a[n] = 1;
      
        // Uses sliding window
        for (int i = n + 1; i < m; i++)
            a[i] = 2 * a[i - 1] - 
                       a[i - n - 1];
      
        // Printing result
        for (int i = 0; i < m; i++)
            Console.Write(a[i] + " ");
    }
      
    // Driver Code
    static void Main()
    {
        int N = 5, M = 15;
        bonacciseries(N, M);
    }
}
  
// This code is contributed by
// Manish Shaw(manishshaw1)

<?php
// PHP program print 
// first M terms of
// N-bonacci series.
  
// Function to print 
// N-bonacci series
function bonacciseries($n, $m)
{ 
    // Assuming m > n.
    $a = array();
    for ($i = 0; $i < $m; $i++)
        $a[$i] = 0;
    $a[$n - 1] = 1;
    $a[$n] = 1;
  
    // Uses sliding window
    for ($i = $n + 1; $i < $m; $i++)
        $a[$i] = 2 * $a[$i - 1] - 
                     $a[$i - $n - 1];
  
    // Printing result
    for ($i = 0; $i < $m; $i++)
        echo ($a[$i] . " ");
}
  
// Driver Code
$N = 5; $M = 15;
bonacciseries($N, $M);
  
// This code is contributed by 
// Manish Shaw(manishshaw1)
?>

<script>
  
// Javascript program print first M terms of
// N-bonacci series.
  
// Function to print bonacci series
    function bonacciseries(n , m) 
    {
  
        // Assuming m > n.
        var a = Array(m).fill(0);
        for (i = 0; i < m; i++)
            a[i] = 0;
  
        a[n - 1] = 1;
        a[n] = 1;
  
        // Uses sliding window
        for (i = n + 1; i < m; i++)
            a[i] = 2 * a[i - 1] - a[i - n - 1];
  
        // Printing result
        for (i = 0; i < m; i++)
            document.write(a[i] + " ");
    }
  
    // Driver's Code
      
        var N = 5, M = 15;
        bonacciseries(N, M);
  
// This code contributed by Rajput-Ji 
  
</script>

0 0 0 0 1 1 2 4 8 16 31 61 120 236 464

Complejidad de tiempo: O(M) 

Espacio Auxiliar: O(M)