patterncMinor
Pascal's triangle in C
Viewed 0 times
pascaltrianglestackoverflow
Problem
I am relearning C so if you could point obvious faults in this solution to this problem I'd greatly appreciate such comments. Please note that I'm using GCC extensions to use larger than 32 bit numbers. Most importantly I want to be aware of the quality of memory management in particular.
http://news.ycombinator.com/item?id=3429466
http://news.ycombinator.com/item?id=3429466
#include
#include
int64_t* next_pascal_row(int64_t* previous_row, int64_t previous_size)
{
int64_t i;
int64_t* retval;
retval = (int64_t*)malloc(sizeof(int64_t)*(previous_size+1));
for (i=0;i<previous_size+1;i++) {
if (i==0 || i == previous_size) {
retval[i] = 1;
} else {
retval[i] = previous_row[i-1] + previous_row[i];
}
}
return retval;
}
void print_row(int64_t* row, int64_t size)
{
int64_t i;
for(i = 0; i < size; i++) {
printf("%lld ",row[i]);
}
printf("\n");
}
int main()
{
int64_t* first_row;
int64_t* previous_row;
int64_t* next_row;
int64_t i,size;
first_row = (int64_t*)malloc(sizeof(int64_t));
first_row[0] = 1;
size = 1;
print_row(first_row,size);
previous_row = first_row;
for(i = 0; i<31;i++) {
next_row = next_pascal_row(previous_row,size);
size++;
print_row(next_row,size);
free(previous_row);
previous_row = next_row;
}
free(next_row);
return 0;
}Solution
Looks pretty good to me. If I were doing this for an interview question, I would take on the challenge of implementing it recursively. Here are some minor changes I would make:
-
You are hard-coding your for loop to 31 iterations. That ought to be a
-
You are using
-
Your variables
-
In regards to the memory management, all of the allocing and freeing is expensive and slow. If you wanted to minimize that, you should alloc 2 rows of max length up front and then ping-pong them as previous/next rows.
-
In your
-
There is no need for a
-
You are hard-coding your for loop to 31 iterations. That ought to be a
const uint32_t num_iterations = 31; at the top of your code. That makes it more clear to future users what to change if they want a different number of iterations.-
You are using
int64_t. These are all going to be positive numbers, so uint64_t is more appropriate.-
Your variables
i and size are int64_t. But your values are going to overflow 64-bits well before the line they are on gets that big. I'm guessing that uint32_t is enough.-
In regards to the memory management, all of the allocing and freeing is expensive and slow. If you wanted to minimize that, you should alloc 2 rows of max length up front and then ping-pong them as previous/next rows.
-
In your
next_pascal_row routine, you're using an array pointer called retval. I see that name way overused. It would be better called this_row or next_row.-
There is no need for a
first_row pointer. Just use the previous_row pointer in initialization.Context
StackExchange Code Review Q#7504, answer score: 6
Revisions (0)
No revisions yet.