Skip to main content

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
Last updated on by Kalkicode




Comment

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