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:
- Start with an integer
n
as input, which represents the number of rows to be printed. - Create a 2D array
dp
of size2 x (n+1)
to store the values of Bernoulli's Triangle. Initialize it with zeros. - 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.
- Initialize a variable
row
to keep track of the current row we are working with. Start with the second row (row = 1). - Use two nested loops to fill the values of each row. The outer loop (
i
) runs from 1 ton
, representing the row number. The inner loop (j
) runs from 0 toi-1
, representing the columns in that row. - 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.
- Print each value as it is calculated.
- After printing all the values in a row, move to the next row by changing the value of
row
. Ifrow
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)
{
Triangle task = 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
*/
task.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
*/
task.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
// 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()
{
Triangle *task = 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
*/
task->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
*/
task->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
// 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)
{
Triangle task = 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
*/
task.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
*/
task.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
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()
{
$task = 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
*/
$task->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
*/
$task->bernoulliTriangle(10);
}
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()
{
var task = 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
*/
task.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
*/
task.bernoulliTriangle(10);
}
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() :
task = Triangle()
# n = 6
# ---------
# 1
# 1 2
# 1 3 4
# 1 4 7 8
# 1 5 11 15 16
# 1 6 16 26 31 32
task.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
task.bernoulliTriangle(10)
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()
task = Triangle.new()
# n = 6
# ---------
# 1
# 1 2
# 1 3 4
# 1 4 7 8
# 1 5 11 15 16
# 1 6 16 26 31 32
task.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
task.bernoulliTriangle(10)
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
*/
task.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
*/
task.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
// 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()
{
let task: Triangle = Triangle();
/*
n = 6
---------
1
1 2
1 3 4
1 4 7 8
1 5 11 15 16
1 6 16 26 31 32
*/
task.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
*/
task.bernoulliTriangle(10);
}
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
{
val task: Triangle = Triangle();
/*
n = 6
---------
1
1 2
1 3 4
1 4 7 8
1 5 11 15 16
1 6 16 26 31 32
*/
task.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
*/
task.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
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.
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