Dados dos números enteros N y K , la tarea es generar una serie de N términos en los que cada término sea la suma de los K términos anteriores.
Nota: El primer término de la serie es 1 y si no hay suficientes términos anteriores, se supone que los demás términos son 0 .
Ejemplos:
Entrada: N = 8, K = 3
Salida: 1 1 2 4 7 13 24 44
Explicación:
La serie se genera de la siguiente manera:
a[0] = 1
a[1] = 1 + 0 + 0 = 1
a[2] = 1 + 1 + 0 = 2
a[3] = 2 + 1 + 1 = 4
a[4] = 4 + 2 + 1 = 7
a[5] = 7 + 4 + 2 = 13
a[6] = 13 + 7 + 4 = 24
a[7] = 24 + 13 + 7 = 44
Entrada: N = 10, K = 4
Salida: 1 1 2 4 8 15 29 56 108 208
Enfoque ingenuo: la idea es ejecutar dos bucles para generar N términos de serie. A continuación se muestra la ilustración de los pasos:
- Recorra el primer bucle de 0 a N – 1 para generar todos los términos de la serie.
- Ejecute un bucle desde max(0, i – K) hasta i para calcular la suma de los K términos anteriores.
- Actualice la suma al índice actual de la serie como el término actual.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// series in which every term is
// sum of previous K terms
#include <iostream>
using namespace std;
// Function to generate the
// series in the form of array
void sumOfPrevK(int N, int K)
{
int arr[N];
arr[0] = 1;
// Pick a starting point
for (int i = 1; i < N; i++) {
int j = i - 1, count = 0,
sum = 0;
// Find the sum of all
// elements till count < K
while (j >= 0 && count < K) {
sum += arr[j];
j--;
count++;
}
// Find the value of
// sum at i position
arr[i] = sum;
}
for (int i = 0; i < N; i++) {
cout << arr[i] << " ";
}
}
// Driver Code
int main()
{
int N = 10, K = 4;
sumOfPrevK(N, K);
return 0;
}
Java
// Java implementation to find the
// series in which every term is
// sum of previous K terms
class Sum {
// Function to generate the
// series in the form of array
void sumOfPrevK(int N, int K)
{
int arr[] = new int[N];
arr[0] = 1;
// Pick a starting point
for (int i = 1; i < N; i++) {
int j = i - 1, count = 0,
sum = 0;
// Find the sum of all
// elements till count < K
while (j >= 0 && count < K) {
sum += arr[j];
j--;
count++;
}
// Find the value of
// sum at i position
arr[i] = sum;
}
for (int i = 0; i < N; i++) {
System.out.print(arr[i] + " ");
}
}
// Driver Code
public static void main(String args[])
{
Sum s = new Sum();
int N = 10, K = 4;
s.sumOfPrevK(N, K);
}
}
Python3
# Python3 implementation to find the # series in which every term is # sum of previous K terms # Function to generate the # series in the form of array def sumOfPrevK(N, K): arr = [0 for i in range(N)] arr[0] = 1 # Pick a starting point for i in range(1,N): j = i - 1 count = 0 sum = 0 # Find the sum of all # elements till count < K while (j >= 0 and count < K): sum = sum + arr[j] j = j - 1 count = count + 1 # Find the value of # sum at i position arr[i] = sum for i in range(0, N): print(arr[i]) # Driver Code N = 10 K = 4 sumOfPrevK(N, K) # This code is contributed by Sanjit_Prasad
C#
// C# implementation to find the
// series in which every term is
// sum of previous K terms
using System;
class Sum {
// Function to generate the
// series in the form of array
void sumOfPrevK(int N, int K)
{
int []arr = new int[N];
arr[0] = 1;
// Pick a starting point
for (int i = 1; i < N; i++) {
int j = i - 1, count = 0,
sum = 0;
// Find the sum of all
// elements till count < K
while (j >= 0 && count < K) {
sum += arr[j];
j--;
count++;
}
// Find the value of
// sum at i position
arr[i] = sum;
}
for (int i = 0; i < N; i++) {
Console.Write(arr[i] + " ");
}
}
// Driver Code
public static void Main(String []args)
{
Sum s = new Sum();
int N = 10, K = 4;
s.sumOfPrevK(N, K);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript implementation to find the
// series in which every term is
// sum of previous K terms
// Function to generate the
// series in the form of array
function sumOfPrevK(N, K)
{
let arr = new Array(N);
arr[0] = 1;
// Pick a starting point
for (let i = 1; i < N; i++) {
let j = i - 1, count = 0, sum = 0;
// Find the sum of all
// elements till count < K
while (j >= 0 && count < K) {
sum += arr[j];
j--;
count++;
}
// Find the value of
// sum at i position
arr[i] = sum;
}
for (let i = 0; i < N; i++) {
document.write(arr[i] + " ");
}
}
// Driver Code
let N = 10, K = 4;
sumOfPrevK(N, K);
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
1 1 2 4 8 15 29 56 108 208
Análisis de rendimiento:
- Complejidad de tiempo: O(N * K)
- Complejidad espacial: O(N)
Enfoque eficiente: la idea es almacenar la suma actual en una variable y en cada paso restar el último K -ésimo término y agregar el último término a la suma previa para calcular cada término de la serie.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// series in which every term is
// sum of previous K terms
#include <iostream>
using namespace std;
// Function to generate the
// series in the form of array
void sumOfPrevK(int N, int K)
{
int arr[N], prevsum = 0;
arr[0] = 1;
// Pick a starting point
for (int i = 0; i < N - 1; i++) {
// Computing the previous sum
if (i < K) {
arr[i + 1] = arr[i] + prevsum;
prevsum = arr[i + 1];
}
else {
arr[i + 1] = arr[i] + prevsum
- arr[i + 1 - K];
prevsum = arr[i + 1];
}
}
// Loop to print the series
for (int i = 0; i < N; i++) {
cout << arr[i] << " ";
}
}
// Driver Code
int main()
{
int N = 8, K = 3;
sumOfPrevK(N, K);
return 0;
}
Java
// Java implementation to find the
// series in which every term is
// sum of previous K terms
class Sum {
// Function to generate the
// series in the form of array
void sumOfPrevK(int N, int K)
{
int arr[] = new int[N];
int prevsum = 0;
arr[0] = 1;
// Pick a starting point
for (int i = 0; i < N - 1; i++) {
// Computing the previous sum
if (i < K) {
arr[i + 1] = arr[i] + prevsum;
prevsum = arr[i + 1];
}
else {
arr[i + 1] = arr[i] + prevsum
- arr[i + 1 - K];
prevsum = arr[i + 1];
}
}
// Loop to print the series
for (int i = 0; i < N; i++) {
System.out.print(arr[i] + " ");
}
}
// Driver code
public static void main(String args[])
{
Sum s = new Sum();
int N = 8, K = 3;
s.sumOfPrevK(N, K);
}
}
Python3
# Python3 implementation to find the # series in which every term is # sum of previous K terms # Function to generate the # series in the form of array def sumOfPrevK(N, K): arr = [0]*N; prevsum = 0; arr[0] = 1; # Pick a starting point for i in range(N-1): # Computing the previous sum if (i < K): arr[i + 1] = arr[i] + prevsum; prevsum = arr[i + 1]; else: arr[i + 1] = arr[i] + prevsum - arr[i + 1 - K]; prevsum = arr[i + 1]; # Loop to print the series for i in range(N): print(arr[i], end=" "); # Driver code if __name__ == '__main__': N = 8; K = 3; sumOfPrevK(N, K); # This code is contributed by 29AjayKumar
C#
// C# implementation to find the
// series in which every term is
// sum of previous K terms
using System;
public class Sum {
// Function to generate the
// series in the form of array
void sumOfPrevK(int N, int K)
{
int []arr = new int[N];
int prevsum = 0;
arr[0] = 1;
// Pick a starting point
for (int i = 0; i < N - 1; i++) {
// Computing the previous sum
if (i < K) {
arr[i + 1] = arr[i] + prevsum;
prevsum = arr[i + 1];
}
else {
arr[i + 1] = arr[i] + prevsum
- arr[i + 1 - K];
prevsum = arr[i + 1];
}
}
// Loop to print the series
for (int i = 0; i < N; i++) {
Console.Write(arr[i] + " ");
}
}
// Driver code
public static void Main(String []args)
{
Sum s = new Sum();
int N = 8, K = 3;
s.sumOfPrevK(N, K);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation to find the
// series in which every term is
// sum of previous K terms
// Function to generate the
// series in the form of array
function sumOfPrevK(N, K)
{
let arr = new Array(N), prevsum = 0;
arr[0] = 1;
// Pick a starting point
for (let i = 0; i < N - 1; i++) {
// Computing the previous sum
if (i < K) {
arr[i + 1] = arr[i] + prevsum;
prevsum = arr[i + 1];
}
else {
arr[i + 1] = arr[i] + prevsum
- arr[i + 1 - K];
prevsum = arr[i + 1];
}
}
// Loop to print the series
for (let i = 0; i < N; i++) {
document.write(arr[i] + " ");
}
}
// Driver Code
let N = 8, K = 3;
sumOfPrevK(N, K);
// This code is contributed by rishavmahato348.
</script>
Análisis de complejidad:
- Complejidad de tiempo: O(N)
- Complejidad espacial: O(N)
Publicación traducida automáticamente
Artículo escrito por _shreya_garg_ y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA