Posted on by Kalkicode
Code Dynamic Programming

# Bernoulli's triangle

Bernoulli's Triangle is a variation of Pascal's Triangle, named after the Swiss mathematician Jacob Bernoulli. Like Pascal's Triangle, it is a triangular array of numbers with some interesting properties. The triangle is constructed in such a way that each number is the sum of the two numbers directly above it. The first row contains only the number 1, and subsequent rows are constructed by following this addition rule.

## Problem Statement

The problem is to print the first `n` rows of Bernoulli's Triangle. The input to the program is an integer `n`, which represents the number of rows to be printed. The program should then calculate the values for each row of Bernoulli's Triangle and print them in the form of a triangular array.

## Explanation with Example

Let's take `n = 6` as an example to understand how Bernoulli's Triangle is constructed. The first six rows of Bernoulli's Triangle are as follows:

``````Row 1:  1
Row 2:  1  2
Row 3:  1  3  4
Row 4:  1  4  7  8
Row 5:  1  5  11  15  16
Row 6:  1  6  16  26  31  32
``````

Each number in the triangle is calculated by summing the two numbers above it. For example, in Row 3, the number 3 is the sum of the numbers 1 and 2 from Row 2. The number 4 is the sum of the numbers 1 and 3 from Row 3.

## Pseudocode and Algorithm

``````function bernoulliTriangle(n)
if n <= 0
return // Invalid input, exit the function

// Initialize a 2D array to store Bernoulli's Triangle values
dp[2][n + 1]

// Set starting column value for both rows
dp[0][0] = 1
dp[1][0] = 1

// Initialize variable to keep track of current row
row = 1

// Print the value of n
print("Given n : ", n)

// Loop to generate each row
for i = 1 to n
// Initialize the columns in the current row with 0
dp[0][i] = 0
dp[1][i] = 0

// Loop to calculate and print values in the current row
for j = 0 to i - 1
// Calculate the value based on the rules of Bernoulli's Triangle
if j > 0
if j + 1 == i
dp[row][j] = dp[row][j - 1] + 1 // Last element of the row
else if row == 1
dp[row][j] = dp[0][j] + dp[0][j - 1] // Change to the second row
else
dp[row][j] = dp[1][j] + dp[1][j - 1] // Change to the first row

// Print the value in the current row
print("  ", dp[row][j])

// Move to the next row
if row == 1
row = 0
else
row = 1

// Move to the next line for the next row
print("\n")

// Example usage
bernoulliTriangle(6) // Print the first 6 rows of Bernoulli's Triangle
``````

Prints the first `n` rows of Bernoulli's Triangle. Let's go through the algorithm step-by-step:

1. Start with an integer `n` as input, which represents the number of rows to be printed.
2. Create a 2D array `dp` of size `2 x (n+1)` to store the values of Bernoulli's Triangle. Initialize it with zeros.
3. Set the starting column value of the first row (dp[0][0]) and the starting column value of the second row (dp[1][0]) to 1.
4. Initialize a variable `row` to keep track of the current row we are working with. Start with the second row (row = 1).
5. Use two nested loops to fill the values of each row. The outer loop (`i`) runs from 1 to `n`, representing the row number. The inner loop (`j`) runs from 0 to `i-1`, representing the columns in that row.
6. Within the inner loop, calculate each value based on the rules of Bernoulli's Triangle. The value is the sum of the two numbers directly above it in the triangle.
7. Print each value as it is calculated.
8. After printing all the values in a row, move to the next row by changing the value of `row`. If `row` is 1, set it to 0, and vice versa.

## Code Solution

Here given code implementation process.

``````// C Program for
// Bernoulli's triangle
#include <stdio.h>

void bernoulliTriangle(int n)
{
if (n <= 0)
{
return;
}
// This problem are need N X N space
// But we are solve this problem using using only two rows
// Here 2 indicates row
// And n+1 indicate column value
int dp[2][n + 1];
// Set starting column value
dp[0][0] = 1;
dp[1][0] = 1;
// We can solve this problem only use two rows
// So initial select second row which position is 1
int row = 1;
printf("\n Given n : %d \n", n);
for (int i = 1; i <= n; ++i)
{
// Set intial value of column
dp[0][i] = 0;
dp[1][i] = 0;
// This loop are used to print result in current row
for (int j = 0; j < i; ++j)
{
if (j > 0)
{
if (j + 1 == i)
{
// Last element of current row
dp[row][j] = dp[row][j - 1] + 1;
}
else if (row == 1)
{
// Change second row
dp[row][j] = dp[0][j] + dp[0][j - 1];
}
else
{
// Change first row
dp[row][j] = dp[1][j] + dp[1][j - 1];
}
}
// Display the value
printf("  %d", dp[row][j]);
}
printf("\n");
// Change row
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
}
}
int main()
{
/*
n = 6
---------
1
1  2
1  3  4
1  4  7  8
1  5  11  15  16
1  6  16  26  31  32
*/
bernoulliTriangle(6);
/*
n = 10
----------
1
1  2
1  3  4
1  4  7  8
1  5  11  15  16
1  6  16  26  31  32
1  7  22  42  57  63  64
1  8  29  64  99  120  127  128
1  9  37  93  163  219  247  255  256
1  10  46  130  256  382  466  502  511  512
*/
bernoulliTriangle(10);
return 0;
}``````

#### Output

`````` Given n : 6
1
1  2
1  3  4
1  4  7  8
1  5  11  15  16
1  6  16  26  31  32

Given n : 10
1
1  2
1  3  4
1  4  7  8
1  5  11  15  16
1  6  16  26  31  32
1  7  22  42  57  63  64
1  8  29  64  99  120  127  128
1  9  37  93  163  219  247  255  256
1  10  46  130  256  382  466  502  511  512``````
``````// Java program for
// Bernoulli's triangle
public class Triangle
{
public void bernoulliTriangle(int n)
{
if (n <= 0)
{
return;
}
// This problem are need N X N space
// But we are solve this problem using using only two rows
// Here 2 indicates row
// And n+1 indicate column value
int[][] dp = new int[2][n + 1];
// Set starting column value
dp[0][0] = 1;
dp[1][0] = 1;
// We can solve this problem only use two rows
// So initial select second row which position is 1
int row = 1;
System.out.print("\n Given n : " + n + " \n");
for (int i = 1; i <= n; ++i)
{
// Set intial value of column
dp[0][i] = 0;
dp[1][i] = 0;
// This loop are used to print result in current row
for (int j = 0; j < i; ++j)
{
if (j > 0)
{
if (j + 1 == i)
{
// Last element of current row
dp[row][j] = dp[row][j - 1] + 1;
}
else if (row == 1)
{
// Change second row
dp[row][j] = dp[0][j] + dp[0][j - 1];
}
else
{
// Change first row
dp[row][j] = dp[1][j] + dp[1][j - 1];
}
}
// Display the value
System.out.print(" " + dp[row][j]);
}
System.out.print("\n");
// Change row
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
}
}
public static void main(String[] args)
{
/*
n = 6
---------
1
1  2
1  3  4
1  4  7  8
1  5  11  15  16
1  6  16  26  31  32
*/
/*
n = 10
----------
1
1  2
1  3  4
1  4  7  8
1  5  11  15  16
1  6  16  26  31  32
1  7  22  42  57  63  64
1  8  29  64  99  120  127  128
1  9  37  93  163  219  247  255  256
1  10  46  130  256  382  466  502  511  512
*/
}
}``````

#### Output

`````` Given n : 6
1
1 2
1 3 4
1 4 7 8
1 5 11 15 16
1 6 16 26 31 32

Given n : 10
1
1 2
1 3 4
1 4 7 8
1 5 11 15 16
1 6 16 26 31 32
1 7 22 42 57 63 64
1 8 29 64 99 120 127 128
1 9 37 93 163 219 247 255 256
1 10 46 130 256 382 466 502 511 512``````
``````// Include header file
#include <iostream>
using namespace std;
// C++ program for
// Bernoulli's triangle
class Triangle
{
public: void bernoulliTriangle(int n)
{
if (n <= 0)
{
return;
}
// This problem are need N X N space
// But we are solve this problem using using only two rows
// Here 2 indicates row
// And n+1 indicate column value
int dp[2][n + 1];
// Set starting column value
dp[0][0] = 1;
dp[1][0] = 1;
// We can solve this problem only use two rows
// So initial select second row which position is 1
int row = 1;
cout << "\n Given n : " << n << " \n";
for (int i = 1; i <= n; ++i)
{
// Set intial value of column
dp[0][i] = 0;
dp[1][i] = 0;
// This loop are used to print result in current row
for (int j = 0; j < i; ++j)
{
if (j > 0)
{
if (j + 1 == i)
{
// Last element of current row
dp[row][j] = dp[row][j - 1] + 1;
}
else if (row == 1)
{
// Change second row
dp[row][j] = dp[0][j] + dp[0][j - 1];
}
else
{
// Change first row
dp[row][j] = dp[1][j] + dp[1][j - 1];
}
}
// Display the value
cout << " " << dp[row][j];
}
cout << "\n";
// Change row
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
}
}
};
int main()
{
/*
n = 6
---------
1
1  2
1  3  4
1  4  7  8
1  5  11  15  16
1  6  16  26  31  32
*/
/*
n = 10
----------
1
1  2
1  3  4
1  4  7  8
1  5  11  15  16
1  6  16  26  31  32
1  7  22  42  57  63  64
1  8  29  64  99  120  127  128
1  9  37  93  163  219  247  255  256
1  10  46  130  256  382  466  502  511  512
*/
return 0;
}``````

#### Output

`````` Given n : 6
1
1 2
1 3 4
1 4 7 8
1 5 11 15 16
1 6 16 26 31 32

Given n : 10
1
1 2
1 3 4
1 4 7 8
1 5 11 15 16
1 6 16 26 31 32
1 7 22 42 57 63 64
1 8 29 64 99 120 127 128
1 9 37 93 163 219 247 255 256
1 10 46 130 256 382 466 502 511 512``````
``````// Include namespace system
using System;
// Csharp program for
// Bernoulli's triangle
public class Triangle
{
public void bernoulliTriangle(int n)
{
if (n <= 0)
{
return;
}
// This problem are need N X N space
// But we are solve this problem using using only two rows
// Here 2 indicates row
// And n+1 indicate column value
int[,] dp = new int[2,n + 1];
// Set starting column value
dp[0,0] = 1;
dp[1,0] = 1;
// We can solve this problem only use two rows
// So initial select second row which position is 1
int row = 1;
Console.Write("\n Given n : " + n + " \n");
for (int i = 1; i <= n; ++i)
{
// Set intial value of column
dp[0,i] = 0;
dp[1,i] = 0;
// This loop are used to print result in current row
for (int j = 0; j < i; ++j)
{
if (j > 0)
{
if (j + 1 == i)
{
// Last element of current row
dp[row,j] = dp[row,j - 1] + 1;
}
else if (row == 1)
{
// Change second row
dp[row,j] = dp[0,j] + dp[0,j - 1];
}
else
{
// Change first row
dp[row,j] = dp[1,j] + dp[1,j - 1];
}
}
// Display the value
Console.Write(" " + dp[row,j]);
}
Console.Write("\n");
// Change row
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
}
}
public static void Main(String[] args)
{
/*
n = 6
---------
1
1  2
1  3  4
1  4  7  8
1  5  11  15  16
1  6  16  26  31  32
*/
/*
n = 10
----------
1
1  2
1  3  4
1  4  7  8
1  5  11  15  16
1  6  16  26  31  32
1  7  22  42  57  63  64
1  8  29  64  99  120  127  128
1  9  37  93  163  219  247  255  256
1  10  46  130  256  382  466  502  511  512
*/
}
}``````

