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)
    {
        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.

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