4 ms·
Here's my version in C: int main(int argc, char ** argv) { long *n1,*n2; int row,i; row=0; N1[0]=1L; print_row(row,N1); while(r
by rayval 15y ago
Here's my version in C:
int main(int argc, char ** argv)
{
long *n1,*n2;
int row,i;
row=0; N1[0]=1L; print_row(row,N1);
while(row++ < MAX_ROWS)
{
for(i=0, n1 = N1, n2=N2; i<MAX_BUF && *n1; i++)
{
if (i==0 ) n2[i] = 0 + n1[i];
else if(n1[i]==0) n2[i] = n1[i-1] + 0;
else n2[i] = n1[i-1] + n1[i];
}
print_row(row,N2);
for(n1=N1,n2=N2; *n2; ) *n1++ = *n2++;
}
}
void print_row(int row,long*n)
{
printf("row #%d",row);
while(*n) { printf(" %ld ", *n++);}
printf("\n");
}
This works through the size of long int (at least 50 rows).
- haberman 15y agoI think some of your code is missing (like where N1 and MAX_ROWS are defined). Here's mine: #include <stdio.h> #include <stdlib.h> long *pascal(int row) { long *ret = (row == 1 ? NULL : pascal(row - 1)); ret = realloc(ret, sizeof(long) * row); ret[row - 1] = 1; for (int i = row - 2; i > 0; i--) ret[i] += ret[i - 1]; return ret; } int main(int argc, char *argv[]) { int row = atoi(argv[1]); long *data = pascal(row); for (int i = 0; i < row; i++) printf("%ld ", data[i]); printf("\n"); free(data); return 0; }
- jiggy2011 15y agoupvoted for realloc trick
- haberman 15y agoThis inspired me to write one that is even shorter and doesn't heap-allocate any memory at all. What can I say, I'm a sucker for minimal C. #include <stdio.h> #include <stdlib.h> int main(int argc, char *argv[]) { int row = atoi(argv[1]); long data[row]; for (int i = 0; i < row; i++) { data[i] = 1; for (int j = i - 1; j > 0; j--) data[j] += data[j - 1]; } for (int i = 0; i < row; i++) printf("%ld ", data[i]); printf("\n"); return 0; }
- hn_reader 15y agoBest solution I've seen here so far.
- deleted 15y ago[deleted]
- demallien 15y agoWhen did C start accepting non-constants for array size declarations?
- shaggyfrog 15y agoIf row is too big you can bust your stack frame when you define your data array.
- hn_reader 15y agoTrue, though in this example integer overflow would happen first.
- kunqiana 15y agoI think your code is off by 1.
- zyzzy 15y agoHi, I ran your code and it does run well. However fails for large cases such as pascal(200000). You mentioned you worked for Google and Amazon, how can you modify the code to get an answer for pascal(200000)
- haberman 15y agoYeah, for large cases the long will overflow (also it will do a lot of realloc()). Your two main options for this are: 1. use double to get approximately-correct answers 2. use an abitrary-precision library like GMP
- zyzzy 15y agoWhat if I wanted an exact precision. Could I use a custom data type to get better precision? If I used a custom data type, how could I make the code work for a distributed system to get parallel behavior?