Anonymous user
Catalan numbers: Difference between revisions
m
→version 1: added/changed comments, indentations, and whitespace.
m (shown the formulas in larger fonts to be easier to read the italics and subscripts, add a Task (bold) header.) |
m (→version 1: added/changed comments, indentations, and whitespace.) |
||
Line 3,014:
===version 1===
All methods use (independent) memoization for the computation of factorials.
<lang rexx>/*REXX program calculates Catalan numbers using four different methods. */
parse arg
if
if
numeric digits max(20, 5*
@cat=' Catalan' /*a nice literal to have for the SAY. */
w=length(
call hdr 1A; do j=
call hdr 1B; do j=
call hdr 2 ; do j=
call hdr 3 ; do j=
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
Catalan1A: procedure expose !.; parse arg n; return comb(n+n, n) % (n+1)
Catalan1B: procedure expose !.; parse arg n; return !(n+n) % ((n+1) * !(n)**2)
comb: procedure;
pFact: procedure; !=1; do k=arg(1) to arg(2); !=!*k; end;
/*──────────────────────────────────────────────────────────────────────────────────────*/
say center(' Catalan numbers, method' left(arg(1),3), 79, '─'); return▼
!.x=!; return !▼
/*──────────────────────────────────────────────────────────────────────────────────────*/
▲ do k=1 for x; !=!*k; end /*k*/
▲ !.x=!; return !
Catalan2: procedure expose c.; parse arg n; $=0; if c.n\==. then return c.n
do k=0 to n-1; $=$+catalan2(k)*catalan2(n-k-1);
/*──────────────────────────────────────────────────────────────────────────────────────*/
Catalan3: procedure expose c.;
if c.n==. then c.n=(4*n-2) * catalan3(n-1) % (n+1)
return c.n
/*──────────────────────────────────────────────────────────────────────────────────────*/
hdr: !.=.; c.=.; c.0=1; say
▲ say center(' Catalan numbers, method' left(arg(1),3), 79, '─'); return</lang>
'''output''' when using the input of: <tt> 0 16 </tt>
<pre>
|