Dado un entero n. Imprime los primeros n elementos de la secuencia de Recaman .
Ejemplos:
Input : n = 6
Output : 0, 1, 3, 6, 2, 7
Input : n = 17
Output : 0, 1, 3, 6, 2, 7, 13, 20, 12, 21,
11, 22, 10, 23, 9, 24, 8
Es básicamente una función con dominio y codominio como números naturales y 0. Se define recursivamente de la siguiente manera:
Específicamente, deje que a(n) denote el (n+1)-ésimo término. (0 ya está allí).
La regla dice:
a(0) = 0,
if n > 0 and the number is not
already included in the sequence,
a(n) = a(n - 1) - n
else
a(n) = a(n-1) + n.
A continuación se muestra una implementación simple en la que almacenamos todos los números de secuencia de n Recaman en una array. Calculamos el siguiente número usando la fórmula recursiva mencionada anteriormente.
C++
// C++ program to print n-th number in Recaman's
// sequence
#include <bits/stdc++.h>
using namespace std;
// Prints first n terms of Recaman sequence
int recaman(int n)
{
// Create an array to store terms
int arr[n];
// First term of the sequence is always 0
arr[0] = 0;
printf("%d, ", arr[0]);
// Fill remaining terms using recursive
// formula.
for (int i=1; i< n; i++)
{
int curr = arr[i-1] - i;
int j;
for (j = 0; j < i; j++)
{
// If arr[i-1] - i is negative or
// already exists.
if ((arr[j] == curr) || curr < 0)
{
curr = arr[i-1] + i;
break;
}
}
arr[i] = curr;
printf("%d, ", arr[i]);
}
}
// Driver code
int main()
{
int n = 17;
recaman(n);
return 0;
}
Java
// Java program to print n-th number in Recaman's
// sequence
import java.io.*;
class GFG {
// Prints first n terms of Recaman sequence
static void recaman(int n)
{
// Create an array to store terms
int arr[] = new int[n];
// First term of the sequence is always 0
arr[0] = 0;
System.out.print(arr[0]+" ,");
// Fill remaining terms using recursive
// formula.
for (int i = 1; i < n; i++)
{
int curr = arr[i - 1] - i;
int j;
for (j = 0; j < i; j++)
{
// If arr[i-1] - i is negative or
// already exists.
if ((arr[j] == curr) || curr < 0)
{
curr = arr[i - 1] + i;
break;
}
}
arr[i] = curr;
System.out.print(arr[i]+", ");
}
}
// Driver code
public static void main (String[] args)
{
int n = 17;
recaman(n);
}
}
// This code is contributed by vt_m
Python 3
# Python 3 program to print n-th # number in Recaman's sequence # Prints first n terms of Recaman # sequence def recaman(n): # Create an array to store terms arr = [0] * n # First term of the sequence # is always 0 arr[0] = 0 print(arr[0], end=", ") # Fill remaining terms using # recursive formula. for i in range(1, n): curr = arr[i-1] - i for j in range(0, i): # If arr[i-1] - i is # negative or already # exists. if ((arr[j] == curr) or curr < 0): curr = arr[i-1] + i break arr[i] = curr print(arr[i], end=", ") # Driver code n = 17 recaman(n) # This code is contributed by Smitha.
C#
// C# program to print n-th number in Recaman's
// sequence
using System;
class GFG {
// Prints first n terms of Recaman sequence
static void recaman(int n)
{
// Create an array to store terms
int []arr = new int[n];
// First term of the sequence is always 0
arr[0] = 0;
Console.Write(arr[0]+" ,");
// Fill remaining terms using recursive
// formula.
for (int i = 1; i < n; i++)
{
int curr = arr[i - 1] - i;
int j;
for (j = 0; j < i; j++)
{
// If arr[i-1] - i is negative or
// already exists.
if ((arr[j] == curr) || curr < 0)
{
curr = arr[i - 1] + i;
break;
}
}
arr[i] = curr;
Console.Write(arr[i]+", ");
}
}
// Driver code
public static void Main ()
{
int n = 17;
recaman(n);
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to print n-th
// number in Recaman's sequence
// Prints first n terms
// of Recaman sequence
function recaman($n)
{
// First term of the
// sequence is always 0
$arr[0] = 0;
echo $arr[0], ", ";
// Fill remaining terms
// using recursive formula.
for ($i = 1; $i < $n; $i++)
{
$curr = $arr[$i - 1] - $i;
$j;
for ($j = 0; $j < $i; $j++)
{
// If arr[i-1] - i
// is negative or
// already exists.
if (($arr[$j] == $curr) || $curr < 0)
{
$curr = $arr[$i-1] + $i;
break;
}
}
$arr[$i] = $curr;
echo $arr[$i], ", ";
}
}
// Driver Code
$n = 17;
recaman($n);
// This code is contributed by Ajit
?>
Javascript
<script>
// Javascript program to print
// n-th number in Recaman's sequence
// Prints first n terms of Recaman sequence
function recaman(n)
{
// Create an array to store terms
let arr = new Array(n);
// First term of the sequence is always 0
arr[0] = 0;
document.write(arr[0]+" ,");
// Fill remaining terms using recursive
// formula.
for (let i = 1; i < n; i++)
{
let curr = arr[i - 1] - i;
let j;
for (j = 0; j < i; j++)
{
// If arr[i-1] - i is negative or
// already exists.
if ((arr[j] == curr) || curr < 0)
{
curr = arr[i - 1] + i;
break;
}
}
arr[i] = curr;
document.write(arr[i]+", ");
}
}
let n = 17;
recaman(n);
</script>
Producción:
0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24, 8,
Complejidad de tiempo : O(n 2 ) Espacio
auxiliar : O(n), ya que se ha agregado n espacio extra Optimizaciones: Podemos usar hash para almacenar valores previamente calculados y podemos hacer que este programa funcione en O(n) tiempo.
C++
// C++ program to print n-th number in Recaman's
// sequence
#include <bits/stdc++.h>
using namespace std;
// Prints first n terms of Recaman sequence
void recaman(int n)
{
if (n <= 0)
return;
// Print first term and store it in a hash
printf("%d, ", 0);
unordered_set<int> s;
s.insert(0);
// Print remaining terms using recursive
// formula.
int prev = 0;
for (int i=1; i< n; i++)
{
int curr = prev - i;
// If arr[i-1] - i is negative or
// already exists.
if (curr < 0 || s.find(curr) != s.end())
curr = prev + i;
s.insert(curr);
printf("%d, ", curr);
prev = curr;
}
}
// Driver code
int main()
{
int n = 17;
recaman(n);
return 0;
}
Java
// Java program to print n-th number
// in Recaman's sequence
import java.util.*;
class GFG
{
// Prints first n terms of Recaman sequence
static void recaman(int n)
{
if (n <= 0)
return;
// Print first term and store it in a hash
System.out.printf("%d, ", 0);
HashSet<Integer> s = new HashSet<Integer>();
s.add(0);
// Print remaining terms using
// recursive formula.
int prev = 0;
for (int i = 1; i< n; i++)
{
int curr = prev - i;
// If arr[i-1] - i is negative or
// already exists.
if (curr < 0 || s.contains(curr))
curr = prev + i;
s.add(curr);
System.out.printf("%d, ", curr);
prev = curr;
}
}
// Driver code
public static void main(String[] args)
{
int n = 17;
recaman(n);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to print n-th number in # Recaman's sequence # Prints first n terms of Recaman sequence def recaman(n): if(n <= 0): return # Print first term and store it in a hash print(0, ",", end='') s = set([]) s.add(0) # Print remaining terms using recursive # formula. prev = 0 for i in range(1, n): curr = prev - i # If arr[i-1] - i is negative or # already exists. if(curr < 0 or curr in s): curr = prev + i s.add(curr) print(curr, ",", end='') prev = curr # Driver code if __name__=='__main__': n = 17 recaman(n) # This code is contributed by # Sanjit_Prasad
C#
// C# program to print n-th number
// in Recaman's sequence
using System;
using System.Collections.Generic;
class GFG
{
// Prints first n terms of Recaman sequence
static void recaman(int n)
{
if (n <= 0)
return;
// Print first term and store it in a hash
Console.Write("{0}, ", 0);
HashSet<int> s = new HashSet<int>();
s.Add(0);
// Print remaining terms using
// recursive formula.
int prev = 0;
for (int i = 1; i < n; i++)
{
int curr = prev - i;
// If arr[i-1] - i is negative or
// already exists.
if (curr < 0 || s.Contains(curr))
curr = prev + i;
s.Add(curr);
Console.Write("{0}, ", curr);
prev = curr;
}
}
// Driver code
public static void Main(String[] args)
{
int n = 17;
recaman(n);
}
}
// This code is contributed by Princi Singh
PHP
<?php
// PHP program to print n-th number in
// Recaman's sequence
// Prints first n terms of Recaman sequence
function recaman($n)
{
if($n <= 0)
return;
// Print first term and store
// it in a hash
print("0, ");
$s = array();
array_push($s, 0);
// Print remaining terms using recursive
// formula.
$prev = 0;
for ($i = 1; $i < $n; $i++)
{
$curr = $prev - $i;
// If arr[i-1] - i is negative or
// already exists.
if($curr < 0 or in_array($curr, $s))
$curr = $prev + $i;
array_push($s, $curr);
print($curr.", ");
$prev = $curr;
}
}
// Driver code
$n = 17;
recaman($n);
// This code is contributed by chandan_jnu
?>
Javascript
<script>
// Javascript program to print n-th number
// in Recaman's sequence
// Prints first n terms of Recaman sequence
function recaman(n)
{
if (n <= 0)
return;
// Print first term and store it in a hash
document.write(0 + ", ");
let s = new Set();
s.add(0);
// Print remaining terms using
// recursive formula.
let prev = 0;
for (let i = 1; i< n; i++)
{
let curr = prev - i;
// If arr[i-1] - i is negative or
// already exists.
if (curr < 0 || s.has(curr))
curr = prev + i;
s.add(curr);
document.write(curr + ", ");
prev = curr;
}
}
// Driver code
let n = 17;
recaman(n);
</script>
Producción:
0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24, 8,
Complejidad del tiempo: O(n)
Espacio auxiliar: O(n)
Este artículo es una contribución de Kishlay Verma . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA