Jul 16, 2014

C Programming Challenge #01: Pascals Traingle

Following article is one of the article in section - C Mastering Challenges.

Problem Statement:


Write a C Program to print Pascal's Triangle ?

For example:- 
    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1

You can go ahead and start programming it.

More explanation of problem
Pascals triangle is formed by adding two adjacent number from top row.



Note that, if there is no number it is assumed to be 0.

You can find an excellent article on Pascals triangle here.  Also some of the properties of Pascals triangle in the article are just mind blowing.


If you analyse the row number and number in the boxes, we see following pattern -

nCr is the number of different, un-ordered combinations of r objects from a set of n objects.
Definition: nCr(n,r) = n! / (n-r)! r!

In above definition '!' stands for factorial. There is no correlation of this problem to combinations of n objects in r ways. But it is just that the pattern of numbers follow nCr. We have already written pyramid of stars using for loop in Program 3 of C Programming #26: Loop -  nested. Same program can be modified as follows.



#include <stdio.h>

int ncr(int, int);
int fact(int);

int main()
{
   int max = 5; /* Maximum number of rows */
   int row_cnt;
   int space_cnt;
   int star_cnt;
   int num;

   for(row_cnt = 1; row_cnt <= max; row_cnt++) {
      for(space_cnt = 1; space_cnt <= max - row_cnt; space_cnt++) {
          printf(" ");
      }
      for(star_cnt = 1; star_cnt <= row_cnt; star_cnt++) {
      num = ncr(row_cnt - 1, star_cnt - 1);
          printf("%d ", num);
      }
      printf("\n");
   }
   return 0;
}

int ncr(int n, int r)
{
   return fact(n)/(fact(n-r) * fact(r));
}
int fact(int n)
{
   int i;
   int f = 1;

   for(i = 1; i <= n; i++) {
      f = f * i; 
   }
   return f;
}

Tricky part of understanding any C program is 
  1. Is to get overview of what each function is doing.
  2. Next is to go with what each of loop doing ? Why are they even used ?
  3. Go to detail of why initial value and condition.
Hope you enjoyed it :) 


Links 

Next Article - C Programming Challenge #02: Sort - insertion
Previous Article - None
All Article - C Programming Challenge

No comments :

Post a Comment