Dado un número entero positivo N , la tarea es imprimir el término N de la secuencia de Van Eck . En matemáticas, la sucesión de Van Eck es una sucesión entera que se define recursivamente de la siguiente manera:
- Sea el primer término 0, es decir, a 0 = 0.
- Entonces para n >= 0, si existe un m < n tal que
am = an
- tome el m más grande y establezca a n+1 = n − m;
- De lo contrario un n+1 = 0.
- Comience con a(1)=0.
Los primeros términos de la sucesión de Van Eck son los siguientes:
0, 0, 1, 0, 2, 0, 2, 2, 1, 6, 0, 5, 0, 2, 6, 5, 4, 0, 5…
Ejemplo:
Input: N = 5 Output: 2 Input: N = 10 Output: 6
Enfoque:
como se describió anteriormente, podemos seguir los pasos a continuación para generar la secuencia de Van Eck:
- Establezca el primer término de la secuencia como 0.
- Luego aplicar repetidamente:
- Si el último término aún no se ha producido y es nuevo en la secuencia hasta el momento, establezca el siguiente término como cero.
- De lo contrario, el siguiente término es qué tan atrás ha ocurrido este último término anteriormente.
- Una vez que se genera la secuencia, podemos obtener fácilmente nuestro término n .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print Nth
// term of Van Eck's sequence
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
int sequence[MAX];
// Utility function to compute
// Van Eck's sequence
void vanEckSequence()
{
// Initialize sequence array
for (int i = 0; i < MAX; i++) {
sequence[i] = 0;
}
// Loop to generate sequence
for (int i = 0; i < MAX; i++) {
// Check if sequence[i] has occurred
// previously or is new to sequence
for (int j = i - 1; j >= 0; j--) {
if (sequence[j] == sequence[i]) {
// If occurrence found
// then the next term will be
// how far back this last term
// occurred previously
sequence[i + 1] = i - j;
break;
}
}
}
}
// Utility function to return
// Nth term of sequence
int getNthTerm(int n)
{
return sequence[n];
}
// Driver code
int main()
{
// Pre-compute Van Eck's sequence
vanEckSequence();
int n = 6;
// Print nth term of the sequence
cout << getNthTerm(n) << endl;
n = 100;
// Print nth term of the sequence
cout << getNthTerm(n) << endl;
return 0;
}
Java
// Java program to print Nth
// term of Van Eck's sequence
class GFG {
static int MAX = 1000;
// Array to store terms of sequence
static int sequence[] = new int[MAX];
// Utility function to compute
// Van Eck's sequence
static void vanEckSequence()
{
// Initialize sequence array
for (int i = 0; i < MAX - 1; i++) {
sequence[i] = 0;
}
// Loop to generate sequence
for (int i = 0; i < MAX - 1; i++) {
// Check if sequence[i] has occurred
// previously or is new to sequence
for (int j = i - 1; j >= 0; j--) {
if (sequence[j] == sequence[i]) {
// If occurrence found
// then the next term will be
// how far back this last term
// occurred previously
sequence[i + 1] = i - j;
break;
}
}
}
}
// Utility function to return
// Nth term of sequence
static int getNthTerm(int n)
{
return sequence[n];
}
// Driver code
public static void main(String[] args)
{
// Pre-compute Van Eck's sequence
vanEckSequence();
int n = 6;
// Print nth term of the sequence
System.out.println(getNthTerm(n));
n = 100;
// Print nth term of the sequence
System.out.println(getNthTerm(n));
}
}
Python3
# Python3 program to print Nth # term of Van Eck's sequence MAX = 1000 sequence = [0] * (MAX + 1); # Utility function to compute # Van Eck's sequence def vanEckSequence() : # Initialize sequence array for i in range(MAX) : sequence[i] = 0; # Loop to generate sequence for i in range(MAX) : # Check if sequence[i] has occurred # previously or is new to sequence for j in range(i - 1 , -1, -1) : if (sequence[j] == sequence[i]) : # If occurrence found # then the next term will be # how far back this last term # occurred previously sequence[i + 1] = i - j; break; # Utility function to return # Nth term of sequence def getNthTerm(n) : return sequence[n]; # Driver code if __name__ == "__main__" : # Pre-compute Van Eck's sequence vanEckSequence(); n = 6; # Print nth term of the sequence print(getNthTerm(n)); n = 100; # Print nth term of the sequence print(getNthTerm(n)); # This code is contributed by kanugargng
C#
// C# program to print Nth
// term of Van Eck's sequence
using System;
class GFG {
static int MAX = 1000;
// Array to store terms of sequence
static int[] sequence = new int[MAX];
// Utility function to compute
// Van Eck's sequence
static void vanEckSequence()
{
// Initialize sequence array
for (int i = 0; i < MAX - 1; i++) {
sequence[i] = 0;
}
// Loop to generate sequence
for (int i = 0; i < MAX - 1; i++) {
// Check if sequence[i] has occurred
// previously or is new to sequence
for (int j = i - 1; j >= 0; j--) {
if (sequence[j] == sequence[i]) {
// If occurrence found
// then the next term will be
// how far back this last term
// occurred previously
sequence[i + 1] = i - j;
break;
}
}
}
}
// Utility function to return
// Nth term of sequence
static int getNthTerm(int n)
{
return sequence[n];
}
// Driver code
public static void Main()
{
// Pre-compute Van Eck's sequence
vanEckSequence();
int n = 6;
// Print nth term of the sequence
Console.WriteLine(getNthTerm(n));
n = 100;
// Print nth term of the sequence
Console.WriteLine(getNthTerm(n));
}
}
Javascript
<script>
function getVanEckSequence(n) {
let result = [0];
let dir = {};
for( let i = 0 ; i < n ; i++) {
const currentData = result[i];
const currentPosition = i + 1;
// If number is already there, then insert the difference of positions.
if (dir[currentData]) {
result.push(currentPosition - dir[currentData]);
} else {
result.push(0);
}
// Update with the latest position
dir[currentData] = currentPosition;
}
return result;
}
console.log(getVanEckSequence(100));
// This code is contributed by Devesh
</script>
Producción:
2 23
Complejidad de tiempo: O (MAX 2 )
Espacio Auxiliar: O(MAX)
Método 2: uso de funciones lambda
No es necesario almacenar la secuencia completa para obtener el valor del término n . Podemos construir recursivamente la serie hasta el término n y encontrar solo el valor del término n usando la expresión lambda . A continuación se muestra la implementación del enfoque anterior utilizando la función lambda:
Python3
# Python3 program to find # Nth term of Van Eck's sequence # using the lambda expression # Lambda function f = lambda n, l = 0, *s : f(n-1, l in s and ~s.index(l), l, *s) \ if n else -l # The above lambda function recursively # build the sequence and store it in tuple s # The expression l in s and ~s.index(l) # returns False if l is not present in tuple s # otherwise, returns the negation of the value of # the index of l in tuple s # and is appended to tuple s # Thus, tuple s store negation of all the elements # of the sequence in reverse order # At the end, when n reaches 0, function converts # the nth term back to its actual value # and returns it. # Driver code n = 6 # Get Nth term of the sequence print(f(n)) n = 100 # Get Nth term of the sequence print(f(n))
Producción:
2 23
Referencia: https://codegolf.stackexchange.com/questions/186654/nth-term-of-van-eck-sequence