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
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
Google on the binomial theorem. You can do it with factorials (combinatorials).
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.
Your arrays will have to keep growing, though, as the rows expand.
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.
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.
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.
Just remember that with floating point numbers, large and small numbers don't add together too well.
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:
When printing be careful with the zerosCode://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;
please post it ... thanksQuote:
Originally Posted by xErath
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 :cool: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);
}
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.
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.
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).
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.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.
As an after-thought, the function should test for the highest divisor between 1...k (or, for efficiency's sake, simply the highest of the set of integers 1...k that a given number divides out. This is the solutions I was going for (but it's late, I'm tired, and I have much work to do - which I am avoiding at the moment - so anyone who wants to mess with it feel free). You'd have to compute and store k!, and then just divide out those numbers until whatever value holding k! initially becomes 1 (then stop dividing when you multiply the next number in the sequence as well). The iterative solution is probably faster for the earlier rows, but this one doesn't grow very fast. Still the fastest for very small rows would be just to actually do the division.