#### Output

`````` Given n : 6
1
1 2
1 3 4
1 4 7 8
1 5 11 15 16
1 6 16 26 31 32

Given n : 10
1
1 2
1 3 4
1 4 7 8
1 5 11 15 16
1 6 16 26 31 32
1 7 22 42 57 63 64
1 8 29 64 99 120 127 128
1 9 37 93 163 219 247 255 256
1 10 46 130 256 382 466 502 511 512``````
``````package main
import "fmt"
// Go program for
// Bernoulli's triangle

func bernoulliTriangle(n int) {
if n <= 0 {
return
}
// This problem are need N X N space
// But we are solve this problem using using only two rows
// Here 2 indicates row
// And n+1 indicate column value
var dp = make([][] int, 2)
for i := 0; i < 2; i++ {
dp[i] = make([] int, n + 1)
}
// Set starting column value
dp[0][0] = 1
dp[1][0] = 1
// We can solve this problem only use two rows
// So initial select second row which position is 1
var row int = 1
fmt.Print("\n Given n : ", n, " \n")
for i := 1 ; i <= n ; i++ {
// Set intial value of column
dp[0][i] = 0
dp[1][i] = 0
// This loop are used to print result in current row
for j := 0 ; j < i ; j++ {
if j > 0 {
if j + 1 == i {
// Last element of current row
dp[row][j] = dp[row][j - 1] + 1
} else if row == 1 {
// Change second row
dp[row][j] = dp[0][j] + dp[0][j - 1]
} else {
// Change first row
dp[row][j] = dp[1][j] + dp[1][j - 1]
}
}
// Display the value
fmt.Print(" ", dp[row][j])
}
fmt.Print("\n")
// Change row
if row == 1 {
row = 0
} else {
row = 1
}
}
}
func main() {

/*
n = 6
---------
1
1  2
1  3  4
1  4  7  8
1  5  11  15  16
1  6  16  26  31  32
*/
bernoulliTriangle(6)
/*
n = 10
----------
1
1  2
1  3  4
1  4  7  8
1  5  11  15  16
1  6  16  26  31  32
1  7  22  42  57  63  64
1  8  29  64  99  120  127  128
1  9  37  93  163  219  247  255  256
1  10  46  130  256  382  466  502  511  512
*/
bernoulliTriangle(10)
}``````

#### Output

`````` Given n : 6
1
1 2
1 3 4
1 4 7 8
1 5 11 15 16
1 6 16 26 31 32

Given n : 10
1
1 2
1 3 4
1 4 7 8
1 5 11 15 16
1 6 16 26 31 32
1 7 22 42 57 63 64
1 8 29 64 99 120 127 128
1 9 37 93 163 219 247 255 256
1 10 46 130 256 382 466 502 511 512``````
``````<?php
// Php program for
// Bernoulli's triangle
class Triangle
{
public  function bernoulliTriangle(\$n)
{
if (\$n <= 0)
{
return;
}
// This problem are need N X N space
// But we are solve this problem using using only two rows
// Here 2 indicates row
// And n+1 indicate column value
\$dp = array_fill(0, 2, array_fill(0, \$n + 1, 0));
// Set starting column value
\$dp[0][0] = 1;
\$dp[1][0] = 1;
// We can solve this problem only use two rows
// So initial select second row which position is 1
\$row = 1;
echo("\n Given n : ".\$n." \n");
for (\$i = 1; \$i <= \$n; ++\$i)
{
// Set intial value of column
\$dp[0][\$i] = 0;
\$dp[1][\$i] = 0;
// This loop are used to print result in current row
for (\$j = 0; \$j < \$i; ++\$j)
{
if (\$j > 0)
{
if (\$j + 1 == \$i)
{
// Last element of current row
\$dp[\$row][\$j] = \$dp[\$row][\$j - 1] + 1;
}
else if (\$row == 1)
{
// Change second row
\$dp[\$row][\$j] = \$dp[0][\$j] + \$dp[0][\$j - 1];
}
else
{
// Change first row
\$dp[\$row][\$j] = \$dp[1][\$j] + \$dp[1][\$j - 1];
}
}
// Display the value
echo(" ".\$dp[\$row][\$j]);
}
echo("\n");
// Change row
if (\$row == 1)
{
\$row = 0;
}
else
{
\$row = 1;
}
}
}
}

