Catalan numbers: Difference between revisions

Content added Content deleted
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 botLO topHI . /*get optional arguments from the C.L. */
if botLO=='' | LO=="," then do; top HI=15; botLO=0; end /*No args? Use a range of 0 ───► 15. */
if topHI=='' then| topHI==bot"," then HI=LO /*No topHI? Use the bottom LO for default. */
numeric digits max(20, 5*topHI) /*this allows gihugic Catalan numbers. */
@cat=' Catalan' /*a nice literal to have for the SAY. */
w=length(topHI) /*width of the largest number for SAY. */
call hdr 1A; do j=botLO to topHI; say @cat right(j, w)": " Catalan1A(j); end
call hdr 1B; do j=botLO to topHI; say @cat right(j, w)": " Catalan1B(j); end
call hdr 2 ; do j=botLO to topHI; say @cat right(j, w)": " Catalan2(j); end
call hdr 3 ; do j=botLO to topHI; say @cat right(j, w)": " Catalan3(j); end
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; parse arg x,y; parse arg x,y; return pFact(x-y+1,x) % pFact(2,y)
pFact: procedure; !=1; do k=arg(1) to arg(2); !=!*k; end; return !
/*──────────────────────────────────────────────────────────────────────────────────────*/
/*────────────────────────────────────────────────────────────────────────────*/
hdr!: procedure expose !.=.; parse arg cx; if !.x\==.; then return c!.0=1x; say!=1
do k=12 for x; !=!*k; end /*k*/▼
say center(' Catalan numbers, method' left(arg(1),3), 79, '─'); return▼
!.x=!; return !▼
/*────────────────────────────────────────────────────────────────────────────*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
!: procedure expose !.; parse arg x; !=1; if !.x\==. then return !.x
▲ do k=1 for x; !=!*k; end /*k*/
▲ !.x=!; return !
/*──────────────────────────────────Catalan method 2──────────────────────────*/
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); end
c.n=$; return $ c.n=$; return $ /*use a REXX memoization technique. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
/*──────────────────────────────────Catalan method 3──────────────────────────*/
Catalan3: procedure expose c.; parse arg n
if c.n==. then c.n=(4*n-2) * catalan3(n-1) % (n+1); return c.n</lang>
return c.n
/*──────────────────────────────────────────────────────────────────────────────────────*/
hdr: !.=.; c.=.; c.0=1; say
▲ say center(' Catalan numbers, method' left(arg(1),3), 79, '─'); return</lang>
'''output''' &nbsp; when using the input of: &nbsp; <tt> 0 &nbsp; 16 </tt>
<pre>
Retrieved from "https://rosettacode.org/wiki/Catalan_numbers"