Skip to content

Instantly share code, notes, and snippets.

@watmough
Created January 6, 2012 05:18
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save watmough/1569136 to your computer and use it in GitHub Desktop.
Save watmough/1569136 to your computer and use it in GitHub Desktop.
Better C implementation for Pascals Triangle
/*
* Pascal2.c
*
* Pascals Triangle in C
*
* See notes below.
* To run:
gcc -std=c99 pascal2.c -o pascal2 && ./pascal2 10
*/
#include <stdio.h>
#include <stdlib.h>
long *pascal( int rows )
{
long *line = (long*)malloc(sizeof(long)*rows);
line[0]=1;
int r,c,p1,p2;
for (r=1,p1=1;r<rows;++r)
{
for (c=1; c<r; ++c)
{
p2=p1;
p1=line[c];
line[c]=p2+p1;
}
line[r]=1;
}
return line;
}
int main( int argc, char**argv )
{
if (argc!=2) {
printf("usage: pascal2 <n>\n");
exit(1);
}
int rows = atoi(argv[1]);
long *line = pascal(rows);
int col;
for (col=0; col<rows; ++col) {
printf("%ld ",line[col]);
}
printf("\n");
exit(0);
}
/*
Notes for a better implementation:
1
11
121 ... a
1331 ... b
14641
To update in-situ, just need to save overwritten entry or
defer writing until the next column written.
ok, after several minutes, we need to save what we need and
fifo what we are summing for the next line.
p1=before update
p2=previous column before update
b[0]=1
p1=b[0]
i:1->count-2
p2=p1
p1=a[i]
b[i]=p2+p1
b[count-1]=1
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment