This is a C++ Program that Solves Forming Triangles Problem – Catalan Numbers using Dynamic Programming technique.
In how many ways a plane convex polygon of n sides can be divided into triangles by diagonals?
This problem can be solved using catalan numbers. Catalan numbers forms a sequence of natural numbers based on a recursive formula(like fibonacci). Catalan numbers are used in various counting problems, this being one of them.
Let C[n]=nth catalan number
Total number of ways in which a convex polygon of n sides can be divided into triangles by diagonals = C[n-2]
Time Complexity of this solution is O(n^2).
Case-1:
If n=3, Expected result=1, the triangle itself
Case-2:
If n=4, Expected result=2, a quadrilateral can be divided into triangle in two ways (using one diagonal every time)
Case-3:
If n=5, Expected result=5
Here is source code of the C++ Program to Solve Forming Triangles Problem – Catalan Numbers. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.
#include<iostream>
using namespace std;
int catalan_polygon(int n)
{
//we are given a convex polygon of n sides
//we have to find out in how many ways a plane convex polygon of n sides can be divided into triangles by diagonals
//result will be equal to (n-2)th catalan number ie, c[n-2]
int c[n-1];
//c[i]=total number of ways in which a plane convex polygon of (i+2) sides can be divided into triangles by diagonals
//initialize
c[0]=1;
c[1]=1;
c[2]=2;
int i,j;
//now, using bottom up DP, we will implement the recursive formula of catalan number to find the required value
for(i=3;i<=(n-2);i++)
{
c[i]=0;
for(j=0;j<i;j++)
{
c[i]+=c[j] * c[(i-1)-j];
}
}
return c[n-2];
}
int main()
{
int n;
cout<<"Enter the number of sides in the convex polygon(>=3)"<<endl;
cin>>n;
cout<<"Total number of ways in which a convex polygon of "<<n<<" sides can be divided into triangles by diagonals is "<<endl;
cout<<catalan_polygon(n);
cout<<endl;
return 0;
}
In the main function, we ask the user to input the number of sides in the polygon. We pass this value to the function catalan_polygon as parameter. This function will calculate the expected result and return it. The returned value will be displayed.
Case-1: $ g++ catalan_polygon.cpp $ ./a.out Enter the number of sides in the convex polygon(>=3) 5 Total number of ways in which a convex polygon of 5 sides can be divided into triangles by diagonals is 5
Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.
- Get Free Certificate of Merit in Data Structure I
- Participate in Data Structure I Certification Contest
- Become a Top Ranker in Data Structure I
- Take Data Structure I Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Practice Design & Analysis of Algorithms MCQ
- Practice Computer Science MCQs
- Apply for Information Technology Internship
- Buy Computer Science Books
- Apply for Computer Science Internship