function main()
{
/*
n = 6
---------
1
1  2
1  3  4
1  4  7  8
1  5  11  15  16
1  6  16  26  31  32
*/
/*
n = 10
----------
1
1  2
1  3  4
1  4  7  8
1  5  11  15  16
1  6  16  26  31  32
1  7  22  42  57  63  64
1  8  29  64  99  120  127  128
1  9  37  93  163  219  247  255  256
1  10  46  130  256  382  466  502  511  512
*/
}
main();``````

#### Output

`````` Given n : 6
1
1 2
1 3 4
1 4 7 8
1 5 11 15 16
1 6 16 26 31 32

Given n : 10
1
1 2
1 3 4
1 4 7 8
1 5 11 15 16
1 6 16 26 31 32
1 7 22 42 57 63 64
1 8 29 64 99 120 127 128
1 9 37 93 163 219 247 255 256
1 10 46 130 256 382 466 502 511 512``````
``````// Node JS program for
// Bernoulli's triangle
class Triangle
{
bernoulliTriangle(n)
{
if (n <= 0)
{
return;
}
// This problem are need N X N space
// But we are solve this problem using using only two rows
// Here 2 indicates row
// And n+1 indicate column value

var dp = Array(2).fill(0).map(() => new Array(n + 1).fill(0));
// Set starting column value
dp[0][0] = 1;
dp[1][0] = 1;
// We can solve this problem only use two rows
// So initial select second row which position is 1
var row = 1;
process.stdout.write("\n Given n : " + n + " \n");
for (var i = 1; i <= n; ++i)
{
// Set intial value of column
dp[0][i] = 0;
dp[1][i] = 0;
// This loop are used to print result in current row
for (var j = 0; j < i; ++j)
{
if (j > 0)
{
if (j + 1 == i)
{
// Last element of current row
dp[row][j] = dp[row][j - 1] + 1;
}
else if (row == 1)
{
// Change second row
dp[row][j] = dp[0][j] + dp[0][j - 1];
}
else
{
// Change first row
dp[row][j] = dp[1][j] + dp[1][j - 1];
}
}
// Display the value
process.stdout.write(" " + dp[row][j]);
}
process.stdout.write("\n");
// Change row
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
}
}
}

function main()
{
/*
n = 6
---------
1
1  2
1  3  4
1  4  7  8
1  5  11  15  16
1  6  16  26  31  32
*/
/*
n = 10
----------
1
1  2
1  3  4
1  4  7  8
1  5  11  15  16
1  6  16  26  31  32
1  7  22  42  57  63  64
1  8  29  64  99  120  127  128
1  9  37  93  163  219  247  255  256
1  10  46  130  256  382  466  502  511  512
*/
}
main();``````

#### Output

`````` Given n : 6
1
1 2
1 3 4
1 4 7 8
1 5 11 15 16
1 6 16 26 31 32

Given n : 10
1
1 2
1 3 4
1 4 7 8
1 5 11 15 16
1 6 16 26 31 32
1 7 22 42 57 63 64
1 8 29 64 99 120 127 128
1 9 37 93 163 219 247 255 256
1 10 46 130 256 382 466 502 511 512``````
``````#  Python 3 program for
#  Bernoulli's triangle
class Triangle :
def bernoulliTriangle(self, n) :
if (n <= 0) :
return

