Dados tres enteros positivos n, s y k . La tarea es imprimir todas las secuencias posibles de longitud s, comenzando con n y la diferencia absoluta entre elementos consecutivos es menor que k.
Ejemplos:
Input : n = 5, s = 3, k = 2 Output : 5 5 5 5 5 6 5 5 4 5 6 6 5 6 7 5 6 5 5 4 4 5 4 5 5 4 3 Input : n = 3, s = 2, k = 1 Output : 3 3
Observe, para obtener la diferencia absoluta entre elementos consecutivos menores que k, podemos aumentar de 0 a k – 1. De manera similar, podemos disminuir el siguiente elemento de 1 a k – 1.
Ahora, para formar la secuencia requerida, primero empuje ‘n’ al vector. Y luego intente completar el otro elemento de la secuencia haciendo una llamada recursiva para cada elemento de la secuencia. En cada llamada recursiva, ejecutamos un ciclo de 0 a k – 1 y agregamos (n + i) a la secuencia. Una vez que hagamos la secuencia de tamaño ‘s’, imprimiremos la secuencia completa y regresaremos a la función de llamada recursiva y eliminaremos (n + i).
De manera similar, podemos ejecutar el bucle de 1 a k – 1 e insertar (n – i) en la siguiente posición del elemento.
Para verificar la cantidad de elementos restantes requeridos, pasaremos el tamaño: 1 a la llamada recursiva y cuando el tamaño sea 0, imprimiremos la secuencia completa.
A continuación se muestra la implementación de este enfoque:
C++
// CPP Program all sequence of length s
// starting with n such that difference
// between consecutive element is less than k.
#include <bits/stdc++.h>
using namespace std;
// Recursive function to print all sequence
// of length s starting with n such that
// difference between consecutive element
// is less than k.
void printSequence(vector<int>& v, int n,
int s, int k)
{
// If size become 0, print the sequence.
if (s == 0) {
for (int i = 0; i < v.size(); i++)
cout << v[i] << " ";
cout << endl;
return;
}
// Increment the next element and make
// recursive call after inserting the
// (n + i) to the sequence.
for (int i = 0; i < k; i++) {
v.push_back(n + i);
printSequence(v, n + i, s - 1, k);
v.pop_back();
}
// Decrementing the next element and'
// make recursive call after inserting
// the (n - i) to the sequence.
for (int i = 1; i < k; i++) {
v.push_back(n - i);
printSequence(v, n - i, s - 1, k);
v.pop_back();
}
}
// Wrapper Function
void wrapper(int n, int s, int k)
{
vector<int> v;
v.push_back(n);
printSequence(v, n, s - 1, k);
}
// Driven Program
int main()
{
int n = 5, s = 3, k = 2;
wrapper(n, s, k);
return 0;
}
Java
// Java Program all sequence of length s
// starting with n such that difference
// between consecutive element is less than k.
import java.io.*;
import java.util.*;
public class GFG {
static List<Integer> v = new ArrayList<Integer>();
// Recursive function to print all sequence
// of length s starting with n such that
// difference between consecutive element
// is less than k.
static void printSequence(int n,
int s, int k)
{
// If size become 0, print the sequence.
if (s == 0) {
for (int i = 0; i < v.size(); i++)
System.out.print(v.get(i) + " ");
System.out.println();
return;
}
// Increment the next element and make
// recursive call after inserting the
// (n + i) to the sequence.
for (int i = 0; i < k; i++) {
v.add(n + i);
printSequence(n + i, s - 1, k);
v.remove(v.size() - 1);
}
// Decrementing the next element and'
// make recursive call after inserting
// the (n - i) to the sequence.
for (int i = 1; i < k; i++) {
v.add(n - i);
printSequence(n - i, s - 1, k);
v.remove(v.size() - 1);
}
}
// Wrapper Function
static void wrapper(int n, int s, int k)
{
v.add(n);
printSequence(n, s - 1, k);
}
// Driven Program
public static void main(String args[])
{
int n = 5, s = 3, k = 2;
wrapper(n, s, k);
}
}
// This code is contributed by Manish Shaw
// (manishshaw1)
Python3
# Python3 Program all sequence of length s
# starting with n such that difference
# between consecutive element is less than k.
# Recursive function to print all sequence
# of length s starting with n such that
# difference between consecutive element
# is less than k.
def printSequence(v, n, s, k):
# If size become 0, print the sequence.
if (s == 0) :
for i in range(0, len(v)):
print ("{} ".format(v[i]), end="")
print ("")
return;
# Increment the next element and make
# recursive call after inserting the
# (n + i) to the sequence.
for i in range(0,k):
v.append(n + i)
printSequence(v, n + i, s - 1, k)
v.pop()
# Decrementing the next element and'
# make recursive call after inserting
# the (n - i) to the sequence.
for i in range(1,k):
v.append(n - i)
printSequence(v, n - i, s - 1, k)
v.pop()
# Wrapper Function
def wrapper(n, s, k):
v = []
v.append(n)
printSequence(v, n, s - 1, k)
# Driven Program
n = 5; s = 3; k = 2;
wrapper(n, s, k);
# This code is contributed by
# Manish Shaw(manishshaw1)
C#
// C# Program all sequence of length s
// starting with n such that difference
// between consecutive element is less than k.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Collections;
class GFG {
// Recursive function to print all sequence
// of length s starting with n such that
// difference between consecutive element
// is less than k.
static void printSequence(ref List<int> v, int n,
int s, int k)
{
// If size become 0, print the sequence.
if (s == 0) {
for (int i = 0; i < v.Count; i++)
Console.Write(v[i] + " ");
Console.WriteLine();
return;
}
// Increment the next element and make
// recursive call after inserting the
// (n + i) to the sequence.
for (int i = 0; i < k; i++) {
v.Add(n + i);
printSequence(ref v, n + i, s - 1, k);
v.RemoveAt(v.Count - 1);
}
// Decrementing the next element and'
// make recursive call after inserting
// the (n - i) to the sequence.
for (int i = 1; i < k; i++) {
v.Add(n - i);
printSequence(ref v, n - i, s - 1, k);
v.RemoveAt(v.Count - 1);
}
}
// Wrapper Function
static void wrapper(int n, int s, int k)
{
List<int> v = new List<int>();
v.Add(n);
printSequence(ref v, n, s - 1, k);
}
// Driven Program
public static void Main()
{
int n = 5, s = 3, k = 2;
wrapper(n, s, k);
}
}
// This code is contributed by Manish Shaw
// (manishshaw1)
PHP
<?php
// PHP Program all sequence of
// length s starting with n
// such that difference between
// consecutive element is less than k.
// Recursive function to print
// all sequence of length s
// starting with n such that
// difference between consecutive
// element is less than k.
function printSequence($v, $n,
$s, $k)
{
// If size become 0,
// print the sequence.
if ($s == 0)
{
for ($i = 0; $i < count($v); $i++)
echo ($v[$i]." ");
echo ("\n");
return;
}
// Increment the next element
// and make recursive call
// after inserting the (n + i)
// to the sequence.
for ($i = 0; $i < $k; $i++)
{
array_push($v, $n + $i);
printSequence($v, $n + $i,
$s - 1, $k);
array_pop($v);
}
// Decrementing the next element
// and make recursive call after
// inserting the (n - i) to the
// sequence.
for ($i = 1; $i < $k; $i++)
{
array_push($v, $n - $i);
printSequence($v, $n - $i,
$s - 1, $k);
array_pop($v);
}
}
// Wrapper Function
function wrapper($n, $s, $k)
{
$v = array();;
array_push($v, $n);
printSequence($v, $n, $s - 1, $k);
}
// Driver Code
$n = 5;
$s = 3;
$k = 2;
wrapper($n, $s, $k);
// This code is contributed by
// Manish Shaw(manishshaw1)
?>
Javascript
<script>
// Javascript Program all sequence of length s
// starting with n such that difference
// between consecutive element is less than k.
v = []
// Recursive function to print all sequence
// of length s starting with n such that
// difference between consecutive element
// is less than k.
function printSequence(n, s, k)
{
// If size become 0, print the sequence.
if (s == 0) {
for (var i = 0; i < v.length; i++)
document.write( v[i] + " ");
document.write("<br>");
return;
}
// Increment the next element and make
// recursive call after inserting the
// (n + i) to the sequence.
for (var i = 0; i < k; i++) {
v.push(n + i);
printSequence(n + i, s - 1, k);
v.pop();
}
// Decrementing the next element and'
// make recursive call after inserting
// the (n - i) to the sequence.
for (var i = 1; i < k; i++) {
v.push(n - i);
printSequence(n - i, s - 1, k);
v.pop();
}
}
// Wrapper Function
function wrapper(n, s, k)
{
v.push(n);
printSequence( n, s - 1, k);
}
// Driven Program
var n = 5, s = 3, k = 2;
wrapper(n, s, k);
// This code is contributed by itsok.
</script>
Producción :
5 5 5 5 5 6 5 5 4 5 6 6 5 6 7 5 6 5 5 4 4 5 4 5 5 4 3