Anonymous user
Catalan numbers: Difference between revisions
m
→{{header|REXX}}: added another version of the first equation, pruned identical outputs.
m (→{{header|Perl 6}}: sign) |
m (→{{header|REXX}}: added another version of the first equation, pruned identical outputs.) |
||
Line 2,340:
=={{header|REXX}}==
All methods use memoization for the computation of factorials.
<lang rexx>/*REXX program calculates Catalan numbers using
parse arg bot top . /*get args from the command line.*/
if bot=='' then do; top=15; bot=0; end /*No args? Use a range of
if top=='' then top=bot /*No top? Use the bottom for it.*/
numeric digits max(20,5*top) /*no limit on big Catalan numbers*/
!.=.; w=length(top)
say; say center(' Catalan numbers, method
say right(
end /*
say; say center(' Catalan numbers, method
say right(
end /*m1b*/
say; say center(' Catalan numbers, method 2 ' , 79, '─')
!.=.; c.=.; c.0=1; do m2=bot to top
say right(m2,w) '=' catalan2(m2)
end /*m2*/
say; say center(' Catalan numbers, method 3 ' , 79, '
!.=.; c.=.;
say right(m3,w) '=' catalan3(m3)
end /*m3*/
exit /*stick a fork in it, we're done.*/
▲/*──────────────────────────────────catalan method 1────────────────────*/
▲catalan1: procedure expose !.; parse arg n /*n+n is faster than 2*n */
return !(n+n) % ( (n+1) * !(n)**2 ) /*using COMB would be faster*/
/*──────────────────────────────────catalan method 1b───────────────────*/
catalan1b: procedure expose !.; parse arg n
return comb(n+n,n)%(n+1) /*use COMB (binomial) function.*/
/*──────────────────────────────────catalan method 2────────────────────*/
catalan2: procedure expose c.; parse arg n; if c.n\==
s=0; do j=0 to n-1
s=s + catalan2(j) * catalan2(n-j-1) /*recursive invokes.*/
Line 2,375 ⟶ 2,381:
c.n=s /*use REXX memoization technique.*/
return s
/*──────────────────────────────────catalan method 3────────────────────*/
catalan3: procedure expose c.; parse arg n; if c.n\==
c.n=(4*n-2) * catalan3(n-1) % (n+1) /*use REXX memoization technique.*/
return c.n
/*──────────────────────────────────! (factorial) function──────────────*/
!: procedure expose !.; parse arg x; if !.x\==
do k=1 for x
!=!*k
end /*k*/
!.x=! /*use REXX memoization technique.*/
return !
/*──────────────────────────────────COMB subroutine─────────────────────*/
'''output''' when using the input of: <tt> 0 16 </tt>▼
comb: procedure; parse arg x,y; return pFact(x-y+1,x) % pFact(2,y)
/*──────────────────────────────────PFACT subroutine────────────────────*/
pFact: procedure; !=1; do j=arg(1) to arg(2); !=!*j; end; return !</lang>
▲'''output''' when using the input of: <tt> 0 16 </tt>
<pre>
───────────────────────── Catalan numbers, method 1a ──────────────────────────
1 = 1
2 = 2
Line 2,409 ⟶ 2,416:
16 = 35357670
───────────────────────── Catalan numbers, method 1b ──────────────────────────
... (elided, same as first version) ...
───────────────────────── Catalan numbers, method 2 ──────────────────────────
... (elided, same as first version) ...
───────────────────────── Catalan numbers, method 3 ──────────────────────────
... (elided, same as first version) ...
</pre>
| |||