Catalan numbers: Difference between revisions
Content added Content deleted
m (→version 1: added/changed comments, indentations, and whitespace.) |
(Added Algol 68) |
||
Line 106: | Line 106: | ||
14 = 2674440 |
14 = 2674440 |
||
15 = 9694845 |
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> |
</pre> |
||