Posted on by Kalkicode
Code Dynamic Programming

Clark's Triangle

In this article, we will explore Clark's Triangle, a mathematical pattern, and understand how it is generated using a C program. We will discuss the problem statement, the algorithm used to generate the triangle, and the time complexity of the code.

Introduction

Clark's Triangle is a triangular pattern of numbers named after William B. Clark. The triangle is generated by following a specific set of rules. Each row in the triangle represents the coefficients of a binomial expansion. The elements of the triangle can be calculated using a recursive formula.

Problem Statement

The problem is to generate Clark's Triangle given two integers, f and m. The triangle has m+1 rows, and each row consists of i+1 elements, where i ranges from 0 to m. The first element of each row is always 0, and the last element is always 1. The remaining elements are calculated based on the previous row.

Algorithm

The algorithm for generating Clark's Triangle can be implemented using a dynamic programming approach. Here are the steps:

1. Initialize a 2D array dp with dimensions 2 x (m + 1).
2. Set row variable to 0.
3. Iterate from i = 0 to m:
     - Set dp[row][0] to i * f.
     - Iterate from j = 0 to i:
         - If j > 0, calculate the element as follows:
             - If j == i, set dp[row][j] to 1 (last element of the row).
             - Else if row == 1, set dp[row][j] to dp[0][j] + dp[0][j - 1].
             - Else, set dp[row][j] to dp[1][j] + dp[1][j - 1].
         - Print the current element.
     - Print a new line.
     - Update the value of row to alternate between 0 and 1.

4. The generated triangle will be stored in the dp array.

Solution

// C Program for
// Clark's Triangle
#include <stdio.h>

void clarkTriangle(int f, int m)
{
	if (f <= 0 || m <= 0)
	{
		return;
	}
	int dp[2][m + 1];
	printf("\n Given f : %d m : %d \n", f, m);
	int row = 0;
	for (int i = 0; i <= m; ++i)
	{
		dp[row][0] = i *f;
		for (int j = 0; j <= i; ++j)
		{
			if (j > 0)
			{
				if (j == i)
				{
					// When last element
					dp[row][j] = 1;
				}
				else if (row == 1)
				{
					//  Combination of top 2 elements
					//  We are using only two rows . 
                    //  And changing the element in first row
					//  So get bottom 2 elements.
					dp[row][j] = dp[0][j] + dp[0][j - 1];
				}
				else
				{
					// Combination of top 2 elements
					dp[row][j] = dp[1][j] + dp[1][j - 1];
				}
			}
			printf("  %d", dp[row][j]);
		}
		printf("\n");
		if (row == 1)
		{
			row = 0;
		}
		else
		{
			row = 1;
		}
	}
}
int main()
{
	/*
	    f = 6
	    m = 10
	    ----------------------
	    [0]
	    [6, 1]
	    [12, 7, 1]
	    [18, 19, 8, 1]
	    [24, 37, 27, 9, 1]
	    [30, 61, 64, 36, 10, 1]
	    [36, 91, 125, 100, 46, 11, 1]
	    [42, 127, 216, 225, 146, 57, 12, 1]
	    [48, 169, 343, 441, 371, 203, 69, 13, 1]
	    [54, 217, 512, 784, 812, 574, 272, 82, 14, 1]
	    [60, 271, 729, 1296, 1596, 1386, 846, 354, 96, 15, 1]
	*/
	clarkTriangle(6, 10);
	/*
	    f = 5
	    m = 7
	    ----------------------
	    [0]
	    [5, 1]
	    [10, 6, 1]
	    [15, 16, 7, 1]
	    [20, 31, 23, 8, 1]
	    [25, 51, 54, 31, 9, 1]
	    [30, 76, 105, 85, 40, 10, 1]
	    [35, 106, 181, 190, 125, 50, 11, 1]
	*/
	clarkTriangle(5, 7);
	return 0;
}

Output

 Given f : 6 m : 10
  0
  6  1
  12  7  1
  18  19  8  1
  24  37  27  9  1
  30  61  64  36  10  1
  36  91  125  100  46  11  1
  42  127  216  225  146  57  12  1
  48  169  343  441  371  203  69  13  1
  54  217  512  784  812  574  272  82  14  1
  60  271  729  1296  1596  1386  846  354  96  15  1

 Given f : 5 m : 7
  0
  5  1
  10  6  1
  15  16  7  1
  20  31  23  8  1
  25  51  54  31  9  1
  30  76  105  85  40  10  1
  35  106  181  190  125  50  11  1
/*
    Java program for
    Clark's Triangle
*/
public class Triangle
{
	public void clarkTriangle(int f, int m)
	{
		if (f <= 0 || m <= 0)
		{
			return;
		}
		int[][] dp = new int[2][m + 1];
		System.out.print("\n Given f : " + f + " m : " + m + " \n");
		int row = 0;
		for (int i = 0; i <= m; ++i)
		{
			dp[row][0] = i * f;
			for (int j = 0; j <= i; ++j)
			{
				if (j > 0)
				{
					if (j == i)
					{
						// When last element
						dp[row][j] = 1;
					}
					else if (row == 1)
					{
						//  Combination of top 2 elements
						//  We are using only two rows . 
						//  And changing the element in first row
						//  So get bottom 2 elements.
						dp[row][j] = dp[0][j] + dp[0][j - 1];
					}
					else
					{
						// Combination of top 2 elements
						dp[row][j] = dp[1][j] + dp[1][j - 1];
					}
				}
				System.out.print(" " + dp[row][j]);
			}
			System.out.print("\n");
			if (row == 1)
			{
				row = 0;
			}
			else
			{
				row = 1;
			}
		}
	}
	public static void main(String[] args)
	{
		Triangle task = new Triangle();
		/*
		    f = 6
		    m = 10
		    ----------------------
		    [0]
		    [6, 1]
		    [12, 7, 1]
		    [18, 19, 8, 1]
		    [24, 37, 27, 9, 1]
		    [30, 61, 64, 36, 10, 1]
		    [36, 91, 125, 100, 46, 11, 1]
		    [42, 127, 216, 225, 146, 57, 12, 1]
		    [48, 169, 343, 441, 371, 203, 69, 13, 1]
		    [54, 217, 512, 784, 812, 574, 272, 82, 14, 1]
		    [60, 271, 729, 1296, 1596, 1386, 846, 354, 96, 15, 1]
		*/
		task.clarkTriangle(6, 10);
		/*
		    f = 5
		    m = 7
		    ----------------------
		    [0]
		    [5, 1]
		    [10, 6, 1]
		    [15, 16, 7, 1]
		    [20, 31, 23, 8, 1]
		    [25, 51, 54, 31, 9, 1]
		    [30, 76, 105, 85, 40, 10, 1]
		    [35, 106, 181, 190, 125, 50, 11, 1]
		*/
		task.clarkTriangle(5, 7);
	}
}

Output

 Given f : 6 m : 10
 0
 6 1
 12 7 1
 18 19 8 1
 24 37 27 9 1
 30 61 64 36 10 1
 36 91 125 100 46 11 1
 42 127 216 225 146 57 12 1
 48 169 343 441 371 203 69 13 1
 54 217 512 784 812 574 272 82 14 1
 60 271 729 1296 1596 1386 846 354 96 15 1

 Given f : 5 m : 7
 0
 5 1
 10 6 1
 15 16 7 1
 20 31 23 8 1
 25 51 54 31 9 1
 30 76 105 85 40 10 1
 35 106 181 190 125 50 11 1
// Include header file
#include <iostream>

using namespace std;
/*
    C++ program for
    Clark's Triangle
*/
class Triangle
{
	public: void clarkTriangle(int f, int m)
	{
		if (f <= 0 || m <= 0)
		{
			return;
		}
		int dp[2][m + 1];
		cout << "\n Given f : " << f << " m : " << m << " \n";
		int row = 0;
		for (int i = 0; i <= m; ++i)
		{
			dp[row][0] = i *f;
			for (int j = 0; j <= i; ++j)
			{
				if (j > 0)
				{
					if (j == i)
					{
						// When last element
						dp[row][j] = 1;
					}
					else if (row == 1)
					{
						//  Combination of top 2 elements
						//  We are using only two rows .
						//  And changing the element in first row
						//  So get bottom 2 elements.
						dp[row][j] = dp[0][j] + dp[0][j - 1];
					}
					else
					{
						// Combination of top 2 elements
						dp[row][j] = dp[1][j] + dp[1][j - 1];
					}
				}
				cout << " " << dp[row][j];
			}
			cout << "\n";
			if (row == 1)
			{
				row = 0;
			}
			else
			{
				row = 1;
			}
		}
	}
};
int main()
{
	Triangle *task = new Triangle();
	/*
	    f = 6
	    m = 10
	    ----------------------
	    [0]
	    [6, 1]
	    [12, 7, 1]
	    [18, 19, 8, 1]
	    [24, 37, 27, 9, 1]
	    [30, 61, 64, 36, 10, 1]
	    [36, 91, 125, 100, 46, 11, 1]
	    [42, 127, 216, 225, 146, 57, 12, 1]
	    [48, 169, 343, 441, 371, 203, 69, 13, 1]
	    [54, 217, 512, 784, 812, 574, 272, 82, 14, 1]
	    [60, 271, 729, 1296, 1596, 1386, 846, 354, 96, 15, 1]
	*/
	task->clarkTriangle(6, 10);
	/*
	    f = 5
	    m = 7
	    ----------------------
	    [0]
	    [5, 1]
	    [10, 6, 1]
	    [15, 16, 7, 1]
	    [20, 31, 23, 8, 1]
	    [25, 51, 54, 31, 9, 1]
	    [30, 76, 105, 85, 40, 10, 1]
	    [35, 106, 181, 190, 125, 50, 11, 1]
	*/
	task->clarkTriangle(5, 7);
	return 0;
}

