En matemáticas, la sucesión de Golomb es una sucesión de enteros no decrecientes en la que el término n-ésimo es igual al número de veces que n aparece en la sucesión.
Los primeros valores son
1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, ……
Explicación de algunos términos:
el tercer término es 2, tenga en cuenta que tres aparece 2 veces.
El segundo término es 2, tenga en cuenta que dos aparece 2 veces.
El cuarto término es 3, tenga en cuenta que cuatro aparece 3 veces.
Dado un entero positivo n. La tarea es encontrar los primeros n términos de la secuencia de Golomb.
Ejemplos:
Input : n = 4 Output : 1 2 2 3 Input : n = 6 Output : 1 2 2 3 3 4
La relación de recurrencia para encontrar el enésimo término de la sucesión de Golomb:
a(1) = 1
a(n + 1) = 1 + a(n + 1 – a(a(n)))
A continuación se muestra la implementación usando Recursion:
C++
// C++ Program to find first
// n terms of Golomb sequence.
#include <bits/stdc++.h>
using namespace std;
// Return the nth element
// of Golomb sequence
int findGolomb(int n)
{
// base case
if (n == 1)
return 1;
// Recursive Step
return 1 + findGolomb(n -
findGolomb(findGolomb(n - 1)));
}
// Print the first n
// term of Golomb Sequence
void printGolomb(int n)
{
// Finding first n
// terms of Golomb Sequence.
for (int i = 1; i <= n; i++)
cout << findGolomb(i) << " ";
}
// Driver Code
int main()
{
int n = 9;
printGolomb(n);
return 0;
}
Java
// Java Program to find first
// n terms of Golomb sequence.
import java.util.*;
class GFG
{
public static int findGolomb(int n)
{
// base case
if (n == 1)
return 1;
// Recursive Step
return 1 + findGolomb(n -
findGolomb(findGolomb(n - 1)));
}
// Print the first n term of
// Golomb Sequence
public static void printGolomb(int n)
{
// Finding first n terms of
// Golomb Sequence.
for (int i = 1; i <= n; i++)
System.out.print(findGolomb(i) +
" ");
}
// Driver Code
public static void main (String[] args)
{
int n = 9;
printGolomb(n);
}
}
// This code is contributed by Akash Singh
Python3
# Python 3 Program to find first # n terms of Golomb sequence. # Return the nth element of # Golomb sequence def findGolomb(n): # base case if (n == 1): return 1 # Recursive Step return 1 + findGolomb(n - findGolomb(findGolomb(n - 1))) # Print the first n term # of Golomb Sequence def printGolomb(n): # Finding first n terms of # Golomb Sequence. for i in range(1, n + 1): print(findGolomb(i), end=" ") # Driver Code n = 9 printGolomb(n) # This code is contributed by # Smitha Dinesh Semwal
C#
// C# Program to find first n
// terms of Golomb sequence.
using System;
class GFG
{
// Return the nth element
// of Golomb sequence
static int findGolomb(int n)
{
// base case
if (n == 1)
return 1;
// Recursive Step
return 1 + findGolomb(n -
findGolomb(findGolomb(n - 1)));
}
// Print the first n term
// of Golomb Sequence
static void printGolomb(int n)
{
// Finding first n terms of
// Golomb Sequence.
for (int i = 1; i <= n; i++)
Console .Write(findGolomb(i) +
" ");
}
// Driver Code
public static void Main ()
{
int n = 9;
printGolomb(n);
}
}
// This code is contributed by vt_m
PHP
<?php
// PHP Program to find first
// n terms of Golomb sequence.
// Return the nth element
// of Golomb sequence
function findGolomb($n)
{
// base case
if ($n == 1)
return 1;
// Recursive Step
return 1 + findGolomb($n -
findGolomb(findGolomb($n - 1)));
}
// Print the first n
// term of Golomb Sequence
function printGolomb($n)
{
// Finding first n terms
// of Golomb Sequence.
for ($i = 1; $i <= $n; $i++)
echo findGolomb($i) , " ";
}
// Driver Code
$n = 9;
printGolomb($n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// javascript Program to find first
// n terms of Golomb sequence.
function findGolomb(n)
{
// base case
if (n == 1)
return 1;
// Recursive Step
return 1 + findGolomb(n - findGolomb(findGolomb(n - 1)));
}
// Print the first n term of
// Golomb Sequence
function printGolomb(n)
{
// Finding first n terms of
// Golomb Sequence.
for (let i = 1; i <= n; i++)
document.write(findGolomb(i) + " ");
}
// Driver Code
var n = 9;
printGolomb(n);
// This code is contributed by Amit Katiyar
</script>
Producción :
1 2 2 3 3 4 4 4 5
A continuación se muestra la implementación usando Programación Dinámica:
C++
// C++ Program to find first
// n terms of Golomb sequence.
#include <bits/stdc++.h>
using namespace std;
// Print the first n term
// of Golomb Sequence
void printGolomb(int n)
{
int dp[n + 1];
// base cases
dp[1] = 1;
cout << dp[1] << " ";
// Finding and printing first
// n terms of Golomb Sequence.
for (int i = 2; i <= n; i++)
{
dp[i] = 1 + dp[i - dp[dp[i - 1]]];
cout << dp[i] << " ";
}
}
// Driver Code
int main()
{
int n = 9;
printGolomb(n);
return 0;
}
Java
// Java Program to find first
// n terms of Golomb sequence.
import java.util.*;
class GFG
{
public static void printGolomb(int n)
{
int dp[] = new int[n + 1];
// base cases
dp[1] = 1;
System.out.print(dp[1] + " ");
// Finding and printing first n
// terms of Golomb Sequence.
for (int i = 2; i <= n; i++)
{
dp[i] = 1 + dp[i - dp[dp[i - 1]]];
System.out.print(dp[i] + " ");
}
}
// Driver code
public static void main (String[] args)
{
int n = 9;
printGolomb(n);
}
}
// This code is contributed by Akash Singh
Python3
# Python3 Program to find first # n terms of Golomb sequence. # Print the first n term # of Golomb Sequence def Golomb( n): dp = [0] * (n + 1) # base cases dp[1] = 1 print(dp[1], end = " " ) # Finding and print first # n terms of Golomb Sequence. for i in range(2, n + 1): dp[i] = 1 + dp[i - dp[dp[i - 1]]] print(dp[i], end = " ") # Driver Code n = 9 Golomb(n) # This code is contributed by ash264
C#
// C# Program to find first n
// terms of Golomb sequence.
using System;
class GFG
{
// Print the first n term of
// Golomb Sequence
static void printGolomb(int n)
{
int []dp = new int[n + 1];
// base cases
dp[1] = 1;
Console.Write(dp[1] + " ");
// Finding and printing first n
// terms of Golomb Sequence.
for (int i = 2; i <= n; i++)
{
dp[i] = 1 + dp[i - dp[dp[i - 1]]];
Console.Write( dp[i] + " ");
}
}
// Driver Code
public static void Main ()
{
int n = 9;
printGolomb(n);
}
}
// This code is contributed by vt_m
PHP
<?php
// PHP Program to find first
// n terms of Golomb sequence.
// Print the first n term
// of Golomb Sequence
function printGolomb($n)
{
// base cases
$dp[1] = 1;
echo $dp[1], " ";
// Finding and printing first
// n terms of Golomb Sequence.
for ($i = 2; $i <= $n; $i++)
{
$dp[$i] = 1 + $dp[$i -
$dp[$dp[$i - 1]]];
echo $dp[$i], " ";
}
}
// Driver Code
$n = 9;
printGolomb($n);
// This code is contributed by ajit.
?>
Javascript
<script>
// Javascript Program to find first
// n terms of Golomb sequence.
// Print the first n term
// of Golomb Sequence
function printGolomb( n) {
let dp = Array(n + 1).fill(0);
// base cases
dp[1] = 1;
document.write(dp[1] + " ");
// Finding and printing first n
// terms of Golomb Sequence.
for ( i = 2; i <= n; i++) {
dp[i] = 1 + dp[i - dp[dp[i - 1]]];
document.write(dp[i] + " ");
}
}
// Driver code
let n = 9;
printGolomb(n);
// This code is contributed by shikhasingrajput
</script>
Producción :
1 2 2 3 3 4 4 4 5