Thread: pascal triangle

  1. #1
    Registered User
    Join Date
    Oct 2004
    Posts
    2

    pascal triangle

    i am wondering if anyone knows an easy way to write a c++ program that asks for a number and then prints that row of the pascal triangle without displaying the rows before it.
    Thanks for any help received

  2. #2
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    Google on the binomial theorem. You can do it with factorials (combinatorials).
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  3. #3
    Registered User
    Join Date
    Oct 2004
    Posts
    26
    Well, just calculate the row first, before printing it out.

    You could have two arrays of int, oldrow & newrow.

    Initialize newrow with the first row of pascal's triangle, and initialize some counter variable. As long as you have not counted up to the row you want, keep doing the following: copy newrow to oldrow, then use oldrow to calculate a new newrow, then update your counter variable.

    Now print out newrow.

  4. #4
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    Your arrays will have to keep growing, though, as the rows expand.
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  5. #5
    Registered User
    Join Date
    Oct 2004
    Posts
    17
    Definitely binomial theorem! The other would be a waste of time!

    (x+y)^n = x^n + (n*x^(n-1)*y)/(1!) + (n*(n-1)*x^(n-2)*y^2)/(2!) + (n*(n-1)*(n-2)*x^(n-3)*y^3)/(3!) +...+y^n

    Remember to be careful the 7th row will have 7 terms but n=6 in the formula. In a more general sense the nth row will have n terms but n-1 will need to be the exponent in the binomial theorem.

  6. #6
    Registered User
    Join Date
    Oct 2004
    Posts
    26
    You could just declare two fixed arrays of large enough size, like 100 cells each. That's not so expensive, and it more than exceeds the maximum row of Pascal's triangle that can be accurately calculated using the pre-provided numerical types:
    1. if you declared the arrays to be of unsigned long int, on my computer, sizeof(unsigned long int) == 4 bytes = 32 bits. So, the maximum possible unsigned long int is 2^32 - 1.
    2. if you declared the arrays to be of long double, on my computer, sizeof(long double) == 10 bytes = 80 bits. So, even if all 80 bits were used to represent significant digits (which isn't the case, since some bits have to be used to represent the exponent), the maximum number you could represent before losing track of the one's digit is 2^80 - 1.

    But for large n, C(2n,n) ~ 2^{2n}/sqrt(pi*n) (use Stirling's approximation, n! ~ sqrt(2*pi*n)*(n/e)^n), so C(100,50) ~ 2^100/sqrt(pi*50) > 2^100/sqrt(256) = 2^96, not accurately representable even by long double.

  7. #7
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    I've already written code to do that, with one diference: it writes all lines till one number is bigger than 10^60. It can easily be changed to print that specific line. If you wanted I'll gradly post it here.
    //edit
    To present each number I use
    __int64 number[4];
    //4 is and example
    And it was made in pure C.
    Last edited by xErath; 10-05-2004 at 09:10 AM.

  8. #8
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    Just remember that with floating point numbers, large and small numbers don't add together too well.
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  9. #9
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    A Pascal's triangle is a triangle of INTEGERs.
    If you don't want precision you may use long doubles. If you want precision use an array of int to store pieces of the number.
    Like:
    Code:
    //store 34141340013401041979003456305
    #define DIVISOR 1000//numbers are stored from 0 to 999 in each element
    int number[10];
    number[9]=34;
    number[8]=141;
    number[7]=340;
    number[6]=013;
    number[5]=401;
    number[4]=041;
    number[3]=979;
    number[2]=003;
    number[1]=456;
    number[0]=305;
    When printing be careful with the zeros

  10. #10
    Registered User
    Join Date
    Oct 2004
    Posts
    2
    Quote Originally Posted by xErath
    I've already written code to do that, with one diference: it writes all lines till one number is bigger than 10^60. It can easily be changed to print that specific line. If you wanted I'll gradly post it here.
    //edit
    To present each number I use
    __int64 number[4];
    //4 is and example
    And it was made in pure C.
    please post it ... thanks

  11. #11
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    Code:
    #include<stdio.h>
    
    #define SIZE_NUM 1000000000000000000	/* 2^64 = 18446744073709551616 ~ 1e+19 -> 8 bytes (18 zeros)*/
    #define N_INT 4
    /*205 lines needed*/
    #define MAX_LINES 204
    
    #ifdef WIN32
    typedef unsigned __int64 uint64;
    #else
    typedef unsigned long long int uint64;
    #endif
    
    int main(void)
    {
    	/*array that stores the numbers in a single row - 4 elements * 18 zeros = 72 zeros > 60 zeros: the max asked*/
    	uint64  line[MAX_LINES+2][N_INT] = {{1}}, expt, temp;
    	long int i=1, j, n_cicles=0;
    	
    	putchar('1');
    	while(n_cicles<MAX_LINES)
    	{
    		/*SUM*/
    		for(/*i already defined in output cicle */; i>0; i--){/*sum cicle*/
    			for(j=0;j<N_INT; j++)
    			{
    				temp = line[i][j] + line[i-1][j];
    				line[i][j]   = temp%SIZE_NUM;
    				line[i][j+1] = temp/SIZE_NUM + line[i][j+1];
    			}/*for*/
    		}/*for*/
    
    		/*OUTPUT*/
    		printf("\n1 %d", line[1][0]);
    		for(i=2;line[i][0];i++){	/*cicle to write all numbers*/
    			for(j=N_INT-1;j>=0;j--)		/*cicle to write the 4 pieces of a number*/
    				if(line[i][j]){
    					printf(" %I64d", line[i][j--]);
    					break;
    				}/*if*/
    			/*for*/
    
    			while(j>=0){
    				expt=SIZE_NUM/10;
    				while(1){
    					if(line[i][j]/expt)	break;
    					putchar('0');					
    					expt/=10;
    				}/*while(1)*/
    				printf("%I64d", line[i][j]);
    				j--;
    			}/*while(j>-1)*/
    		}/*for(i=2;!(line[i]);i++)*/
    		n_cicles++;
    	}/*while(n_cicles<205)*/
    
    	return(0);
    }
    Like I said this is C. I decided to post my code. Try to change it and adapt it to your problem. This code presents all lines till one number exceeds 10^60 so you should consider later the number of lines defined in MAX_LINES, and the space necessary for a single number defined in N_INT. Good luck

  12. #12
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    A closed form solution: Column k of row n of pascals triangle is given by nCk (n choose k) where k goes from 0 to n (n + 1 values).

    The formula for nCk is n!/[ (n - k)! * k! ]. This can be simplified (yielding a greater range due to lower wraparound errors for integers) as n*(n-1)*(n-2)*...*(n-r+1) / r!. It is conceivable that it'll become simpler, but I can't compute what at the moment.
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  13. #13
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    What about: each element in a pascal's triangle of index n is the sum of elements n and n-1 in the previous row??? So, while loop till calculation ends... Calculating factorials and keep the results with full precision could be a bit hard.

  14. #14
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    You can rig it fairly easily so that your value never actually exceeds the value in the corresponding entry for pascal's triangle with only a little bit of cleverness. Give me a few minutes, and I'll post an example (note, I don't have a compiler on this computer, so the example will be one that should work, but please forgive any small errors).
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  15. #15
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    Code:
    unsigned int get_entry(unsigned int n, unsigned int k)
    {
       if (k >= (n + 1) / 2)
       {
          return get_entry(n, n - k);
       }
       
       unsigned int value = 1; // The return value.
       unsigned int next = k;  // The next term to be divided out in k!.
    
       for(unsigned int itr = n; itr >= (n - r + 1); --itr)
       {
          if (next >= 2 && itr % next == 0)
          {
             value *= itr / next;
             --next;
          }
          else
          {
             value *= next;
          }
       }
       
       return value;
    }
    A very rough example (to show intent only). The code is untested, as mentioned above, and there is a mild bit of sketchy number theory.

    The sketchy bit of number theory has to do with where I'll find multiples of a number (linear order as I have assumed?), but the point is to show that this can be done.
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Recursive Triangle Function
    By w2look in forum C Programming
    Replies: 14
    Last Post: 11-13-2010, 02:31 PM
  2. Right Triangle Program
    By BSmith4740 in forum C# Programming
    Replies: 9
    Last Post: 02-27-2008, 12:24 AM
  3. Just in case: "Odd" Triangle Challenge (for me)
    By BB18 in forum C Programming
    Replies: 3
    Last Post: 10-09-2004, 12:02 AM
  4. Pascal triangle numbers generation~
    By bljonk in forum C Programming
    Replies: 6
    Last Post: 03-22-2002, 02:25 PM
  5. Pascal Triangle
    By Unregistered in forum C++ Programming
    Replies: 2
    Last Post: 02-22-2002, 01:34 PM