Output

 Given f : 6 m : 10
 0
 6 1
 12 7 1
 18 19 8 1
 24 37 27 9 1
 30 61 64 36 10 1
 36 91 125 100 46 11 1
 42 127 216 225 146 57 12 1
 48 169 343 441 371 203 69 13 1
 54 217 512 784 812 574 272 82 14 1
 60 271 729 1296 1596 1386 846 354 96 15 1

 Given f : 5 m : 7
 0
 5 1
 10 6 1
 15 16 7 1
 20 31 23 8 1
 25 51 54 31 9 1
 30 76 105 85 40 10 1
 35 106 181 190 125 50 11 1
// Include namespace system
using System;
/*
    Csharp program for
    Clark's Triangle
*/
public class Triangle
{
	public void clarkTriangle(int f, int m)
	{
		if (f <= 0 || m <= 0)
		{
			return;
		}
		int[,] dp = new int[2,m + 1];
		Console.Write("\n Given f : " + f + " m : " + m + " \n");
		int row = 0;
		for (int i = 0; i <= m; ++i)
		{
			dp[row,0] = i * f;
			for (int j = 0; j <= i; ++j)
			{
				if (j > 0)
				{
					if (j == i)
					{
						// When last element
						dp[row,j] = 1;
					}
					else if (row == 1)
					{
						//  Combination of top 2 elements
						//  We are using only two rows .
						//  And changing the element in first row
						//  So get bottom 2 elements.
						dp[row,j] = dp[0,j] + dp[0,j - 1];
					}
					else
					{
						// Combination of top 2 elements
						dp[row,j] = dp[1,j] + dp[1,j - 1];
					}
				}
				Console.Write(" " + dp[row,j]);
			}
			Console.Write("\n");
			if (row == 1)
			{
				row = 0;
			}
			else
			{
				row = 1;
			}
		}
	}
	public static void Main(String[] args)
	{
		Triangle task = new Triangle();
		/*
		    f = 6
		    m = 10
		    ----------------------
		    [0]
		    [6, 1]
		    [12, 7, 1]
		    [18, 19, 8, 1]
		    [24, 37, 27, 9, 1]
		    [30, 61, 64, 36, 10, 1]
		    [36, 91, 125, 100, 46, 11, 1]
		    [42, 127, 216, 225, 146, 57, 12, 1]
		    [48, 169, 343, 441, 371, 203, 69, 13, 1]
		    [54, 217, 512, 784, 812, 574, 272, 82, 14, 1]
		    [60, 271, 729, 1296, 1596, 1386, 846, 354, 96, 15, 1]
		*/
		task.clarkTriangle(6, 10);
		/*
		    f = 5
		    m = 7
		    ----------------------
		    [0]
		    [5, 1]
		    [10, 6, 1]
		    [15, 16, 7, 1]
		    [20, 31, 23, 8, 1]
		    [25, 51, 54, 31, 9, 1]
		    [30, 76, 105, 85, 40, 10, 1]
		    [35, 106, 181, 190, 125, 50, 11, 1]
		*/
		task.clarkTriangle(5, 7);
	}
}

Output

 Given f : 6 m : 10
 0
 6 1
 12 7 1
 18 19 8 1
 24 37 27 9 1
 30 61 64 36 10 1
 36 91 125 100 46 11 1
 42 127 216 225 146 57 12 1
 48 169 343 441 371 203 69 13 1
 54 217 512 784 812 574 272 82 14 1
 60 271 729 1296 1596 1386 846 354 96 15 1

 Given f : 5 m : 7
 0
 5 1
 10 6 1
 15 16 7 1
 20 31 23 8 1
 25 51 54 31 9 1
 30 76 105 85 40 10 1
 35 106 181 190 125 50 11 1
package main
import "fmt"
/*
    Go program for
    Clark's Triangle
*/

func clarkTriangle(f, m int) {
	if f <= 0 || m <= 0 {
		return
	}
	var dp = make([][] int,2)
	for i:= 0; i < 2; i++{
		dp[i] = make([]int,m + 1);
	}
	fmt.Print("\n Given f : ", f, " m : ", m, " \n")
	var row int = 0
	for i := 0 ; i <= m ; i++ {
		dp[row][0] = i * f
		for j := 0 ; j <= i ; j++ {
			if j > 0 {
				if j == i {
					// When last element
					dp[row][j] = 1
				} else if row == 1 {
					//  Combination of top 2 elements
					//  We are using only two rows .
					//  And changing the element in first row
					//  So get bottom 2 elements.
					dp[row][j] = dp[0][j] + dp[0][j - 1]
				} else {
					// Combination of top 2 elements
					dp[row][j] = dp[1][j] + dp[1][j - 1]
				}
			}
			fmt.Print(" ", dp[row][j])
		}
		fmt.Print("\n")
		if row == 1 {
			row = 0
		} else {
			row = 1
		}
	}
}
func main() {

	/*
	    f = 6
	    m = 10
	    ----------------------
	    [0]
	    [6, 1]
	    [12, 7, 1]
	    [18, 19, 8, 1]
	    [24, 37, 27, 9, 1]
	    [30, 61, 64, 36, 10, 1]
	    [36, 91, 125, 100, 46, 11, 1]
	    [42, 127, 216, 225, 146, 57, 12, 1]
	    [48, 169, 343, 441, 371, 203, 69, 13, 1]
	    [54, 217, 512, 784, 812, 574, 272, 82, 14, 1]
	    [60, 271, 729, 1296, 1596, 1386, 846, 354, 96, 15, 1]
	*/
	clarkTriangle(6, 10)
	/*
	    f = 5
	    m = 7
	    ----------------------
	    [0]
	    [5, 1]
	    [10, 6, 1]
	    [15, 16, 7, 1]
	    [20, 31, 23, 8, 1]
	    [25, 51, 54, 31, 9, 1]
	    [30, 76, 105, 85, 40, 10, 1]
	    [35, 106, 181, 190, 125, 50, 11, 1]
	*/
	clarkTriangle(5, 7)
}

Output

 Given f : 6 m : 10
 0
 6 1
 12 7 1
 18 19 8 1
 24 37 27 9 1
 30 61 64 36 10 1
 36 91 125 100 46 11 1
 42 127 216 225 146 57 12 1
 48 169 343 441 371 203 69 13 1
 54 217 512 784 812 574 272 82 14 1
 60 271 729 1296 1596 1386 846 354 96 15 1

 Given f : 5 m : 7
 0
 5 1
 10 6 1
 15 16 7 1
 20 31 23 8 1
 25 51 54 31 9 1
 30 76 105 85 40 10 1
 35 106 181 190 125 50 11 1
<?php
/*
    Php program for
    Clark's Triangle
*/
class Triangle
{
	public	function clarkTriangle($f, $m)
	{
		if ($f <= 0 || $m <= 0)
		{
			return;
		}
		$dp = array_fill(0, 2, array_fill(0, $m + 1, 0));
		echo("\n Given f : ".$f.
			" m : ".$m.
			" \n");
		$row = 0;
		for ($i = 0; $i <= $m; ++$i)
		{
			$dp[$row][0] = $i * $f;
			for ($j = 0; $j <= $i; ++$j)
			{
				if ($j > 0)
				{
					if ($j == $i)
					{
						// When last element
						$dp[$row][$j] = 1;
					}
					else if ($row == 1)
					{
						//  Combination of top 2 elements
						//  We are using only two rows .
						//  And changing the element in first row
						//  So get bottom 2 elements.
						$dp[$row][$j] = $dp[0][$j] + $dp[0][$j - 1];
					}
					else
					{
						// Combination of top 2 elements
						$dp[$row][$j] = $dp[1][$j] + $dp[1][$j - 1];
					}
				}
				echo(" ".$dp[$row][$j]);
			}
			echo("\n");
			if ($row == 1)
			{
				$row = 0;
			}
			else
			{
				$row = 1;
			}
		}
	}
}

function main()
{
	$task = new Triangle();
	/*
	    f = 6
	    m = 10
	    ----------------------
	    [0]
	    [6, 1]
	    [12, 7, 1]
	    [18, 19, 8, 1]
	    [24, 37, 27, 9, 1]
	    [30, 61, 64, 36, 10, 1]
	    [36, 91, 125, 100, 46, 11, 1]
	    [42, 127, 216, 225, 146, 57, 12, 1]
	    [48, 169, 343, 441, 371, 203, 69, 13, 1]
	    [54, 217, 512, 784, 812, 574, 272, 82, 14, 1]
	    [60, 271, 729, 1296, 1596, 1386, 846, 354, 96, 15, 1]
	*/
	$task->clarkTriangle(6, 10);
	/*
	    f = 5
	    m = 7
	    ----------------------
	    [0]
	    [5, 1]
	    [10, 6, 1]
	    [15, 16, 7, 1]
	    [20, 31, 23, 8, 1]
	    [25, 51, 54, 31, 9, 1]
	    [30, 76, 105, 85, 40, 10, 1]
	    [35, 106, 181, 190, 125, 50, 11, 1]
	*/
	$task->clarkTriangle(5, 7);
}
main();

Output

 Given f : 6 m : 10
 0
 6 1
 12 7 1
 18 19 8 1
 24 37 27 9 1
 30 61 64 36 10 1
 36 91 125 100 46 11 1
 42 127 216 225 146 57 12 1
 48 169 343 441 371 203 69 13 1
 54 217 512 784 812 574 272 82 14 1
 60 271 729 1296 1596 1386 846 354 96 15 1

 Given f : 5 m : 7
 0
 5 1
 10 6 1
 15 16 7 1
 20 31 23 8 1
 25 51 54 31 9 1
 30 76 105 85 40 10 1
 35 106 181 190 125 50 11 1
/*
    Node JS program for
    Clark's Triangle
*/
class Triangle
{
	clarkTriangle(f, m)
	{
		if (f <= 0 || m <= 0)
		{
			return;
		}
		var dp = Array(2).fill(0).map(() => new Array(m + 1).fill(0));
		process.stdout.write("\n Given f : " + f + " m : " + m + " \n");
		var row = 0;
		for (var i = 0; i <= m; ++i)
		{
			dp[row][0] = i * f;
			for (var j = 0; j <= i; ++j)
			{
				if (j > 0)
				{
					if (j == i)
					{
						// When last element
						dp[row][j] = 1;
					}
					else if (row == 1)
					{
						//  Combination of top 2 elements
						//  We are using only two rows .
						//  And changing the element in first row
						//  So get bottom 2 elements.
						dp[row][j] = dp[0][j] + dp[0][j - 1];
					}
					else
					{
						// Combination of top 2 elements
						dp[row][j] = dp[1][j] + dp[1][j - 1];
					}
				}
				process.stdout.write(" " + dp[row][j]);
			}
			process.stdout.write("\n");
			if (row == 1)
			{
				row = 0;
			}
			else
			{
				row = 1;
			}
		}
	}
}

function main()
{
	var task = new Triangle();
	/*
	    f = 6
	    m = 10
	    ----------------------
	    [0]
	    [6, 1]
	    [12, 7, 1]
	    [18, 19, 8, 1]
	    [24, 37, 27, 9, 1]
	    [30, 61, 64, 36, 10, 1]
	    [36, 91, 125, 100, 46, 11, 1]
	    [42, 127, 216, 225, 146, 57, 12, 1]
	    [48, 169, 343, 441, 371, 203, 69, 13, 1]
	    [54, 217, 512, 784, 812, 574, 272, 82, 14, 1]
	    [60, 271, 729, 1296, 1596, 1386, 846, 354, 96, 15, 1]
	*/
	task.clarkTriangle(6, 10);
	/*
	    f = 5
	    m = 7
	    ----------------------
	    [0]
	    [5, 1]
	    [10, 6, 1]
	    [15, 16, 7, 1]
	    [20, 31, 23, 8, 1]
	    [25, 51, 54, 31, 9, 1]
	    [30, 76, 105, 85, 40, 10, 1]
	    [35, 106, 181, 190, 125, 50, 11, 1]
	*/
	task.clarkTriangle(5, 7);
}
main();

Output

 Given f : 6 m : 10
 0
 6 1
 12 7 1
 18 19 8 1
 24 37 27 9 1
 30 61 64 36 10 1
 36 91 125 100 46 11 1
 42 127 216 225 146 57 12 1
 48 169 343 441 371 203 69 13 1
 54 217 512 784 812 574 272 82 14 1
 60 271 729 1296 1596 1386 846 354 96 15 1

 Given f : 5 m : 7
 0
 5 1
 10 6 1
 15 16 7 1
 20 31 23 8 1
 25 51 54 31 9 1
 30 76 105 85 40 10 1
 35 106 181 190 125 50 11 1
#    Python 3 program for
#    Clark's Triangle
class Triangle :
	def clarkTriangle(self, f, m) :
		if (f <= 0 or m <= 0) :
			return
		
		dp = [[0] * (m + 1) for _ in range(2) ]
		print("\n Given f : ", f ," m : ", m ," ")
		row = 0
		i = 0
		while (i <= m) :
			dp[row][0] = i * f
			j = 0
			while (j <= i) :
				if (j > 0) :
					if (j == i) :
						#  When last element
						dp[row][j] = 1
					elif (row == 1) :
						#   Combination of top 2 elements
						#   We are using only two rows .
						#   And changing the element in first row
						#   So get bottom 2 elements.
						dp[row][j] = dp[0][j] + dp[0][j - 1]
					else :
						#  Combination of top 2 elements
						dp[row][j] = dp[1][j] + dp[1][j - 1]
					
				
				print(" ", dp[row][j], end = "")
				j += 1
			
			print(end = "\n")
			if (row == 1) :
				row = 0
			else :
				row = 1
			
			i += 1
		
	

def main() :
	task = Triangle()
	#    f = 6
	#    m = 10
	#    ----------------------
	#    [0]
	#    [6, 1]
	#    [12, 7, 1]
	#    [18, 19, 8, 1]
	#    [24, 37, 27, 9, 1]
	#    [30, 61, 64, 36, 10, 1]
	#    [36, 91, 125, 100, 46, 11, 1]
	#    [42, 127, 216, 225, 146, 57, 12, 1]
	#    [48, 169, 343, 441, 371, 203, 69, 13, 1]
	#    [54, 217, 512, 784, 812, 574, 272, 82, 14, 1]
	#    [60, 271, 729, 1296, 1596, 1386, 846, 354, 96, 15, 1]
	task.clarkTriangle(6, 10)
	#    f = 5
	#    m = 7
	#    ----------------------
	#    [0]
	#    [5, 1]
	#    [10, 6, 1]
	#    [15, 16, 7, 1]
	#    [20, 31, 23, 8, 1]
	#    [25, 51, 54, 31, 9, 1]
	#    [30, 76, 105, 85, 40, 10, 1]
	#    [35, 106, 181, 190, 125, 50, 11, 1]
	task.clarkTriangle(5, 7)

if __name__ == "__main__": main()

Output

 Given f :  6  m :  10
  0
  6  1
  12  7  1
  18  19  8  1
  24  37  27  9  1
  30  61  64  36  10  1
  36  91  125  100  46  11  1
  42  127  216  225  146  57  12  1
  48  169  343  441  371  203  69  13  1
  54  217  512  784  812  574  272  82  14  1
  60  271  729  1296  1596  1386  846  354  96  15  1

 Given f :  5  m :  7
  0
  5  1
  10  6  1
  15  16  7  1
  20  31  23  8  1
  25  51  54  31  9  1
  30  76  105  85  40  10  1
  35  106  181  190  125  50  11  1
#    Ruby program for
#    Clark's Triangle
class Triangle 
	def clarkTriangle(f, m) 
		if (f <= 0 || m <= 0) 
			return
		end

		dp = Array.new(2) {Array.new(m + 1) {0}}
		print("\n Given f : ", f ," m : ", m ," \n")
		row = 0
		i = 0
		while (i <= m) 
			dp[row][0] = i * f
			j = 0
			while (j <= i) 
				if (j > 0) 
					if (j == i) 
						#  When last element
						dp[row][j] = 1
					elsif (row == 1) 
						#   Combination of top 2 elements
						#   We are using only two rows .
						#   And changing the element in first row
						#   So get bottom 2 elements.
						dp[row][j] = dp[0][j] + dp[0][j - 1]
					else
 
						#  Combination of top 2 elements
						dp[row][j] = dp[1][j] + dp[1][j - 1]
					end

				end

				print(" ", dp[row][j])
				j += 1
			end

			print("\n")
			if (row == 1) 
				row = 0
			else
 
				row = 1
			end

			i += 1
		end

	end

end

def main() 
	task = Triangle.new()
	#    f = 6
	#    m = 10
	#    ----------------------
	#    [0]
	#    [6, 1]
	#    [12, 7, 1]
	#    [18, 19, 8, 1]
	#    [24, 37, 27, 9, 1]
	#    [30, 61, 64, 36, 10, 1]
	#    [36, 91, 125, 100, 46, 11, 1]
	#    [42, 127, 216, 225, 146, 57, 12, 1]
	#    [48, 169, 343, 441, 371, 203, 69, 13, 1]
	#    [54, 217, 512, 784, 812, 574, 272, 82, 14, 1]
	#    [60, 271, 729, 1296, 1596, 1386, 846, 354, 96, 15, 1]
	task.clarkTriangle(6, 10)
	#    f = 5
	#    m = 7
	#    ----------------------
	#    [0]
	#    [5, 1]
	#    [10, 6, 1]
	#    [15, 16, 7, 1]
	#    [20, 31, 23, 8, 1]
	#    [25, 51, 54, 31, 9, 1]
	#    [30, 76, 105, 85, 40, 10, 1]
	#    [35, 106, 181, 190, 125, 50, 11, 1]
	task.clarkTriangle(5, 7)
end

main()

Output

 Given f : 6 m : 10 
 0
 6 1
 12 7 1
 18 19 8 1
 24 37 27 9 1
 30 61 64 36 10 1
 36 91 125 100 46 11 1
 42 127 216 225 146 57 12 1
 48 169 343 441 371 203 69 13 1
 54 217 512 784 812 574 272 82 14 1
 60 271 729 1296 1596 1386 846 354 96 15 1

 Given f : 5 m : 7 
 0
 5 1
 10 6 1
 15 16 7 1
 20 31 23 8 1
 25 51 54 31 9 1
 30 76 105 85 40 10 1
 35 106 181 190 125 50 11 1

