Catalan numbers: Difference between revisions
Added Algol 68
m (→version 1: added/changed comments, indentations, and whitespace.) |
(Added Algol 68) |
||
Line 106:
14 = 2674440
15 = 9694845
</pre>
=={{header|ALGOL 68}}==
<lang algol68># calculate the first few catalan numbers, using LONG INT values #
# (64-bit quantities in Algol 68G which can handle up to C23) #
# returns n!/k! #
PROC factorial over factorial = ( INT n, k )LONG INT:
IF k > n THEN 0
ELIF k = n THEN 1
ELSE # k < n #
LONG INT f := 1;
FOR i FROM k + 1 TO n DO f *:= i OD;
f
FI # factorial over factorial # ;
# returns n! #
PROC factorial = ( INT n )LONG INT:
BEGIN
LONG INT f := 1;
FOR i FROM 2 TO n DO f *:= i OD;
f
END # factorial # ;
# returnss the nth Catalan number using binomial coefficeients #
# uses the factorial over factorial procedure for a slight optimisation #
# note: Cn = 1/(n+1)(2n n) #
# = (2n)!/((n+1)!n!) #
# = factorial over factorial( 2n, n+1 )/n! #
PROC catalan = ( INT n )LONG INT: IF n < 2 THEN 1 ELSE factorial over factorial( n + n, n + 1 ) OVER factorial( n ) FI;
# show the first few catalan numbers #
FOR i FROM 0 TO 15 DO
print( ( whole( i, -2 ), ": ", whole( catalan( i ), 0 ), newline ) )
OD</lang>
{{out}}
<pre>
0: 1
1: 1
2: 2
3: 5
4: 14
5: 42
6: 132
7: 429
8: 1430
9: 4862
10: 16796
11: 58786
12: 208012
13: 742900
14: 2674440
15: 9694845
</pre>
| |||