#  This problem are need N X N space
#  But we are solve this problem using using only two rows
#  Here 2 indicates row
#  And n+1 indicate column value
dp = [[0] * (n + 1) for _ in range(2) ]
#  Set starting column value
dp[0][0] = 1
dp[1][0] = 1
#  We can solve this problem only use two rows
#  So initial select second row which position is 1
row = 1
print("\n Given n : ", n ," ")
i = 1
while (i <= n) :
#  Set intial value of column
dp[0][i] = 0
dp[1][i] = 0
j = 0
#  This loop are used to print result in current row
while (j < i) :
if (j > 0) :
if (j + 1 == i) :
#  Last element of current row
dp[row][j] = dp[row][j - 1] + 1
elif (row == 1) :
#  Change second row
dp[row][j] = dp[0][j] + dp[0][j - 1]
else :
#  Change first row
dp[row][j] = dp[1][j] + dp[1][j - 1]

#  Display the value
print(" ", dp[row][j], end = "")
j += 1

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

i += 1

def main() :
#    n = 6
#    ---------
#    1
#    1  2
#    1  3  4
#    1  4  7  8
#    1  5  11  15  16
#    1  6  16  26  31  32
#    n = 10
#    ----------
#    1
#    1  2
#    1  3  4
#    1  4  7  8
#    1  5  11  15  16
#    1  6  16  26  31  32
#    1  7  22  42  57  63  64
#    1  8  29  64  99  120  127  128
#    1  9  37  93  163  219  247  255  256
#    1  10  46  130  256  382  466  502  511  512

if __name__ == "__main__": main()``````

#### Output

`````` Given n :  6
1
1  2
1  3  4
1  4  7  8
1  5  11  15  16
1  6  16  26  31  32

Given n :  10
1
1  2
1  3  4
1  4  7  8
1  5  11  15  16
1  6  16  26  31  32
1  7  22  42  57  63  64
1  8  29  64  99  120  127  128
1  9  37  93  163  219  247  255  256
1  10  46  130  256  382  466  502  511  512``````
``````#  Ruby program for
#  Bernoulli's triangle
class Triangle
def bernoulliTriangle(n)
if (n <= 0)
return
end

#  This problem are need N X N space
#  But we are solve this problem using using only two rows
#  Here 2 indicates row
#  And n+1 indicate column value
dp = Array.new(2) {Array.new(n + 1) {0}}
#  Set starting column value
dp[0][0] = 1
dp[1][0] = 1
#  We can solve this problem only use two rows
#  So initial select second row which position is 1
row = 1
print("\n Given n : ", n ," \n")
i = 1
while (i <= n)
#  Set intial value of column
dp[0][i] = 0
dp[1][i] = 0
j = 0
#  This loop are used to print result in current row
while (j < i)
if (j > 0)
if (j + 1 == i)
#  Last element of current row
dp[row][j] = dp[row][j - 1] + 1
elsif (row == 1)
#  Change second row
dp[row][j] = dp[0][j] + dp[0][j - 1]
else

#  Change first row
dp[row][j] = dp[1][j] + dp[1][j - 1]
end

end

#  Display the value
print(" ", dp[row][j])
j += 1
end

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

row = 1
end

i += 1
end

end

end

def main()
#    n = 6
#    ---------
#    1
#    1  2
#    1  3  4
#    1  4  7  8
#    1  5  11  15  16
#    1  6  16  26  31  32
#    n = 10
#    ----------
#    1
#    1  2
#    1  3  4
#    1  4  7  8
#    1  5  11  15  16
#    1  6  16  26  31  32
#    1  7  22  42  57  63  64
#    1  8  29  64  99  120  127  128
#    1  9  37  93  163  219  247  255  256
#    1  10  46  130  256  382  466  502  511  512
end

main()``````

#### Output