/*
    Scala program for
    Clark's Triangle
*/
class Triangle()
{
	def clarkTriangle(f: Int, m: Int): Unit = {
		if (f <= 0 || m <= 0)
		{
			return;
		}
		var dp: Array[Array[Int]] = Array.fill[Int](2, m + 1)(0);
		print("\n Given f : " + f + " m : " + m + " \n");
		var row: Int = 0;
		var i: Int = 0;
		while (i <= m)
		{
			dp(row)(0) = i * f;
			var j: Int = 0;
			while (j <= i)
			{
				if (j > 0)
				{
					if (j == i)
					{
						// When last element
						dp(row)(j) = 1;
					}
					else if (row == 1)
					{
						//  Combination of top 2 elements
						//  We are using only two rows .
						//  And changing the element in first row
						//  So get bottom 2 elements.
						dp(row)(j) = dp(0)(j) + dp(0)(j - 1);
					}
					else
					{
						// Combination of top 2 elements
						dp(row)(j) = dp(1)(j) + dp(1)(j - 1);
					}
				}
				print(" " + dp(row)(j));
				j += 1;
			}
			print("\n");
			if (row == 1)
			{
				row = 0;
			}
			else
			{
				row = 1;
			}
			i += 1;
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Triangle = new Triangle();
		/*
		    f = 6
		    m = 10
		    ----------------------
		    [0]
		    [6, 1]
		    [12, 7, 1]
		    [18, 19, 8, 1]
		    [24, 37, 27, 9, 1]
		    [30, 61, 64, 36, 10, 1]
		    [36, 91, 125, 100, 46, 11, 1]
		    [42, 127, 216, 225, 146, 57, 12, 1]
		    [48, 169, 343, 441, 371, 203, 69, 13, 1]
		    [54, 217, 512, 784, 812, 574, 272, 82, 14, 1]
		    [60, 271, 729, 1296, 1596, 1386, 846, 354, 96, 15, 1]
		*/
		task.clarkTriangle(6, 10);
		/*
		    f = 5
		    m = 7
		    ----------------------
		    [0]
		    [5, 1]
		    [10, 6, 1]
		    [15, 16, 7, 1]
		    [20, 31, 23, 8, 1]
		    [25, 51, 54, 31, 9, 1]
		    [30, 76, 105, 85, 40, 10, 1]
		    [35, 106, 181, 190, 125, 50, 11, 1]
		*/
		task.clarkTriangle(5, 7);
	}
}

Output

 Given f : 6 m : 10
 0
 6 1
 12 7 1
 18 19 8 1
 24 37 27 9 1
 30 61 64 36 10 1
 36 91 125 100 46 11 1
 42 127 216 225 146 57 12 1
 48 169 343 441 371 203 69 13 1
 54 217 512 784 812 574 272 82 14 1
 60 271 729 1296 1596 1386 846 354 96 15 1

 Given f : 5 m : 7
 0
 5 1
 10 6 1
 15 16 7 1
 20 31 23 8 1
 25 51 54 31 9 1
 30 76 105 85 40 10 1
 35 106 181 190 125 50 11 1
/*
    Swift 4 program for
    Clark's Triangle
*/
class Triangle
{
	func clarkTriangle(_ f: Int, _ m: Int)
	{
		if (f <= 0 || m <= 0)
		{
			return;
		}
		var dp: [
			[Int]
		] = Array(repeating: Array(
                  repeating: 0, count: m + 1), count: 2);
		print("\n Given f : ", f ," m : ", m ," ");
		var row: Int = 0;
		var i: Int = 0;
		while (i <= m)
		{
			dp[row][0] = i * f;
			var j: Int = 0;
			while (j <= i)
			{
				if (j > 0)
				{
					if (j == i)
					{
						// When last element
						dp[row][j] = 1;
					}
					else if (row == 1)
					{
						//  Combination of top 2 elements
						//  We are using only two rows .
						//  And changing the element in first row
						//  So get bottom 2 elements.
						dp[row][j] = dp[0][j] + dp[0][j - 1];
					}
					else
					{
						// Combination of top 2 elements
						dp[row][j] = dp[1][j] + dp[1][j - 1];
					}
				}
				print(" ", dp[row][j], terminator: "");
				j += 1;
			}
			print(terminator: "\n");
			if (row == 1)
			{
				row = 0;
			}
			else
			{
				row = 1;
			}
			i += 1;
		}
	}
}
func main()
{
	let task: Triangle = Triangle();
	/*
	    f = 6
	    m = 10
	    ----------------------
	    [0]
	    [6, 1]
	    [12, 7, 1]
	    [18, 19, 8, 1]
	    [24, 37, 27, 9, 1]
	    [30, 61, 64, 36, 10, 1]
	    [36, 91, 125, 100, 46, 11, 1]
	    [42, 127, 216, 225, 146, 57, 12, 1]
	    [48, 169, 343, 441, 371, 203, 69, 13, 1]
	    [54, 217, 512, 784, 812, 574, 272, 82, 14, 1]
	    [60, 271, 729, 1296, 1596, 1386, 846, 354, 96, 15, 1]
	*/
	task.clarkTriangle(6, 10);
	/*
	    f = 5
	    m = 7
	    ----------------------
	    [0]
	    [5, 1]
	    [10, 6, 1]
	    [15, 16, 7, 1]
	    [20, 31, 23, 8, 1]
	    [25, 51, 54, 31, 9, 1]
	    [30, 76, 105, 85, 40, 10, 1]
	    [35, 106, 181, 190, 125, 50, 11, 1]
	*/
	task.clarkTriangle(5, 7);
}
main();

Output

