Golomb sequence using dynamic programming
Here given code implementation process.
// C Program
// Golomb sequence using dynamic programming
#include <stdio.h>
void golombSequence(int n)
{
if (n <= 0)
{
return;
}
int dp[n + 1];
// Set initial value
dp[0] = 0;
dp[1] = 1;
printf("\n Size : %d", n);
// First sequence
printf("\n %d", dp[1]);
// Display other sequence
for (int i = 2; i <= n; ++i)
{
// Calculate golomb sequence
dp[i] = dp[i - dp[dp[i - 1]]] + 1;
printf(" %d", dp[i]);
}
}
int main()
{
// Test
golombSequence(15);
golombSequence(25);
return 0;
}
Output
Size : 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
Size : 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9
// Java program for
// Golomb sequence using dynamic programming
public class Sequence
{
public void golombSequence(int n)
{
if (n <= 0)
{
return;
}
int[] dp = new int[n + 1];
// Set initial value
dp[0] = 0;
dp[1] = 1;
System.out.print("\n Size : " + n);
// First sequence
System.out.print("\n " + dp[1]);
// Display other sequence
for (int i = 2; i <= n; ++i)
{
// Calculate golomb sequence
dp[i] = dp[i - dp[dp[i - 1]]] + 1;
// Display value
System.out.print(" " + dp[i]);
}
}
public static void main(String[] args)
{
Sequence task = new Sequence();
// Test
task.golombSequence(15);
task.golombSequence(25);
}
}
Output
Size : 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
Size : 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9
// Include header file
#include <iostream>
using namespace std;
// C++ program for
// Golomb sequence using dynamic programming
class Sequence
{
public: void golombSequence(int n)
{
if (n <= 0)
{
return;
}
int dp[n + 1];
// Set initial value
dp[0] = 0;
dp[1] = 1;
cout << "\n Size : " << n;
// First sequence
cout << "\n " << dp[1];
// Display other sequence
for (int i = 2; i <= n; ++i)
{
// Calculate golomb sequence
dp[i] = dp[i - dp[dp[i - 1]]] + 1;
// Display value
cout << " " << dp[i];
}
}
};
int main()
{
Sequence *task = new Sequence();
// Test
task->golombSequence(15);
task->golombSequence(25);
return 0;
}
Output
Size : 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
Size : 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9
// Include namespace system
using System;
// Csharp program for
// Golomb sequence using dynamic programming
public class Sequence
{
public void golombSequence(int n)
{
if (n <= 0)
{
return;
}
int[] dp = new int[n + 1];
// Set initial value
dp[0] = 0;
dp[1] = 1;
Console.Write("\n Size : " + n);
// First sequence
Console.Write("\n " + dp[1]);
// Display other sequence
for (int i = 2; i <= n; ++i)
{
// Calculate golomb sequence
dp[i] = dp[i - dp[dp[i - 1]]] + 1;
// Display value
Console.Write(" " + dp[i]);
}
}
public static void Main(String[] args)
{
Sequence task = new Sequence();
// Test
task.golombSequence(15);
task.golombSequence(25);
}
}
Output
Size : 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
Size : 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9
package main
import "fmt"
// Go program for
// Golomb sequence using dynamic programming
func golombSequence(n int) {
if n <= 0 {
return
}
var dp = make([] int, n + 1)
// Set initial value
dp[0] = 0
dp[1] = 1
fmt.Print("\n Size : ", n)
// First sequence
fmt.Print("\n ", dp[1])
// Display other sequence
for i := 2 ; i <= n ; i++ {
// Calculate golomb sequence
dp[i] = dp[i - dp[dp[i - 1]]] + 1
// Display value
fmt.Print(" ", dp[i])
}
}
func main() {
// Test
golombSequence(15)
golombSequence(25)
}
Output
Size : 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
Size : 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9
<?php
// Php program for
// Golomb sequence using dynamic programming
class Sequence
{
public function golombSequence($n)
{
if ($n <= 0)
{
return;
}
$dp = array_fill(0, $n + 1, 0);
// Set initial value
$dp[0] = 0;
$dp[1] = 1;
echo("\n Size : ".$n);
// First sequence
echo("\n ".$dp[1]);
// Display other sequence
for ($i = 2; $i <= $n; ++$i)
{
// Calculate golomb sequence
$dp[$i] = $dp[$i - $dp[$dp[$i - 1]]] + 1;
// Display value
echo(" ".$dp[$i]);
}
}
}
function main()
{
$task = new Sequence();
// Test
$task->golombSequence(15);
$task->golombSequence(25);
}
main();
Output
Size : 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
Size : 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9
// Node JS program for
// Golomb sequence using dynamic programming
class Sequence
{
golombSequence(n)
{
if (n <= 0)
{
return;
}
var dp = Array(n + 1).fill(0);
// Set initial value
dp[0] = 0;
dp[1] = 1;
process.stdout.write("\n Size : " + n);
// First sequence
process.stdout.write("\n " + dp[1]);
// Display other sequence
for (var i = 2; i <= n; ++i)
{
// Calculate golomb sequence
dp[i] = dp[i - dp[dp[i - 1]]] + 1;
// Display value
process.stdout.write(" " + dp[i]);
}
}
}
function main()
{
var task = new Sequence();
// Test
task.golombSequence(15);
task.golombSequence(25);
}
main();
Output
Size : 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
Size : 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9
# Python 3 program for
# Golomb sequence using dynamic programming
class Sequence :
def golombSequence(self, n) :
if (n <= 0) :
return
dp = [0] * (n + 1)
# Set initial value
dp[0] = 0
dp[1] = 1
print("\n Size : ", n, end = "")
# First sequence
print("\n ", dp[1], end = "")
i = 2
# Display other sequence
while (i <= n) :
# Calculate golomb sequence
dp[i] = dp[i - dp[dp[i - 1]]] + 1
# Display value
print(" ", dp[i], end = "")
i += 1
def main() :
task = Sequence()
# Test
task.golombSequence(15)
task.golombSequence(25)
if __name__ == "__main__": main()
Output
Size : 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
Size : 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9
# Ruby program for
# Golomb sequence using dynamic programming
class Sequence
def golombSequence(n)
if (n <= 0)
return
end
dp = Array.new(n + 1) {0}
# Set initial value
dp[0] = 0
dp[1] = 1
print("\n Size : ", n)
# First sequence
print("\n ", dp[1])
i = 2
# Display other sequence
while (i <= n)
# Calculate golomb sequence
dp[i] = dp[i - dp[dp[i - 1]]] + 1
# Display value
print(" ", dp[i])
i += 1
end
end
end
def main()
task = Sequence.new()
# Test
task.golombSequence(15)
task.golombSequence(25)
end
main()
Output
Size : 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
Size : 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9
// Scala program for
// Golomb sequence using dynamic programming
class Sequence()
{
def golombSequence(n: Int): Unit = {
if (n <= 0)
{
return;
}
var dp: Array[Int] = Array.fill[Int](n + 1)(0);
// Set initial value
dp(0) = 0;
dp(1) = 1;
print("\n Size : " + n);
// First sequence
print("\n " + dp(1));
var i: Int = 2;
// Display other sequence
while (i <= n)
{
// Calculate golomb sequence
dp(i) = dp(i - dp(dp(i - 1))) + 1;
// Display value
print(" " + dp(i));
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Sequence = new Sequence();
// Test
task.golombSequence(15);
task.golombSequence(25);
}
}
Output
Size : 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
Size : 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9
// Swift 4 program for
// Golomb sequence using dynamic programming
class Sequence
{
func golombSequence(_ n: Int)
{
if (n <= 0)
{
return;
}
var dp: [Int] = Array(repeating: 0, count: n + 1);
// Set initial value
dp[0] = 0;
dp[1] = 1;
print("\n Size : ", n, terminator: "");
// First sequence
print("\n ", dp[1], terminator: "");
var i: Int = 2;
// Display other sequence
while (i <= n)
{
// Calculate golomb sequence
dp[i] = dp[i - dp[dp[i - 1]]] + 1;
// Display value
print(" ", dp[i], terminator: "");
i += 1;
}
}
}
func main()
{
let task: Sequence = Sequence();
// Test
task.golombSequence(15);
task.golombSequence(25);
}
main();
Output
Size : 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
Size : 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9
// Kotlin program for
// Golomb sequence using dynamic programming
class Sequence
{
fun golombSequence(n: Int): Unit
{
if (n <= 0)
{
return;
}
val dp: Array < Int > = Array(n + 1)
{
0
};
// Set initial value
dp[0] = 0;
dp[1] = 1;
print("\n Size : " + n);
// First sequence
print("\n " + dp[1]);
var i: Int = 2;
// Display other sequence
while (i <= n)
{
// Calculate golomb sequence
dp[i] = dp[i - dp[dp[i - 1]]] + 1;
// Display value
print(" " + dp[i]);
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
val task: Sequence = Sequence();
// Test
task.golombSequence(15);
task.golombSequence(25);
}
Output
Size : 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
Size : 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment