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

Printable View

- 10-04-2004ndukaa1pascal 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 - 10-04-2004Zach L.
Google on the binomial theorem. You can do it with factorials (combinatorials).

- 10-05-2004zzzaaahhh
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. - 10-05-2004Zach L.
Your arrays will have to keep growing, though, as the rows expand.

- 10-05-2004just2peachy
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. - 10-05-2004zzzaaahhh
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:

- 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.
- 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. - 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.
- 10-05-2004xErath
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. - 10-05-2004Zach L.
Just remember that with floating point numbers, large and small numbers don't add together too well.

- 10-05-2004xErath
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;

- 10-05-2004ndukaa1Quote:

Originally Posted by**xErath**

- 10-05-2004xErathCode:
`#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);

}

- 10-05-2004Zach L.
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. - 10-05-2004xErath
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.

- 10-05-2004Zach L.
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). - 10-05-2004Zach L.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;

}

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.