 Given f :  6  m :  10
  0
  6  1
  12  7  1
  18  19  8  1
  24  37  27  9  1
  30  61  64  36  10  1
  36  91  125  100  46  11  1
  42  127  216  225  146  57  12  1
  48  169  343  441  371  203  69  13  1
  54  217  512  784  812  574  272  82  14  1
  60  271  729  1296  1596  1386  846  354  96  15  1

 Given f :  5  m :  7
  0
  5  1
  10  6  1
  15  16  7  1
  20  31  23  8  1
  25  51  54  31  9  1
  30  76  105  85  40  10  1
  35  106  181  190  125  50  11  1
/*
    Kotlin program for
    Clark's Triangle
*/
class Triangle
{
	fun clarkTriangle(f: Int, m: Int): Unit
	{
		if (f <= 0 || m <= 0)
		{
			return;
		}
		val dp: Array < Array < Int >> = Array(2)
		{
			Array(m + 1)
			{
				0
			}
		};
		print("\n Given f : " + f + " m : " + m + " \n");
		var row: Int = 0;
		var i: Int = 0;
		while (i <= m)
		{
			dp[row][0] = i * f;
			var j: Int = 0;
			while (j <= i)
			{
				if (j > 0)
				{
					if (j == i)
					{
						// When last element
						dp[row][j] = 1;
					}
					else if (row == 1)
					{
						//  Combination of top 2 elements
						//  We are using only two rows .
						//  And changing the element in first row
						//  So get bottom 2 elements.
						dp[row][j] = dp[0][j] + dp[0][j - 1];
					}
					else
					{
						// Combination of top 2 elements
						dp[row][j] = dp[1][j] + dp[1][j - 1];
					}
				}
				print(" " + dp[row][j]);
				j += 1;
			}
			print("\n");
			if (row == 1)
			{
				row = 0;
			}
			else
			{
				row = 1;
			}
			i += 1;
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Triangle = Triangle();
	/*
	    f = 6
	    m = 10
	    ----------------------
	    [0]
	    [6, 1]
	    [12, 7, 1]
	    [18, 19, 8, 1]
	    [24, 37, 27, 9, 1]
	    [30, 61, 64, 36, 10, 1]
	    [36, 91, 125, 100, 46, 11, 1]
	    [42, 127, 216, 225, 146, 57, 12, 1]
	    [48, 169, 343, 441, 371, 203, 69, 13, 1]
	    [54, 217, 512, 784, 812, 574, 272, 82, 14, 1]
	    [60, 271, 729, 1296, 1596, 1386, 846, 354, 96, 15, 1]
	*/
	task.clarkTriangle(6, 10);
	/*
	    f = 5
	    m = 7
	    ----------------------
	    [0]
	    [5, 1]
	    [10, 6, 1]
	    [15, 16, 7, 1]
	    [20, 31, 23, 8, 1]
	    [25, 51, 54, 31, 9, 1]
	    [30, 76, 105, 85, 40, 10, 1]
	    [35, 106, 181, 190, 125, 50, 11, 1]
	*/
	task.clarkTriangle(5, 7);
}

Output

 Given f : 6 m : 10
 0
 6 1
 12 7 1
 18 19 8 1
 24 37 27 9 1
 30 61 64 36 10 1
 36 91 125 100 46 11 1
 42 127 216 225 146 57 12 1
 48 169 343 441 371 203 69 13 1
 54 217 512 784 812 574 272 82 14 1
 60 271 729 1296 1596 1386 846 354 96 15 1

 Given f : 5 m : 7
 0
 5 1
 10 6 1
 15 16 7 1
 20 31 23 8 1
 25 51 54 31 9 1
 30 76 105 85 40 10 1
 35 106 181 190 125 50 11 1

Time Complexity

The time complexity of the algorithm is O(m^2). The outer loop iterates m times, and the inner loop also iterates up to m times. Therefore, the overall time complexity is quadratic in terms of the input size.

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





Categories
Relative Post