65 lines
1.3 KiB
Text
65 lines
1.3 KiB
Text
MODULE CatalanNumbers;
|
|
FROM FormatString IMPORT FormatString;
|
|
FROM Terminal IMPORT WriteString,WriteLn,ReadChar;
|
|
|
|
PROCEDURE binomial(m,n : LONGCARD) : LONGCARD;
|
|
VAR r,d : LONGCARD;
|
|
BEGIN
|
|
r := 1;
|
|
d := m - n;
|
|
IF d>n THEN
|
|
n := d;
|
|
d := m - n;
|
|
END;
|
|
WHILE m>n DO
|
|
r := r * m;
|
|
DEC(m);
|
|
WHILE (d>1) AND NOT (r MOD d # 0) DO
|
|
r := r DIV d;
|
|
DEC(d)
|
|
END
|
|
END;
|
|
RETURN r
|
|
END binomial;
|
|
|
|
PROCEDURE catalan1(n : LONGCARD) : LONGCARD;
|
|
BEGIN
|
|
RETURN binomial(2*n,n) DIV (1+n)
|
|
END catalan1;
|
|
|
|
PROCEDURE catalan2(n : LONGCARD) : LONGCARD;
|
|
VAR i,sum : LONGCARD;
|
|
BEGIN
|
|
IF n>1 THEN
|
|
sum := 0;
|
|
FOR i:=0 TO n-1 DO
|
|
sum := sum + catalan2(i) * catalan2(n - 1 - i)
|
|
END;
|
|
RETURN sum
|
|
ELSE
|
|
RETURN 1
|
|
END
|
|
END catalan2;
|
|
|
|
PROCEDURE catalan3(n : LONGCARD) : LONGCARD;
|
|
BEGIN
|
|
IF n#0 THEN
|
|
RETURN 2 *(2 * n - 1) * catalan3(n - 1) DIV (1 + n)
|
|
ELSE
|
|
RETURN 1
|
|
END
|
|
END catalan3;
|
|
|
|
VAR
|
|
blah : LONGCARD = 123;
|
|
buf : ARRAY[0..63] OF CHAR;
|
|
i : LONGCARD;
|
|
BEGIN
|
|
FormatString("\tdirect\tsumming\tfrac\n", buf);
|
|
WriteString(buf);
|
|
FOR i:=0 TO 15 DO
|
|
FormatString("%u\t%u\t%u\t%u\n", buf, i, catalan1(i), catalan2(i), catalan3(i));
|
|
WriteString(buf)
|
|
END;
|
|
ReadChar
|
|
END CatalanNumbers.
|