`````` Given n : 6
1
1 2
1 3 4
1 4 7 8
1 5 11 15 16
1 6 16 26 31 32

Given n : 10
1
1 2
1 3 4
1 4 7 8
1 5 11 15 16
1 6 16 26 31 32
1 7 22 42 57 63 64
1 8 29 64 99 120 127 128
1 9 37 93 163 219 247 255 256
1 10 46 130 256 382 466 502 511 512
``````
``````// Scala program for
// Bernoulli's triangle
class Triangle()
{
def bernoulliTriangle(n: Int): Unit = {
if (n <= 0)
{
return;
}
// This problem are need N X N space
// But we are solve this problem using using only two rows
// Here 2 indicates row
// And n+1 indicate column value
var dp: Array[Array[Int]] = Array.fill[Int](2, n + 1)(0);
// Set starting column value
dp(0)(0) = 1;
dp(1)(0) = 1;
// We can solve this problem only use two rows
// So initial select second row which position is 1
var row: Int = 1;
print("\n Given n : " + n + " \n");
var i: Int = 1;
while (i <= n)
{
var j: Int = 0;
// This loop are used to print result in current row
while (j < i)
{
if (j > 0)
{
if (j + 1 == i)
{
// Last element of current row
dp(row)(j) = dp(row)(j - 1) + 1;
}
else if (row == 1)
{
// Change second row
dp(row)(j) = dp(0)(j) + dp(0)(j - 1);
}
else
{
// Change first row
dp(row)(j) = dp(1)(j) + dp(1)(j - 1);
}
}
// Display the value
print(" " + dp(row)(j));
j += 1;
}
print("\n");
// Change row
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Triangle = new Triangle();
/*
n = 6
---------
1
1  2
1  3  4
1  4  7  8
1  5  11  15  16
1  6  16  26  31  32
*/
/*
n = 10
----------
1
1  2
1  3  4
1  4  7  8
1  5  11  15  16
1  6  16  26  31  32
1  7  22  42  57  63  64
1  8  29  64  99  120  127  128
1  9  37  93  163  219  247  255  256
1  10  46  130  256  382  466  502  511  512
*/
}
}``````

#### Output

`````` Given n : 6
1
1 2
1 3 4
1 4 7 8
1 5 11 15 16
1 6 16 26 31 32

Given n : 10
1
1 2
1 3 4
1 4 7 8
1 5 11 15 16
1 6 16 26 31 32
1 7 22 42 57 63 64
1 8 29 64 99 120 127 128
1 9 37 93 163 219 247 255 256
1 10 46 130 256 382 466 502 511 512``````
``````// Swift 4 program for
// Bernoulli's triangle
class Triangle
{
func bernoulliTriangle(_ n: Int)
{
if (n <= 0)
{
return;
}
// This problem are need N X N space
// But we are solve this problem using using only two rows
// Here 2 indicates row
// And n+1 indicate column value
var dp: [[Int]] =
Array(repeating: Array(repeating: 0,
count: n + 1), count: 2);
// Set starting column value
dp[0][0] = 1;
dp[1][0] = 1;
// We can solve this problem only use two rows
// So initial select second row which position is 1
var row: Int = 1;
print("\n Given n : ", n ," ");
var i: Int = 1;
while (i <= n)
{
var j: Int = 0;
// This loop are used to print result in current row
while (j < i)
{
if (j > 0)
{
if (j + 1 == i)
{
// Last element of current row
dp[row][j] = dp[row][j - 1] + 1;
}
else if (row == 1)
{
// Change second row
dp[row][j] = dp[0][j] + dp[0][j - 1];
}
else
{
// Change first row
dp[row][j] = dp[1][j] + dp[1][j - 1];
}
}
// Display the value
print(" ", dp[row][j], terminator: "");
j += 1;
}
print(terminator: "\n");
// Change row
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
i += 1;
}
}
}
func main()
{
/*
n = 6
---------
1
1  2
1  3  4
1  4  7  8
1  5  11  15  16
1  6  16  26  31  32
*/
/*
n = 10
----------
1
1  2
1  3  4
1  4  7  8
1  5  11  15  16
1  6  16  26  31  32
1  7  22  42  57  63  64
1  8  29  64  99  120  127  128
1  9  37  93  163  219  247  255  256
1  10  46  130  256  382  466  502  511  512
*/
}
main();``````

#### Output

`````` Given n :  6
1
1  2
1  3  4
1  4  7  8
1  5  11  15  16
1  6  16  26  31  32

Given n :  10
1
1  2
1  3  4
1  4  7  8
1  5  11  15  16
1  6  16  26  31  32
1  7  22  42  57  63  64
1  8  29  64  99  120  127  128
1  9  37  93  163  219  247  255  256
1  10  46  130  256  382  466  502  511  512``````
``````// Kotlin program for
// Bernoulli's triangle
class Triangle
{
fun bernoulliTriangle(n: Int): Unit
{
if (n <= 0)
{
return;
}
// This problem are need N X N space
// But we are solve this problem using using only two rows
// Here 2 indicates row
// And n+1 indicate column value
var dp: Array < Array < Int >> = Array(2)
{
Array(n + 1)
{
0
}
};
// Set starting column value
dp[0][0] = 1;
dp[1][0] = 1;
// We can solve this problem only use two rows
// So initial select second row which position is 1
var row: Int = 1;
print("\n Given n : " + n + " \n");
var i: Int = 1;
while (i <= n)
{
var j: Int = 0;
// This loop are used to print result in current row
while (j < i)
{
if (j > 0)
{
if (j + 1 == i)
{
// Last element of current row
dp[row][j] = dp[row][j - 1] + 1;
}
else if (row == 1)
{
// Change second row
dp[row][j] = dp[0][j] + dp[0][j - 1];
}
else
{
// Change first row
dp[row][j] = dp[1][j] + dp[1][j - 1];
}
}
// Display the value
print(" " + dp[row][j]);
j += 1;
}
print("\n");
// Change row
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
/*
n = 6
---------
1
1  2
1  3  4
1  4  7  8
1  5  11  15  16
1  6  16  26  31  32
*/
/*
n = 10
----------
1
1  2
1  3  4
1  4  7  8
1  5  11  15  16
1  6  16  26  31  32
1  7  22  42  57  63  64
1  8  29  64  99  120  127  128
1  9  37  93  163  219  247  255  256
1  10  46  130  256  382  466  502  511  512
*/
}``````

#### Output

`````` Given n : 6
1
1 2
1 3 4
1 4 7 8
1 5 11 15 16
1 6 16 26 31 32

Given n : 10
1
1 2
1 3 4
1 4 7 8
1 5 11 15 16
1 6 16 26 31 32
1 7 22 42 57 63 64
1 8 29 64 99 120 127 128
1 9 37 93 163 219 247 255 256
1 10 46 130 256 382 466 502 511 512``````

## Time Complexity

The time complexity of the code is O(n^2) because we have two nested loops, one running `n` times and the other running at most `n` times. As a result, the time taken to construct and print the first `n` rows of Bernoulli's Triangle grows quadratically with `n`.

## Resultant Output Explanation

The output of the code matches the expected values for the first `n` rows of Bernoulli's Triangle. The program successfully prints the triangular array with the correct values.

In the provided output, two examples are shown: one with `n = 6` and another with `n = 10`. Each row is printed, and the numbers in each row are separated by spaces to create the triangular format.

## Finally

Bernoulli's Triangle is an interesting mathematical construct related to Pascal's Triangle. The C program provided successfully prints the first `n` rows of Bernoulli's Triangle using a space-efficient approach and the summing rule. The explanation, example, pseudocode, algorithm, and output provided above should help you understand the concept and implementation of Bernoulli's Triangle in a clear and concise manner.

## 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.

Categories
Relative Post