Archived

This topic is now archived and is closed to further replies.

nicoloco

Pasacal's triangle

Recommended Posts

nicoloco    122
HI i need a function that generates the pascal''s triangle. the triangle has to look like this 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 thanks very much nico

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
This wreaks of a homework problem about recursion.

Mabey you should ask a classmate.

Okay, Okay..

You''ll need a linked list, and a procedure to be called recursively, given a pointer to the list as an argument, and probably what tier of the triangle you''re on as the second arg.

Your recursion should stop when you''ve reach some predetermined tier number N.

Start with that.



Share this post


Link to post
Share on other sites
Beer Hunter    712
This does seem like a classroom question. And something tells me you are using pascal. But linked lists... recursion... way too much for a simple question. The following is tested code.

procedure PascalTri(rows: integer);
type
ilist = array[0..0] of integer;
iptr = ^ilist;
var
ibuf: iptr;
x, n, row, col: integer;
f: text;
begin
if rows <= 0 then exit;
GetMem(ibuf, (rows+1)*sizeof(integer));
Assign(f, ''pascal.txt'');
Rewrite(f);
ibuf^[0] := 1;
for x := 1 to rows do ibuf^[x] := 0;
WriteLn(f, 1: 4);
if rows > 1 then
for row := 1 to rows - 1 do
begin
Write(f, 1: 4);
x := 1;
for col := 0 to row - 1 do
begin
n := ibuf^[col] + ibuf^[col+1];
ibuf^[col] := x;
x := n;
Write(f, x: 4);
end;
ibuf^[row] := 1;
WriteLn(f);
end;
Close(f);
FreeMem(ibuf, (rows+1)*sizeof(integer));
end;

Share this post


Link to post
Share on other sites
MrSandman666    122
I happen to be in his class and I have to clarify some things here. We''re using C++ and we''re still pretty much beginners (most of us), so - officially - we don''t know anything about pointers or recursion.
I will post my function for this here, as quite a few people seem to have problems with this.
To explain for non-APComputer students: the apvector class is just a luxury array class, that prevents array overflow and can be resized dynamically. In all the other aspects it behaves exactly like a standard array.
So here it is:
  
void PascalTriangle(apvector<int> &tr, int n)
{
apvector<int> a(n), b(n);
int x;

a.resize(2);
b.resize(a.length() + 1);

a[0] = a[1] = 1;

for(int i = 0; i < n; i++)
{
a.resize(i);
b.resize(a.length() + 1);

if(i == 0)
b[0] = 1;

else if(i == 1)
b[0] = b[1] = 1;

else
{
for(x = 0; x < a.length(); x++)
a[x] = b[x];

for(x = 0; x < b.length(); x++)
{
if(x == 0)
b[x] = 1;
else if(x == a.length())
b[x] = 1;
else
b[x] = a[x-1] + a[x];
}
}


for(x = 0; x < n - i; x++)
cout << '' '';

for(x = 0; x < b.length(); x++)
cout << b[x] << '' '';

cout << endl;

}
}


Have fun with it.

"Mr Sandman bring me a dream"

Share this post


Link to post
Share on other sites
Beer Hunter    712
Well, here's the c++ version of the same function. But I'm still going to use pointers, as they are still more efficient and everything. It shouldn't be much work to edit this to use the class you mentioned. The one you demonstrated uses a lot of time for reallocating memory - this one doesn't.

(tested under BCB. Needed to #include <stdio.h>
    
void PascalTri(int rows)
{
int *ibuf = (int*)malloc((rows+1)*sizeof(int));
int x, n, row, col;
FILE *f;
if(rows <= 0) return;
f = fopen("pascal.txt", "w");
ibuf[0] = 1;
for(x = 1; x <= rows; x++) ibuf[x] = 0;
fprintf(f, "%4i\n", 1);
if(rows > 1)
for(row = 1; row < rows; row++)
{
fprintf(f, "%4i", 1);
x = 1;
for(col = 0; col < row; col++)
{
n = ibuf[col] + ibuf[col+1];
ibuf[col] = x;
x = n;
fprintf(f, "%4i", x);
}
ibuf[row] = 1;
fprintf(f, "\n");
}
fclose(f);
free(ibuf);
}


EDIT: note to self - use &lt; and &gt; for < and >

Edited by - Beer Hunter on February 1, 2001 4:37:24 PM

Share this post


Link to post
Share on other sites