C++ Program to Print Fibonacci Triangle

Fibonacci Triangle Program in CPP

Definition:

Fibonacci Triangle as the name suggests is the same as the Fibonacci number series where the next element is the sum of the previous two elements. But, there's a logical difference in Fibonacci Triangle. Typically, Fibonacci Triangle is a triangular arrangement (like Pascal's Triangle). In Fibonacci Triangle, each number is the sum of the two numbers covering left diagonals or right diagonals.

After rearranging the triangle, it may look like

Note: A Fibonacci Triangle is also called as Hasoya’s Triangle.

Various recurrence relations properly explain the logic behind it.

Consider a Fibonacci recurrence relation

H(0, 0) = H(1, 0) = H(1, 1) = H(2, 1) = 1

The numbers in the triangle obey recurrence relations.

Also,

 H(n, j) = H(n ? 1, j) + H(n ? 2, j)
 = H(n ? 1, j ? 1) + H(n ? 2, j ? 2). 

 From these relations, we can conclude that:

1. The outermost diagonals are Fibonacci Numbers.

• The numbers on middle vertical line are squares of     Fibonacci Numbers.

Let us look at the code below.

 #include<bits/stdc++.h>
 using namespace std;
 int FibonacciTriangle(int number)
 {
     int dp[N][N];
     memset(dp, 0, sizeof(dp));
     dp[0][0] = dp[1][0] = dp[1][1] = 1;
     for (int i = 2; i < number; i++) {
         for (int j = 0; j < number; j++) {
             if (i > j)
                 dp[i][j] = dp[i - 1][j] + dp[i - 2][j];
             else
                 dp[i][j] = dp[i - 1][j - 1] + dp[i - 2][j - 2];
         }
     }
     for (int i = 0; i < number; i++) {
         for (int j = 0; j <= i; j++) 
             cout << dp[i][j] << " ";        
         cout << endl;
     }
 }
 int main()
 {
     int number;
     cin>>number;
     FibonacciTriangle(number);
 return 0;
 } 

Output:

Explanation:

The above code is a representation of the Fibonacci Triangle. It follows various programming approaches usually dynamic programming.

Function Fibonacci Triangle takes a number from the user and the function is defined as a 2D array that takes values in the forms of rows and columns. The row and column are assigned 0 and 1 value initially. According to the following formula

             H(n ? 1, j ? 1) + H(n ? 2, j ? 2).

Here, if the input is taken as 6, it will print Fibonacci Numbers in the sequence of rows and columns based on either left or right diagonals.

The two loops are defined to iterate over rows and columns. Since the array is multi-dimensional, we can use dynamic programming to assign values in a sequential arrangement that satisfies the above formula for Fibonacci numbers. It ensures that the outermost diagonals are Fibonacci numbers and the middle vertical elements are the square of Fibonacci Numbers.

The next loop iterates through the values in rows and columns and prints them on the console.

Numbers in Characters in C++

It is a popular programming practice where we are supposed to generate strings respective to the digits entered. In order words, numbers in characters simply mean to convert numbers into the characters like they are called.

Example:

 Given an integer N. Task is to convert number in character

Input: 12345

Output: one two three four five

Code:

 #include<bits/stdc++.h>
 using namespace std;
 int NumChar(int number)
 {
     int reverse = 0, r = 0;
     while (number > 0) {
         r = number % 10;
         reverse = reverse * 10 + r;
         number = number / 10;
     }
     while (reverse > 0) {
         r = reverse % 10;
         switch (r) {
         case 1:
             cout << "one ";
             break;
         case 2:
             cout << "two ";
             break;
         case 3:
             cout << "three ";
             break;
         case 4:
             cout << "four ";
             break;
         case 5:
             cout << "five ";
             break;
         case 6:
             cout << "six ";
             break;
         case 7:
             cout << "seven ";
             break;
         case 8:
             cout << "eight ";
             break;
         case 9:
             cout << "nine ";
             break;
         case 0:
             cout << "zero ";
             break;
         default:
             cout << "Invalid ";
             break;
         }
         reverse = reverse / 10;
     }
 }
 int main()
 {
     int number;
     cin>>number;
     NumChar(number);
     return 0;
 } 

Output:

Explanation:

Start

1. Define a function taking integer input.
2. Reverse the number.
3. Carry out right to left iteration.
4. Find last digit with the help of modulus operator.
5. Divide the number by 10 to get the factor.
6. Switch case to find the corresponding character.
7. Call the function in the drive code with the number entered.

Note: We can also use loops but that will increase time complexity.