It is a commonly asked algorithm question that is asked in onsite technical interviews. Below is the pascal
1
1 1
1 2 1
1 3 3 1
First iteration of returns 1
Second iteration returns 1(taken from above row 1) and 1+0
Third iteration returns 1(taken from above row 2), then 2(which is column 1+1) and 1(which is 1 + 0)
Fourth iteration returns 1(taken from row 3 and column 0), then 3(which is 1+2) then 3(which is 2 + 1), then 1(which is 1 + 0)
Algorithm :
Step 1: Call Pascal function with the value 5 (Height of pascal triangle) from the main function.
Step 2: Declare and initialize row and column variables to 0(zero).
Step 3: In pascal function, Initialize the 5x5 matrix “a” with 0(zero).
Initial matrix “a”,
Step 4: Using nested for loop,find pascal triangle values for each row.
Outer loop for each row(0 to 4) and inner loop for column values.
Iteration 1 (outer loop):
row=0 and 0<5 -> Condition true
For the inner loop, “col<=row” condition is used. Because,
Every row has a number of integers equal to the row number.
Iteration 1.1 (inner loop) :
col=0 and 0<=0 ->Condition true
IF : (First and last values in every row are 1)
(row)0==0(col) and 0==0 -> Condition true
a[0][0] = 1
col=1 (incremented by 1)
Iteration 1.2 (inner loop) :
col=1 and 1<=0 -> condition false.
Terminate the inner loop for the row 0.
row = 1 (incremented by 1)
Iteration 2 (outer loop) :
row=1 and 1<5 -> Condition true
Iteration 2.1 (inner loop) :
col=0 and 0<=1 -> Condition true
IF : (First and last values in every row are 1)
(row)1==0(col) || 0==0 -> Condition true
a[1][0] = 1
col=1 (incremented by one)
Iteration 2.2 (inner loop) :
col=1 and 1<=1 -> condition true
IF : (First and last values in every row are 1)
(row)1==1(col) || 1==1 -> Condition true
a[1][1] = 1
col=2 (incremented by one)
Iteration 2.3 (inner loop) :
col=2 and 2<=1 -> condition false
Terminate the inner loop for the row 1.
row=2 (incremented by 1)
Iteration 3 (outer loop) :
row=2 and 2<5 -> Condition true
Iteration 3.1 (inner loop) :
col=0 and 0<=2 -> Condition true
IF : (First and last values in every row are 1)
(row)2==0(col) || 0==0 -> Condition true
a[2][0] = 1
col=1 (incremented by one)
Iteration 3.2 (inner loop) :
col=1 and 1<=2 -> condition true
IF : (First and last values in every row are 1)
(row)2==1(col) || 1==0 -> Condition false
ELSE : (other values = values just above + left of above)
a[2][1] = a[1][1] + a[1][0]
a[2][1] = 1 + 1
a[2][1] = 2
col=2 (incremented by one)
Iteration 3.3 (inner loop) :
col=2 and 2<=2 -> condition true
IF : (First and last values in every row are 1)
(row)2==2(col) || 2==0 -> Condition true
a[2][2] = 1
col=3 (incremented by 1)
Iteration 3.4 (inner loop) :
col=3 and 3<=2 -> condition false.
Terminate the inner loop for the row 2.
row=3 (incremented by 1)
Iteration 4 (outer loop) :
row=3 and 3<5 -> Condition true
Iteration 4.1 (inner loop) :
col=0 and 0<=3 -> Condition true
IF : (First and last values in every row are 1)
(row)3==0(col) || 0==0 -> Condition true
a[3][0] = 1
col=1 (incremented by one)
Iteration 4.2 (inner loop) :
col=1 and 1<=3 -> condition true
IF : (First and last values in every row are 1)
(row)3==1(col) || 1==0 -> Condition false
ELSE : (other values = values just above + left of above)
a[3][1] = a[2][1] + a[2][0]
a[3][1] = 2 + 1
a[3][1] = 3
col=2 (incremented by one)
Iteration 4.3 (inner loop) :
col=2 and 2<=3 -> condition true
IF : (First and last values in every row are 1)
(row)3==2(col) || 2==0 -> Condition false
ELSE : (other values = values just above + left of above)
a[3][2] = a[2][2] + a[2][1]
a[3][2] = 1 + 2
a[3][2] = 3
col=3 (incremented by 1)
Iteration 4.4 (inner loop) :
col=3 and 3<=3 -> Condition true
IF : (First and last values in every row are 1)
(row)3==3(col) || 3==0 -> Condition true
a[3][3] = 1
col=4 (incremented by one)
Iteration 4.5 (inner loop) :
col=4 and 4<=3 -> condition false.
Terminate the inner loop for the row 3.
row=4 (incremented by 1)
Iteration 5 (outer loop) :
row=4 and 4<5 -> Condition true
Iteration 5.1 (inner loop) :
col=0 and 0<=4 -> Condition true
IF : (First and last values in every row are 1)
(row)4==0(col) || 0==0 -> Condition true
a[4][0] = 1
col=1 (incremented by one)
Iteration 5.2 (inner loop) :
col=1 and 1<=4 -> condition true
IF : (First and last values in every row are 1)
(row)4==1(col) || 1==0 -> Condition false
ELSE : (other values = values just above + left of above)
a[4][1] = a[3][1] + a[3][0]
a[4][1] = 3 + 1
a[4][1] = 4
col=2 (incremented by one)
Iteration 5.3 (inner loop) :
col=2 and 2<=4 -> condition true
IF : (First and last values in every row are 1)
(row)4==2(col) || 2==0 -> Condition false
ELSE : (other values = values just above + left of above)
a[4][2] = a[3][2] + a[3][1]
a[4][2] = 3 + 3 = 6
col=3 (incremented by 1)
Iteration 5.4 (inner loop) :
col=3 and 3<=4 -> condition true
IF : (First and last values in every row are 1)
(row)4==3(col) || 3==0 -> Condition false
ELSE : (other values = values just above + left of above)
a[4][3] = a[3][3] + a[3][2]
a[4][3] = 1 + 3
a[4][3] = 4
col=4 (incremented by 1)
Iteration 5.5 (inner loop) :
col=4 and 4<=4 -> Condition true
IF : (First and last values in every row are 1)
(row)4==4(col) || 4==0 -> Condition true
a[4][4] = 1
col=5 (incremented by one)
Iteration 5.6 (inner loop) :
col=5 and 5<=4 -> condition false.
Terminate the inner loop for the row 4.
row=5 (incremented by 1)
Iteration 6 (outer loop) :
row=5 and 5<5 -> Condition false
Terminate the outer loop.
Step 5 : Using a nested loop to print the pascal triangle to the console.
Print if a[row][col] != 0,
then the final output is
Output:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Implementation:
#include <iostream>
#include <conio.h>
#include <stdio.h>
using namespace std;
void pascal(int level)
{
int row = 0, col = 0;
int a[5][5] = {0};
for(row=0;row<level;row++)
{
for(col=0;col<=row;col++)
{
if(row==col || col==0)
a[row][col] = 1;
else
a[row][col] = a[row-1][col] + a[row-1][col-1];
}
}
cout<<"Output : "<<"\n";
for(row=0;row<level;row++)
{
for(col=0;col<level;col++)
{
if(a[row][col]!=0)
cout<<a[row][col]<<"\t";
}
cout<<endl;
}
}
int main()
{
pascal(5);
getch();
return 0;
}
Algorithm complexity :
O(m*n) here m = row and n = column
No comments:
Post a Comment