Tribonacci triangle
Here given code implementation process.
// C Program for
// Tribonacci triangle
#include <stdio.h>
void tribonacciTriangle(int n)
{
if (n <= 0)
{
return;
}
// Optimize N *N space by using 2 rows and n+1 columns
int dp[2][n + 1];
// Set initial value of first column
dp[0][0] = 1;
dp[1][0] = 1;
// We can solve this problem only use two rows
// So initial select first row which position is 0
int row = 0;
// Auxiliary variables
int temp = 0;
int back = 0;
for (int i = 1; i <= n; ++i)
{
// Set initial value in current column
dp[0][i] = 0;
dp[1][i] = 0;
for (int j = 0; j < i; ++j)
{
if (j > 0)
{
if (j + 1 == i)
{
// When last element
dp[row][j] = 1;
}
else if (row == 1)
{
temp = dp[row][j];
// Change second row 'j' column value
// Combination of three elements
dp[row][j] = dp[0][j] + dp[0][j - 1] + back;
back = temp;
}
else
{
temp = dp[row][j];
// Change first row 'j' column value
// Combination of three elements
dp[row][j] = dp[1][j] + dp[1][j - 1] + back;
back = temp;
}
}
printf(" %d", dp[row][j]);
}
back = 1;
printf("\n");
if (i > 1)
{
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
}
}
}
int main()
{
/*
1
1 1
1 3 1
1 5 5 1
1 7 13 7 1
1 9 25 25 9 1
1 11 41 63 41 11 1
1 13 61 129 129 61 13 1
1 15 85 231 321 231 85 15 1
1 17 113 377 681 681 377 113 17 1
------------------------------------------------------
*/
tribonacciTriangle(10);
return 0;
}
Output
1
1 1
1 3 1
1 5 5 1
1 7 13 7 1
1 9 25 25 9 1
1 11 41 63 41 11 1
1 13 61 129 129 61 13 1
1 15 85 231 321 231 85 15 1
1 17 113 377 681 681 377 113 17 1
// Java program for
// Tribonacci triangle
public class Triangle
{
public void tribonacciTriangle(int n)
{
if (n <= 0)
{
return;
}
// Optimize N *N space by using 2 rows and n+1 columns
int[][] dp = new int[2][n + 1];
// Set initial value of first column
dp[0][0] = 1;
dp[1][0] = 1;
// We can solve this problem only use two rows
// So initial select first row which position is 0
int row = 0;
// Auxiliary variables
int temp = 0;
int back = 0;
for (int i = 1; i <= n; ++i)
{
// Set initial value in current column
dp[0][i] = 0;
dp[1][i] = 0;
for (int j = 0; j < i; ++j)
{
if (j > 0)
{
if (j + 1 == i)
{
// When last element
dp[row][j] = 1;
}
else if (row == 1)
{
temp = dp[row][j];
// Change second row 'j' column value
// Combination of three elements
dp[row][j] = dp[0][j] + dp[0][j - 1] + back;
back = temp;
}
else
{
temp = dp[row][j];
// Change first row 'j' column value
// Combination of three elements
dp[row][j] = dp[1][j] + dp[1][j - 1] + back;
back = temp;
}
}
System.out.print(" " + dp[row][j]);
}
back = 1;
System.out.print("\n");
if (i > 1)
{
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
}
}
}
public static void main(String[] args)
{
Triangle task = new Triangle();
/*
1
1 1
1 3 1
1 5 5 1
1 7 13 7 1
1 9 25 25 9 1
1 11 41 63 41 11 1
1 13 61 129 129 61 13 1
1 15 85 231 321 231 85 15 1
1 17 113 377 681 681 377 113 17 1
----------------------------------------------------------
*/
task.tribonacciTriangle(10);
}
}
Output
1
1 1
1 3 1
1 5 5 1
1 7 13 7 1
1 9 25 25 9 1
1 11 41 63 41 11 1
1 13 61 129 129 61 13 1
1 15 85 231 321 231 85 15 1
1 17 113 377 681 681 377 113 17 1
// Include header file
#include <iostream>
using namespace std;
// C++ program for
// Tribonacci triangle
class Triangle
{
public: void tribonacciTriangle(int n)
{
if (n <= 0)
{
return;
}
// Optimize N *N space by using 2 rows and n+1 columns
int dp[2][n + 1];
// Set initial value of first column
dp[0][0] = 1;
dp[1][0] = 1;
// We can solve this problem only use two rows
// So initial select first row which position is 0
int row = 0;
// Auxiliary variables
int temp = 0;
int back = 0;
for (int i = 1; i <= n; ++i)
{
// Set initial value in current column
dp[0][i] = 0;
dp[1][i] = 0;
for (int j = 0; j < i; ++j)
{
if (j > 0)
{
if (j + 1 == i)
{
// When last element
dp[row][j] = 1;
}
else if (row == 1)
{
temp = dp[row][j];
// Change second row 'j' column value
// Combination of three elements
dp[row][j] = dp[0][j] + dp[0][j - 1] + back;
back = temp;
}
else
{
temp = dp[row][j];
// Change first row 'j' column value
// Combination of three elements
dp[row][j] = dp[1][j] + dp[1][j - 1] + back;
back = temp;
}
}
cout << " " << dp[row][j];
}
back = 1;
cout << "\n";
if (i > 1)
{
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
}
}
}
};
int main()
{
Triangle *task = new Triangle();
/*
1
1 1
1 3 1
1 5 5 1
1 7 13 7 1
1 9 25 25 9 1
1 11 41 63 41 11 1
1 13 61 129 129 61 13 1
1 15 85 231 321 231 85 15 1
1 17 113 377 681 681 377 113 17 1
----------------------------------------------------------
*/
task->tribonacciTriangle(10);
return 0;
}
Output
1
1 1
1 3 1
1 5 5 1
1 7 13 7 1
1 9 25 25 9 1
1 11 41 63 41 11 1
1 13 61 129 129 61 13 1
1 15 85 231 321 231 85 15 1
1 17 113 377 681 681 377 113 17 1
// Include namespace system
using System;
// Csharp program for
// Tribonacci triangle
public class Triangle
{
public void tribonacciTriangle(int n)
{
if (n <= 0)
{
return;
}
// Optimize N *N space by using 2 rows and n+1 columns
int[,] dp = new int[2,n + 1];
// Set initial value of first column
dp[0,0] = 1;
dp[1,0] = 1;
// We can solve this problem only use two rows
// So initial select first row which position is 0
int row = 0;
// Auxiliary variables
int temp = 0;
int back = 0;
for (int i = 1; i <= n; ++i)
{
// Set initial value in current column
dp[0,i] = 0;
dp[1,i] = 0;
for (int j = 0; j < i; ++j)
{
if (j > 0)
{
if (j + 1 == i)
{
// When last element
dp[row,j] = 1;
}
else if (row == 1)
{
temp = dp[row,j];
// Change second row 'j' column value
// Combination of three elements
dp[row,j] = dp[0,j] + dp[0,j - 1] + back;
back = temp;
}
else
{
temp = dp[row,j];
// Change first row 'j' column value
// Combination of three elements
dp[row,j] = dp[1,j] + dp[1,j - 1] + back;
back = temp;
}
}
Console.Write(" " + dp[row,j]);
}
back = 1;
Console.Write("\n");
if (i > 1)
{
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
}
}
}
public static void Main(String[] args)
{
Triangle task = new Triangle();
/*
1
1 1
1 3 1
1 5 5 1
1 7 13 7 1
1 9 25 25 9 1
1 11 41 63 41 11 1
1 13 61 129 129 61 13 1
1 15 85 231 321 231 85 15 1
1 17 113 377 681 681 377 113 17 1
----------------------------------------------------------
*/
task.tribonacciTriangle(10);
}
}
Output
1
1 1
1 3 1
1 5 5 1
1 7 13 7 1
1 9 25 25 9 1
1 11 41 63 41 11 1
1 13 61 129 129 61 13 1
1 15 85 231 321 231 85 15 1
1 17 113 377 681 681 377 113 17 1
package main
import "fmt"
// Go program for
// Tribonacci triangle
func tribonacciTriangle(n int) {
if n <= 0 {
return
}
// Optimize N *N space by using 2 rows and n+1 columns
var dp = make([][] int, 2)
for i := 0; i < 2; i++ {
dp[i] = make([]int,n+1)
}
// Set initial value of first column
dp[0][0] = 1
dp[1][0] = 1
// We can solve this problem only use two rows
// So initial select first row which position is 0
var row int = 0
// Auxiliary variables
var temp int = 0
var back int = 0
for i := 1 ; i <= n ; i++ {
// Set initial value in current column
dp[0][i] = 0
dp[1][i] = 0
for j := 0 ; j < i ; j++ {
if j > 0 {
if j + 1 == i {
// When last element
dp[row][j] = 1
} else if row == 1 {
temp = dp[row][j]
// Change second row 'j' column value
// Combination of three elements
dp[row][j] = dp[0][j] + dp[0][j - 1] + back
back = temp
} else {
temp = dp[row][j]
// Change first row 'j' column value
// Combination of three elements
dp[row][j] = dp[1][j] + dp[1][j - 1] + back
back = temp
}
}
fmt.Print(" ", dp[row][j])
}
back = 1
fmt.Print("\n")
if i > 1 {
if row == 1 {
row = 0
} else {
row = 1
}
}
}
}
func main() {
/*
1
1 1
1 3 1
1 5 5 1
1 7 13 7 1
1 9 25 25 9 1
1 11 41 63 41 11 1
1 13 61 129 129 61 13 1
1 15 85 231 321 231 85 15 1
1 17 113 377 681 681 377 113 17 1
----------------------------------------------------------
*/
tribonacciTriangle(10)
}
Output
1
1 1
1 3 1
1 5 5 1
1 7 13 7 1
1 9 25 25 9 1
1 11 41 63 41 11 1
1 13 61 129 129 61 13 1
1 15 85 231 321 231 85 15 1
1 17 113 377 681 681 377 113 17 1
<?php
// Php program for
// Tribonacci triangle
class Triangle
{
public function tribonacciTriangle($n)
{
if ($n <= 0)
{
return;
}
// Optimize N *N space by using 2 rows and n+1 columns
$dp = array_fill(0, 2, array_fill(0, $n + 1, 0));
// Set initial value of first column
$dp[0][0] = 1;
$dp[1][0] = 1;
// We can solve this problem only use two rows
// So initial select first row which position is 0
$row = 0;
// Auxiliary variables
$temp = 0;
$back = 0;
for ($i = 1; $i <= $n; ++$i)
{
for ($j = 0; $j < $i; ++$j)
{
if ($j > 0)
{
if ($j + 1 == $i)
{
// When last element
$dp[$row][$j] = 1;
}
else if ($row == 1)
{
$temp = $dp[$row][$j];
// Change second row 'j' column value
// Combination of three elements
$dp[$row][$j] = $dp[0][$j] + $dp[0][$j - 1] + $back;
$back = $temp;
}
else
{
$temp = $dp[$row][$j];
// Change first row 'j' column value
// Combination of three elements
$dp[$row][$j] = $dp[1][$j] + $dp[1][$j - 1] + $back;
$back = $temp;
}
}
echo(" ".$dp[$row][$j]);
}
$back = 1;
echo("\n");
if ($i > 1)
{
if ($row == 1)
{
$row = 0;
}
else
{
$row = 1;
}
}
}
}
}
function main()
{
$task = new Triangle();
/*
1
1 1
1 3 1
1 5 5 1
1 7 13 7 1
1 9 25 25 9 1
1 11 41 63 41 11 1
1 13 61 129 129 61 13 1
1 15 85 231 321 231 85 15 1
1 17 113 377 681 681 377 113 17 1
----------------------------------------------------------
*/
$task->tribonacciTriangle(10);
}
main();
Output
1
1 1
1 3 1
1 5 5 1
1 7 13 7 1
1 9 25 25 9 1
1 11 41 63 41 11 1
1 13 61 129 129 61 13 1
1 15 85 231 321 231 85 15 1
1 17 113 377 681 681 377 113 17 1
// Node JS program for
// Tribonacci triangle
class Triangle
{
tribonacciTriangle(n)
{
if (n <= 0)
{
return;
}
// Optimize N *N space by using 2 rows and n+1 columns
var dp = Array(2).fill(0).map(() => new Array(n + 1).fill(0));
// Set initial value of first column
dp[0][0] = 1;
dp[1][0] = 1;
// We can solve this problem only use two rows
// So initial select first row which position is 0
var row = 0;
// Auxiliary variables
var temp = 0;
var back = 0;
for (var i = 1; i <= n; ++i)
{
for (var j = 0; j < i; ++j)
{
if (j > 0)
{
if (j + 1 == i)
{
// When last element
dp[row][j] = 1;
}
else if (row == 1)
{
temp = dp[row][j];
// Change second row 'j' column value
// Combination of three elements
dp[row][j] = dp[0][j] + dp[0][j - 1] + back;
back = temp;
}
else
{
temp = dp[row][j];
// Change first row 'j' column value
// Combination of three elements
dp[row][j] = dp[1][j] + dp[1][j - 1] + back;
back = temp;
}
}
process.stdout.write(" " + dp[row][j]);
}
back = 1;
process.stdout.write("\n");
if (i > 1)
{
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
}
}
}
}
function main()
{
var task = new Triangle();
/*
1
1 1
1 3 1
1 5 5 1
1 7 13 7 1
1 9 25 25 9 1
1 11 41 63 41 11 1
1 13 61 129 129 61 13 1
1 15 85 231 321 231 85 15 1
1 17 113 377 681 681 377 113 17 1
----------------------------------------------------------
*/
task.tribonacciTriangle(10);
}
main();
Output
1
1 1
1 3 1
1 5 5 1
1 7 13 7 1
1 9 25 25 9 1
1 11 41 63 41 11 1
1 13 61 129 129 61 13 1
1 15 85 231 321 231 85 15 1
1 17 113 377 681 681 377 113 17 1
# Python 3 program for
# Tribonacci triangle
class Triangle :
def tribonacciTriangle(self, n) :
if (n <= 0) :
return
# Optimize N *N space by using 2 rows and n+1 columns
dp = [[0] * (n + 1) for _ in range(2) ]
# Set initial value of first column
dp[0][0] = 1
dp[1][0] = 1
# We can solve this problem only use two rows
# So initial select first row which position is 0
row = 0
# Auxiliary variables
temp = 0
back = 0
i = 1
while (i <= n) :
j = 0
while (j < i) :
if (j > 0) :
if (j + 1 == i) :
# When last element
dp[row][j] = 1
elif (row == 1) :
temp = dp[row][j]
# Change second row 'j' column value
# Combination of three elements
dp[row][j] = dp[0][j] + dp[0][j - 1] + back
back = temp
else :
temp = dp[row][j]
# Change first row 'j' column value
# Combination of three elements
dp[row][j] = dp[1][j] + dp[1][j - 1] + back
back = temp
print(" ", dp[row][j], end = "")
j += 1
back = 1
print(end = "\n")
if (i > 1) :
if (row == 1) :
row = 0
else :
row = 1
i += 1
def main() :
task = Triangle()
# 1
# 1 1
# 1 3 1
# 1 5 5 1
# 1 7 13 7 1
# 1 9 25 25 9 1
# 1 11 41 63 41 11 1
# 1 13 61 129 129 61 13 1
# 1 15 85 231 321 231 85 15 1
# 1 17 113 377 681 681 377 113 17 1
# ----------------------------------------------------------
task.tribonacciTriangle(10)
if __name__ == "__main__": main()
Output
1
1 1
1 3 1
1 5 5 1
1 7 13 7 1
1 9 25 25 9 1
1 11 41 63 41 11 1
1 13 61 129 129 61 13 1
1 15 85 231 321 231 85 15 1
1 17 113 377 681 681 377 113 17 1
# Ruby program for
# Tribonacci triangle
class Triangle
def tribonacciTriangle(n)
if (n <= 0)
return
end
# Optimize N *N space by using 2 rows and n+1 columns
dp = Array.new(2) {Array.new(n + 1) {0}}
# Set initial value of first column
dp[0][0] = 1
dp[1][0] = 1
# We can solve this problem only use two rows
# So initial select first row which position is 0
row = 0
# Auxiliary variables
temp = 0
back = 0
i = 1
while (i <= n)
j = 0
while (j < i)
if (j > 0)
if (j + 1 == i)
# When last element
dp[row][j] = 1
elsif (row == 1)
temp = dp[row][j]
# Change second row 'j' column value
# Combination of three elements
dp[row][j] = dp[0][j] + dp[0][j - 1] + back
back = temp
else
temp = dp[row][j]
# Change first row 'j' column value
# Combination of three elements
dp[row][j] = dp[1][j] + dp[1][j - 1] + back
back = temp
end
end
print(" ", dp[row][j])
j += 1
end
back = 1
print("\n")
if (i > 1)
if (row == 1)
row = 0
else
row = 1
end
end
i += 1
end
end
end
def main()
task = Triangle.new()
# 1
# 1 1
# 1 3 1
# 1 5 5 1
# 1 7 13 7 1
# 1 9 25 25 9 1
# 1 11 41 63 41 11 1
# 1 13 61 129 129 61 13 1
# 1 15 85 231 321 231 85 15 1
# 1 17 113 377 681 681 377 113 17 1
# ----------------------------------------------------------
task.tribonacciTriangle(10)
end
main()
Output
1
1 1
1 3 1
1 5 5 1
1 7 13 7 1
1 9 25 25 9 1
1 11 41 63 41 11 1
1 13 61 129 129 61 13 1
1 15 85 231 321 231 85 15 1
1 17 113 377 681 681 377 113 17 1
// Scala program for
// Tribonacci triangle
class Triangle()
{
def tribonacciTriangle(n: Int): Unit = {
if (n <= 0)
{
return;
}
// Optimize N *N space by using 2 rows and n+1 columns
var dp: Array[Array[Int]] = Array.fill[Int](2, n + 1)(0);
// Set initial value of first column
dp(0)(0) = 1;
dp(1)(0) = 1;
// We can solve this problem only use two rows
// So initial select first row which position is 0
var row: Int = 0;
// Auxiliary variables
var temp: Int = 0;
var back: Int = 0;
var i: Int = 1;
while (i <= n)
{
var j: Int = 0;
while (j < i)
{
if (j > 0)
{
if (j + 1 == i)
{
// When last element
dp(row)(j) = 1;
}
else if (row == 1)
{
temp = dp(row)(j);
// Change second row 'j' column value
// Combination of three elements
dp(row)(j) = dp(0)(j) + dp(0)(j - 1) + back;
back = temp;
}
else
{
temp = dp(row)(j);
// Change first row 'j' column value
// Combination of three elements
dp(row)(j) = dp(1)(j) + dp(1)(j - 1) + back;
back = temp;
}
}
print(" " + dp(row)(j));
j += 1;
}
back = 1;
print("\n");
if (i > 1)
{
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
}
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Triangle = new Triangle();
/*
1
1 1
1 3 1
1 5 5 1
1 7 13 7 1
1 9 25 25 9 1
1 11 41 63 41 11 1
1 13 61 129 129 61 13 1
1 15 85 231 321 231 85 15 1
1 17 113 377 681 681 377 113 17 1
----------------------------------------------------------
*/
task.tribonacciTriangle(10);
}
}
Output
1
1 1
1 3 1
1 5 5 1
1 7 13 7 1
1 9 25 25 9 1
1 11 41 63 41 11 1
1 13 61 129 129 61 13 1
1 15 85 231 321 231 85 15 1
1 17 113 377 681 681 377 113 17 1
// Swift 4 program for
// Tribonacci triangle
class Triangle
{
func tribonacciTriangle(_ n: Int)
{
if (n <= 0)
{
return;
}
// Optimize N *N space by using 2 rows and n+1 columns
var dp: [
[Int]
] = Array(repeating: Array(
repeating: 0, count: n + 1), count: 2
);
// Set initial value of first column
dp[0][0] = 1;
dp[1][0] = 1;
// We can solve this problem only use two rows
// So initial select first row which position is 0
var row: Int = 0;
// Auxiliary variables
var temp: Int = 0;
var back: Int = 0;
var i: Int = 1;
while (i <= n)
{
var j: Int = 0;
while (j < i)
{
if (j > 0)
{
if (j + 1 == i)
{
// When last element
dp[row][j] = 1;
}
else if (row == 1)
{
temp = dp[row][j];
// Change second row 'j' column value
// Combination of three elements
dp[row][j] = dp[0][j] + dp[0][j - 1] + back;
back = temp;
}
else
{
temp = dp[row][j];
// Change first row 'j' column value
// Combination of three elements
dp[row][j] = dp[1][j] + dp[1][j - 1] + back;
back = temp;
}
}
print(" ", dp[row][j], terminator: "");
j += 1;
}
back = 1;
print(terminator: "\n");
if (i > 1)
{
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
}
i += 1;
}
}
}
func main()
{
let task: Triangle = Triangle();
/*
1
1 1
1 3 1
1 5 5 1
1 7 13 7 1
1 9 25 25 9 1
1 11 41 63 41 11 1
1 13 61 129 129 61 13 1
1 15 85 231 321 231 85 15 1
1 17 113 377 681 681 377 113 17 1
----------------------------------------------------------
*/
task.tribonacciTriangle(10);
}
main();
Output
1
1 1
1 3 1
1 5 5 1
1 7 13 7 1
1 9 25 25 9 1
1 11 41 63 41 11 1
1 13 61 129 129 61 13 1
1 15 85 231 321 231 85 15 1
1 17 113 377 681 681 377 113 17 1
// Kotlin program for
// Tribonacci triangle
class Triangle
{
fun tribonacciTriangle(n: Int): Unit
{
if (n <= 0)
{
return;
}
// Optimize N *N space by using 2 rows and n+1 columns
val dp: Array < Array < Int >> = Array(2)
{
Array(n + 1)
{
0
}
};
// Set initial value of first column
dp[0][0] = 1;
dp[1][0] = 1;
// We can solve this problem only use two rows
// So initial select first row which position is 0
var row: Int = 0;
// Auxiliary variables
var temp: Int;
var back: Int = 0;
var i: Int = 1;
while (i <= n)
{
var j: Int = 0;
while (j < i)
{
if (j > 0)
{
if (j + 1 == i)
{
// When last element
dp[row][j] = 1;
}
else if (row == 1)
{
temp = dp[row][j];
// Change second row 'j' column value
// Combination of three elements
dp[row][j] = dp[0][j] + dp[0][j - 1] + back;
back = temp;
}
else
{
temp = dp[row][j];
// Change first row 'j' column value
// Combination of three elements
dp[row][j] = dp[1][j] + dp[1][j - 1] + back;
back = temp;
}
}
print(" " + dp[row][j]);
j += 1;
}
back = 1;
print("\n");
if (i > 1)
{
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
}
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
val task: Triangle = Triangle();
/*
1
1 1
1 3 1
1 5 5 1
1 7 13 7 1
1 9 25 25 9 1
1 11 41 63 41 11 1
1 13 61 129 129 61 13 1
1 15 85 231 321 231 85 15 1
1 17 113 377 681 681 377 113 17 1
----------------------------------------------------------
*/
task.tribonacciTriangle(10);
}
Output
1
1 1
1 3 1
1 5 5 1
1 7 13 7 1
1 9 25 25 9 1
1 11 41 63 41 11 1
1 13 61 129 129 61 13 1
1 15 85 231 321 231 85 15 1
1 17 113 377 681 681 377 113 17 1
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