Catalan numbers/Pascal's triangle: Difference between revisions
Content added Content deleted
(→{{header|F#}}: Corrected header as suggested on the Count examples/Full list/Tier 4 talk page) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 17: | Line 17: | ||
=={{header|11l}}== |
=={{header|11l}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang=11l>V n = 15 |
||
V t = [0] * (n + 2) |
V t = [0] * (n + 2) |
||
t[1] = 1 |
t[1] = 1 |
||
Line 26: | Line 26: | ||
L(j) (i + 1 .< 1).step(-1) |
L(j) (i + 1 .< 1).step(-1) |
||
t[j] += t[j - 1] |
t[j] += t[j - 1] |
||
print(t[i + 1] - t[i], end' ‘ ’)</ |
print(t[i + 1] - t[i], end' ‘ ’)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 34: | Line 34: | ||
=={{header|360 Assembly}}== |
=={{header|360 Assembly}}== |
||
For maximum compatibility, this program uses only the basic instruction set. |
For maximum compatibility, this program uses only the basic instruction set. |
||
< |
<syntaxhighlight lang=360asm>CATALAN CSECT |
||
USING CATALAN,R13,R12 |
USING CATALAN,R13,R12 |
||
SAVEAREA B STM-SAVEAREA(R15) |
SAVEAREA B STM-SAVEAREA(R15) |
||
Line 124: | Line 124: | ||
WTOBUF DC CL80' ' |
WTOBUF DC CL80' ' |
||
YREGS |
YREGS |
||
END</ |
END</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre style="height:20ex">00000001 |
<pre style="height:20ex">00000001 |
||
Line 144: | Line 144: | ||
=={{header|Action!}}== |
=={{header|Action!}}== |
||
{{libheader|Action! Tool Kit}} |
{{libheader|Action! Tool Kit}} |
||
< |
<syntaxhighlight lang=Action!>INCLUDE "D2:REAL.ACT" ;from the Action! Tool Ki |
||
DEFINE PTR="CARD" |
DEFINE PTR="CARD" |
||
Line 191: | Line 191: | ||
PrintF("C(%B)=",i) PrintRE(c) |
PrintF("C(%B)=",i) PrintRE(c) |
||
OD |
OD |
||
RETURN</ |
RETURN</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Catalan_numbers_Pascal's_triangle.png Screenshot from Atari 8-bit computer] |
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Catalan_numbers_Pascal's_triangle.png Screenshot from Atari 8-bit computer] |
||
Line 216: | Line 216: | ||
Uses package Pascal from the Pascal triangle solution[[http://rosettacode.org/wiki/Pascal%27s_triangle#Ada]] |
Uses package Pascal from the Pascal triangle solution[[http://rosettacode.org/wiki/Pascal%27s_triangle#Ada]] |
||
< |
<syntaxhighlight lang=Ada>with Ada.Text_IO, Pascal; |
||
procedure Catalan is |
procedure Catalan is |
||
Line 229: | Line 229: | ||
Ada.Text_IO.Put(Integer'Image(Row(I+1)-Row(I+2))); |
Ada.Text_IO.Put(Integer'Image(Row(I+1)-Row(I+2))); |
||
end loop; |
end loop; |
||
end Catalan;</ |
end Catalan;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 237: | Line 237: | ||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<syntaxhighlight lang=algol68>INT n = 15; |
||
[ 0 : n + 1 ]INT t; |
[ 0 : n + 1 ]INT t; |
||
t[0] := 0; |
t[0] := 0; |
||
Line 246: | Line 246: | ||
FOR j FROM i+1 BY -1 TO 2 DO t[j] := t[j] + t[j-1] OD; |
FOR j FROM i+1 BY -1 TO 2 DO t[j] := t[j] + t[j-1] OD; |
||
print( ( whole( t[i+1] - t[i], 0 ), " " ) ) |
print( ( whole( t[i+1] - t[i], 0 ), " " ) ) |
||
OD</ |
OD</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 253: | Line 253: | ||
=={{header|ALGOL W}}== |
=={{header|ALGOL W}}== |
||
< |
<syntaxhighlight lang=algolw>begin |
||
% print the first 15 Catalan numbers from Pascal's triangle % |
% print the first 15 Catalan numbers from Pascal's triangle % |
||
integer n; |
integer n; |
||
Line 272: | Line 272: | ||
end for_c |
end for_c |
||
end |
end |
||
end.</ |
end.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 279: | Line 279: | ||
=={{header|APL}}== |
=={{header|APL}}== |
||
< |
<syntaxhighlight lang=apl> |
||
⍝ Based heavily on the J solution |
⍝ Based heavily on the J solution |
||
CATALAN←{¯1↓↑-/1 ¯1↓¨(⊂⎕IO+0 0)⍉¨0 2⌽¨⊂(⎕IO-⍨⍳N){+\⍣⍺⊢⍵}⍤0 1⊢1⍴⍨N←⍵+2} |
CATALAN←{¯1↓↑-/1 ¯1↓¨(⊂⎕IO+0 0)⍉¨0 2⌽¨⊂(⎕IO-⍨⍳N){+\⍣⍺⊢⍵}⍤0 1⊢1⍴⍨N←⍵+2} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 291: | Line 291: | ||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
{{works with|AutoHotkey_L}} |
{{works with|AutoHotkey_L}} |
||
< |
<syntaxhighlight lang=AutoHotkey>/* Generate Catalan Numbers |
||
// |
// |
||
// smgs: 20th Feb, 2014 |
// smgs: 20th Feb, 2014 |
||
Line 320: | Line 320: | ||
} |
} |
||
} |
} |
||
MsgBox % result</ |
MsgBox % result</syntaxhighlight> |
||
{{out|Produces}} |
{{out|Produces}} |
||
<pre> |
<pre> |
||
Line 327: | Line 327: | ||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
< |
<syntaxhighlight lang=AWK> |
||
# syntax: GAWK -f CATALAN_NUMBERS_PASCALS_TRIANGLE.AWK |
# syntax: GAWK -f CATALAN_NUMBERS_PASCALS_TRIANGLE.AWK |
||
# converted from C |
# converted from C |
||
Line 344: | Line 344: | ||
exit(0) |
exit(0) |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 351: | Line 351: | ||
=={{header|Batch File}}== |
=={{header|Batch File}}== |
||
< |
<syntaxhighlight lang=dos>@echo off |
||
setlocal ENABLEDELAYEDEXPANSION |
setlocal ENABLEDELAYEDEXPANSION |
||
set n=15 |
set n=15 |
||
Line 372: | Line 372: | ||
) |
) |
||
) |
) |
||
pause</ |
pause</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre style="height:20ex">1 |
<pre style="height:20ex">1 |
||
Line 391: | Line 391: | ||
=={{header|C}}== |
=={{header|C}}== |
||
<syntaxhighlight lang=c> |
|||
<lang c> |
|||
//This code implements the print of 15 first Catalan's Numbers |
//This code implements the print of 15 first Catalan's Numbers |
||
//Formula used: |
//Formula used: |
||
Line 437: | Line 437: | ||
return 0; |
return 0; |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 446: | Line 446: | ||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |
||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<syntaxhighlight lang=csharp> |
||
int n = 15; |
int n = 15; |
||
List<int> t = new List<int>() { 0, 1 }; |
List<int> t = new List<int>() { 0, 1 }; |
||
Line 456: | Line 456: | ||
Console.Write(((i == 1) ? "" : ", ") + (t[i + 1] - t[i])); |
Console.Write(((i == 1) ? "" : ", ") + (t[i + 1] - t[i])); |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out|Produces}} |
{{out|Produces}} |
||
<pre> |
<pre> |
||
Line 463: | Line 463: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
< |
<syntaxhighlight lang=cpp>// Generate Catalan Numbers |
||
// |
// |
||
// Nigel Galloway: June 9th., 2012 |
// Nigel Galloway: June 9th., 2012 |
||
Line 478: | Line 478: | ||
} |
} |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out|Produces}} |
{{out|Produces}} |
||
<pre> |
<pre> |
||
Line 486: | Line 486: | ||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||
< |
<syntaxhighlight lang=Lisp>(defun catalan (n) |
||
"Return the n-th Catalan number" |
"Return the n-th Catalan number" |
||
(if (<= n 1) 1 |
(if (<= n 1) 1 |
||
Line 495: | Line 495: | ||
(dotimes (n 15) |
(dotimes (n 15) |
||
(print (catalan (1+ n))) )</ |
(print (catalan (1+ n))) )</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 517: | Line 517: | ||
=={{header|D}}== |
=={{header|D}}== |
||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<syntaxhighlight lang=d>void main() { |
||
import std.stdio; |
import std.stdio; |
||
Line 532: | Line 532: | ||
write(t[i + 1] - t[i], ' '); |
write(t[i + 1] - t[i], ' '); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 </pre> |
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 </pre> |
||
Line 538: | Line 538: | ||
See [https://rosettacode.org/wiki/Catalan_numbers/Pascal%27s_triangle#Pascal Pascal]. |
See [https://rosettacode.org/wiki/Catalan_numbers/Pascal%27s_triangle#Pascal Pascal]. |
||
=={{header|EchoLisp}}== |
=={{header|EchoLisp}}== |
||
< |
<syntaxhighlight lang=scheme> |
||
(define dim 100) |
(define dim 100) |
||
(define-syntax-rule (Tidx i j) (+ i (* dim j))) |
(define-syntax-rule (Tidx i j) (+ i (* dim j))) |
||
Line 554: | Line 554: | ||
(remember 'T #(1)) |
(remember 'T #(1)) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
< |
<syntaxhighlight lang=scheme> |
||
;; take elements on diagonal = Catalan numbers |
;; take elements on diagonal = Catalan numbers |
||
(for ((i (in-range 0 16))) (write (T (Tidx i i)))) |
(for ((i (in-range 0 16))) (write (T (Tidx i i)))) |
||
→ 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
→ 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|EDSAC order code}}== |
=={{header|EDSAC order code}}== |
||
Rather than store a triangular array, this solution stores the right-hand half of the current row and updates it in place. It uses the third method in the link, e.g. once we have the half row (70, 56, 28, 8, 1), the Catalan number 42 appears as 70 - 28. |
Rather than store a triangular array, this solution stores the right-hand half of the current row and updates it in place. It uses the third method in the link, e.g. once we have the half row (70, 56, 28, 8, 1), the Catalan number 42 appears as 70 - 28. |
||
< |
<syntaxhighlight lang=edsac> |
||
[Catalan numbers from Pascal triangle, Rosetta Code website. |
[Catalan numbers from Pascal triangle, Rosetta Code website. |
||
EDSAC program, Initial Orders 2] |
EDSAC program, Initial Orders 2] |
||
Line 625: | Line 625: | ||
[75] O4@ ZF [flush printer buffer; stop] |
[75] O4@ ZF [flush printer buffer; stop] |
||
E9Z PF [define entry point; enter with acc = 0] |
E9Z PF [define entry point; enter with acc = 0] |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 646: | Line 646: | ||
=={{header|Elixir}}== |
=={{header|Elixir}}== |
||
< |
<syntaxhighlight lang=elixir>defmodule Catalan do |
||
def numbers(num) do |
def numbers(num) do |
||
{result,_} = Enum.reduce(1..num, {[],{0,1}}, fn i,{list,t0} -> |
{result,_} = Enum.reduce(1..num, {[],{0,1}}, fn i,{list,t0} -> |
||
Line 660: | Line 660: | ||
end |
end |
||
IO.inspect Catalan.numbers(15)</ |
IO.inspect Catalan.numbers(15)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 668: | Line 668: | ||
=={{header|Erlang}}== |
=={{header|Erlang}}== |
||
< |
<syntaxhighlight lang=erlang> |
||
-module(catalin). |
-module(catalin). |
||
-compile(export_all). |
-compile(export_all). |
||
Line 686: | Line 686: | ||
main()-> |
main()-> |
||
Ans=catl(1,2). |
Ans=catl(1,2). |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|ERRE}}== |
=={{header|ERRE}}== |
||
< |
<syntaxhighlight lang=ERRE> |
||
PROGRAM CATALAN |
PROGRAM CATALAN |
||
Line 728: | Line 728: | ||
END FOR |
END FOR |
||
END PROGRAM |
END PROGRAM |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 749: | Line 749: | ||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
< |
<syntaxhighlight lang=fsharp> |
||
let mutable nm=uint64(1) |
let mutable nm=uint64(1) |
||
let mutable dm=uint64(1) |
let mutable dm=uint64(1) |
||
Line 765: | Line 765: | ||
if(i<>15) then |
if(i<>15) then |
||
printf ", " |
printf ", " |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
< |
<syntaxhighlight lang=factor>USING: arrays grouping io kernel math prettyprint sequences ; |
||
IN: rosetta-code.catalan-pascal |
IN: rosetta-code.catalan-pascal |
||
Line 781: | Line 781: | ||
[ dup midpoint@ dup 1 + 2array swap nths first2 - ] if |
[ dup midpoint@ dup 1 + 2array swap nths first2 - ] if |
||
pprint bl |
pprint bl |
||
] each drop</ |
] each drop</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 788: | Line 788: | ||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
< |
<syntaxhighlight lang=freebasic>' version 15-09-2015 |
||
' compile with: fbc -s console |
' compile with: fbc -s console |
||
Line 843: | Line 843: | ||
Print : Print "hit any key to end program" |
Print : Print "hit any key to end program" |
||
Sleep |
Sleep |
||
End</ |
End</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>The first 15 Catalan numbers are |
<pre>The first 15 Catalan numbers are |
||
Line 865: | Line 865: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<syntaxhighlight lang=go>package main |
||
import "fmt" |
import "fmt" |
||
Line 882: | Line 882: | ||
fmt.Printf("%2d : %d\n", i, t[i+1]-t[i]) |
fmt.Printf("%2d : %d\n", i, t[i+1]-t[i]) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 905: | Line 905: | ||
=={{header|Groovy}}== |
=={{header|Groovy}}== |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang=Groovy> |
||
class Catalan |
class Catalan |
||
{ |
{ |
||
Line 929: | Line 929: | ||
} |
} |
||
} |
} |
||
</ |
</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 938: | Line 938: | ||
As required by the task this implementation extracts the Catalan numbers from Pascal's triangle, rather |
As required by the task this implementation extracts the Catalan numbers from Pascal's triangle, rather |
||
than calculating them directly. Also, note that it (correctly) produces [1, 1] as the first two numbers. |
than calculating them directly. Also, note that it (correctly) produces [1, 1] as the first two numbers. |
||
< |
<syntaxhighlight lang=haskell>import System.Environment (getArgs) |
||
-- Pascal's triangle. |
-- Pascal's triangle. |
||
Line 956: | Line 956: | ||
main = do |
main = do |
||
ns <- fmap (map read) getArgs :: IO [Int] |
ns <- fmap (map read) getArgs :: IO [Int] |
||
mapM_ (print . flip take catalan) ns</ |
mapM_ (print . flip take catalan) ns</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 969: | Line 969: | ||
that aren't used. |
that aren't used. |
||
< |
<syntaxhighlight lang=unicon>link math |
||
procedure main(A) |
procedure main(A) |
||
limit := (integer(A[1])|15)+1 |
limit := (integer(A[1])|15)+1 |
||
every write(right(binocoef(i := 2*seq(0)\limit,i/2)-binocoef(i,i/2+1),30)) |
every write(right(binocoef(i := 2*seq(0)\limit,i/2)-binocoef(i,i/2+1),30)) |
||
end</ |
end</syntaxhighlight> |
||
Sample run: |
Sample run: |
||
Line 999: | Line 999: | ||
=={{header|J}}== |
=={{header|J}}== |
||
< |
<syntaxhighlight lang=j> Catalan=. }:@:(}.@:((<0 1)&|:) - }:@:((<0 1)&|:@:(2&|.)))@:(i. +/\@]^:[ #&1)@:(2&+)</syntaxhighlight> |
||
{{out|Example use}} |
{{out|Example use}} |
||
< |
<syntaxhighlight lang=j> Catalan 15 |
||
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
||
</ |
</syntaxhighlight> |
||
A structured derivation of Catalan follows: |
A structured derivation of Catalan follows: |
||
< |
<syntaxhighlight lang=j> o=. @: NB. Composition of verbs (functions) |
||
( PascalTriangle=. i. ((+/\@]^:[)) #&1 ) 5 |
( PascalTriangle=. i. ((+/\@]^:[)) #&1 ) 5 |
||
1 1 1 1 1 |
1 1 1 1 1 |
||
Line 1,023: | Line 1,023: | ||
Catalan |
Catalan |
||
}:@:(}.@:((<0 1)&|:) - }:@:((<0 1)&|:@:(2&|.)))@:(i. +/\@]^:[ #&1)@:(2&+)</ |
}:@:(}.@:((<0 1)&|:) - }:@:((<0 1)&|:@:(2&|.)))@:(i. +/\@]^:[ #&1)@:(2&+)</syntaxhighlight> |
||
=={{header|Java}}== |
=={{header|Java}}== |
||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<syntaxhighlight lang=java>public class Test { |
||
public static void main(String[] args) { |
public static void main(String[] args) { |
||
int N = 15; |
int N = 15; |
||
Line 1,046: | Line 1,046: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre> |
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre> |
||
Line 1,054: | Line 1,054: | ||
Iteration |
Iteration |
||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<syntaxhighlight lang=javascript>var n = 15; |
||
for (var t = [0, 1], i = 1; i <= n; i++) { |
for (var t = [0, 1], i = 1; i <= n; i++) { |
||
for (var j = i; j > 1; j--) t[j] += t[j - 1]; |
for (var j = i; j > 1; j--) t[j] += t[j - 1]; |
||
Line 1,060: | Line 1,060: | ||
for (var j = i + 1; j > 1; j--) t[j] += t[j - 1]; |
for (var j = i + 1; j > 1; j--) t[j] += t[j - 1]; |
||
document.write(i == 1 ? '' : ', ', t[i + 1] - t[i]); |
document.write(i == 1 ? '' : ', ', t[i + 1] - t[i]); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,070: | Line 1,070: | ||
{{Trans|Haskell}} |
{{Trans|Haskell}} |
||
< |
<syntaxhighlight lang=JavaScript>(() => { |
||
'use strict'; |
'use strict'; |
||
Line 1,133: | Line 1,133: | ||
return tail(catalanSeries(16)); |
return tail(catalanSeries(16)); |
||
})();</ |
})();</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
< |
<syntaxhighlight lang=JavaScript>[1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845]</syntaxhighlight> |
||
=={{header|jq}}== |
=={{header|jq}}== |
||
Line 1,143: | Line 1,143: | ||
''Warning'': jq uses IEEE 754 64-bit arithmetic, |
''Warning'': jq uses IEEE 754 64-bit arithmetic, |
||
so the algorithm used here for Catalan numbers loses precision for n > 30 and fails completely for n > 510. |
so the algorithm used here for Catalan numbers loses precision for n > 30 and fails completely for n > 510. |
||
< |
<syntaxhighlight lang=jq>def binomial(n; k): |
||
if k > n / 2 then binomial(n; n-k) |
if k > n / 2 then binomial(n; n-k) |
||
else reduce range(1; k+1) as $i (1; . * (n - $i + 1) / $i) |
else reduce range(1; k+1) as $i (1; . * (n - $i + 1) / $i) |
||
Line 1,149: | Line 1,149: | ||
# Direct (naive) computation using two numbers in Pascal's triangle: |
# Direct (naive) computation using two numbers in Pascal's triangle: |
||
def catalan_by_pascal: . as $n | binomial(2*$n; $n) - binomial(2*$n; $n-1);</ |
def catalan_by_pascal: . as $n | binomial(2*$n; $n) - binomial(2*$n; $n-1);</syntaxhighlight> |
||
'''Example''': |
'''Example''': |
||
(range(0;16), 30, 31, 510, 511) | [., catalan_by_pascal] |
(range(0;16), 30, 31, 510, 511) | [., catalan_by_pascal] |
||
{{Out}} |
{{Out}} |
||
< |
<syntaxhighlight lang=sh>$ jq -n -c -f Catalan_numbers_Pascal.jq |
||
[0,0] |
[0,0] |
||
[1,1] |
[1,1] |
||
Line 1,174: | Line 1,174: | ||
[31,14544636039226880] |
[31,14544636039226880] |
||
[510,5.491717746183512e+302] |
[510,5.491717746183512e+302] |
||
[511,null]</ |
[511,null]</syntaxhighlight> |
||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
{{trans|Matlab}} |
{{trans|Matlab}} |
||
< |
<syntaxhighlight lang=julia># v0.6 |
||
function pascal(n::Int) |
function pascal(n::Int) |
||
Line 1,193: | Line 1,193: | ||
end |
end |
||
@show catalan_num(15)</ |
@show catalan_num(15)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,199: | Line 1,199: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
< |
<syntaxhighlight lang=scala>// version 1.1.2 |
||
import java.math.BigInteger |
import java.math.BigInteger |
||
Line 1,223: | Line 1,223: | ||
val n = 15 |
val n = 15 |
||
catalanFromPascal(n * 2) |
catalanFromPascal(n * 2) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,247: | Line 1,247: | ||
For each line of odd-numbered length from Pascal's triangle, print the middle number minus the one immediately to its right. |
For each line of odd-numbered length from Pascal's triangle, print the middle number minus the one immediately to its right. |
||
This solution is heavily based on the Lua code to generate Pascal's triangle from the page for that task. |
This solution is heavily based on the Lua code to generate Pascal's triangle from the page for that task. |
||
< |
<syntaxhighlight lang=Lua>function nextrow (t) |
||
local ret = {} |
local ret = {} |
||
t[0], t[#t + 1] = 0, 0 |
t[0], t[#t + 1] = 0, 0 |
||
Line 1,263: | Line 1,263: | ||
end |
end |
||
catalans(15)</ |
catalans(15)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440</pre> |
<pre>1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440</pre> |
||
Line 1,277: | Line 1,277: | ||
We use & to pass by reference, here anarray, to sub, but because a sub can see anything in module we can change array name inside sub to same as triangle and we can remove arguments (including size). |
We use & to pass by reference, here anarray, to sub, but because a sub can see anything in module we can change array name inside sub to same as triangle and we can remove arguments (including size). |
||
< |
<syntaxhighlight lang=M2000 Interpreter> |
||
Module CatalanNumbers { |
Module CatalanNumbers { |
||
Def Integer count, t_row, size=31 |
Def Integer count, t_row, size=31 |
||
Line 1,311: | Line 1,311: | ||
} |
} |
||
CatalanNumbers |
CatalanNumbers |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,333: | Line 1,333: | ||
=={{header|Maple}}== |
=={{header|Maple}}== |
||
< |
<syntaxhighlight lang=maple>catalan:=proc(n) |
||
local i,a:=[1],C:=[1]; |
local i,a:=[1],C:=[1]; |
||
for i to n do |
for i to n do |
||
Line 1,344: | Line 1,344: | ||
catalan(10); |
catalan(10); |
||
# [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796]</ |
# [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796]</syntaxhighlight> |
||
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
||
This builds the entire Pascal triangle that's needed and holds it in memory. Very inefficienct, but seems to be what is asked in the problem. |
This builds the entire Pascal triangle that's needed and holds it in memory. Very inefficienct, but seems to be what is asked in the problem. |
||
< |
<syntaxhighlight lang=Mathematica>nextrow[lastrow_] := Module[{output}, |
||
output = ConstantArray[1, Length[lastrow] + 1]; |
output = ConstantArray[1, Length[lastrow] + 1]; |
||
Do[ |
Do[ |
||
Line 1,363: | Line 1,363: | ||
] |
] |
||
(* testing *) |
(* testing *) |
||
catalannumbers[15]</ |
catalannumbers[15]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>{1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845}</pre> |
<pre>{1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845}</pre> |
||
Line 1,369: | Line 1,369: | ||
=={{header|MATLAB}} / {{header|Octave}}== |
=={{header|MATLAB}} / {{header|Octave}}== |
||
< |
<syntaxhighlight lang=MATLAB>n = 15; |
||
p = pascal(n + 2); |
p = pascal(n + 2); |
||
p(n + 4 : n + 3 : end - 1)' - diag(p, 2)</ |
p(n + 4 : n + 3 : end - 1)' - diag(p, 2)</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>ans = |
<pre>ans = |
||
Line 1,392: | Line 1,392: | ||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang=nim>const n = 15 |
||
var t = newSeq[int](n + 2) |
var t = newSeq[int](n + 2) |
||
Line 1,401: | Line 1,401: | ||
for j in countdown(i+1, 1): t[j] += t[j-1] |
for j in countdown(i+1, 1): t[j] += t[j-1] |
||
stdout.write t[i+1] - t[i], " " |
stdout.write t[i+1] - t[i], " " |
||
stdout.write '\n'</ |
stdout.write '\n'</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 </pre> |
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 </pre> |
||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
< |
<syntaxhighlight lang=ocaml> |
||
let catalan : int ref = ref 0 in |
let catalan : int ref = ref 0 in |
||
Printf.printf "%d ," 1 ; |
Printf.printf "%d ," 1 ; |
||
Line 1,419: | Line 1,419: | ||
print_int (!catalan); print_string "," ; |
print_int (!catalan); print_string "," ; |
||
done;; |
done;; |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,428: | Line 1,428: | ||
=={{header|Oforth}}== |
=={{header|Oforth}}== |
||
< |
<syntaxhighlight lang=Oforth>import: mapping |
||
: pascal( n -- [] ) |
: pascal( n -- [] ) |
||
Line 1,434: | Line 1,434: | ||
: catalan( n -- m ) |
: catalan( n -- m ) |
||
n 2 * pascal at( n 1+ ) n 1+ / ;</ |
n 2 * pascal at( n 1+ ) n 1+ / ;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,443: | Line 1,443: | ||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |
||
< |
<syntaxhighlight lang=parigp>vector(15,n,binomial(2*n,n)-binomial(2*n,n+1))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>%1 = [1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]</pre> |
<pre>%1 = [1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]</pre> |
||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||
< |
<syntaxhighlight lang=pascal> |
||
Program CatalanNumbers |
Program CatalanNumbers |
||
type |
type |
||
Line 1,484: | Line 1,484: | ||
For i := 1 to L do |
For i := 1 to L do |
||
Writeln(i:3,Catalan[i]:20); |
Writeln(i:3,Catalan[i]:20); |
||
end.</ |
end.</syntaxhighlight> |
||
<pre> 1 1 |
<pre> 1 1 |
||
2 2 |
2 2 |
||
Line 1,505: | Line 1,505: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<syntaxhighlight lang=Perl>use constant N => 15; |
||
my @t = (0, 1); |
my @t = (0, 1); |
||
for(my $i = 1; $i <= N; $i++) { |
for(my $i = 1; $i <= N; $i++) { |
||
Line 1,512: | Line 1,512: | ||
for(my $j = $i+1; $j>1; $j--) { $t[$j] += $t[$j-1] } |
for(my $j = $i+1; $j>1; $j--) { $t[$j] += $t[$j-1] } |
||
print $t[$i+1] - $t[$i], " "; |
print $t[$i+1] - $t[$i], " "; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre> |
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre> |
||
Line 1,518: | Line 1,518: | ||
After the 28th Catalan number, this overflows 64-bit integers. We could add <tt>use bigint;</tt> <tt>use Math::GMP ":constant";</tt> to make it work, albeit not at a fast pace. However we can use a module to do it much faster: |
After the 28th Catalan number, this overflows 64-bit integers. We could add <tt>use bigint;</tt> <tt>use Math::GMP ":constant";</tt> to make it work, albeit not at a fast pace. However we can use a module to do it much faster: |
||
{{libheader|ntheory}} |
{{libheader|ntheory}} |
||
< |
<syntaxhighlight lang=Perl>use ntheory qw/binomial/; |
||
print join(" ", map { binomial( 2*$_, $_) / ($_+1) } 1 .. 1000), "\n";</ |
print join(" ", map { binomial( 2*$_, $_) / ($_+1) } 1 .. 1000), "\n";</syntaxhighlight> |
||
The <tt>Math::Pari</tt> module also has a binomial, but isn't as fast and overflows its stack after 3400. |
The <tt>Math::Pari</tt> module also has a binomial, but isn't as fast and overflows its stack after 3400. |
||
Line 1,525: | Line 1,525: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Calculates the minimum pascal triangle in minimum memory. Inspired by the comments in, but not the code of the FreeBasic example |
Calculates the minimum pascal triangle in minimum memory. Inspired by the comments in, but not the code of the FreeBasic example |
||
<!--< |
<!--<syntaxhighlight lang=Phix>(phixonline)--> |
||
<span style="color: #008080;">constant</span> <span style="color: #000000;">N</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">15</span> <span style="color: #000080;font-style:italic;">-- accurate to 30, nan/inf for anything over 514 (gmp version is below).</span> |
<span style="color: #008080;">constant</span> <span style="color: #000000;">N</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">15</span> <span style="color: #000080;font-style:italic;">-- accurate to 30, nan/inf for anything over 514 (gmp version is below).</span> |
||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">catalan</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span> <span style="color: #000080;font-style:italic;">-- (>=1 only)</span> |
<span style="color: #004080;">sequence</span> <span style="color: #000000;">catalan</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span> <span style="color: #000080;font-style:italic;">-- (>=1 only)</span> |
||
Line 1,540: | Line 1,540: | ||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
||
<span style="color: #0000FF;">?</span><span style="color: #000000;">catalan</span> |
<span style="color: #0000FF;">?</span><span style="color: #000000;">catalan</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,546: | Line 1,546: | ||
</pre> |
</pre> |
||
Explanatory comments to accompany the above |
Explanatory comments to accompany the above |
||
< |
<syntaxhighlight lang=Phix>-- FreeBASIC said: |
||
--' 1 1 1 1 1 1 |
--' 1 1 1 1 1 1 |
||
--' 1 2 3 4 5 6 |
--' 1 2 3 4 5 6 |
||
Line 1,578: | Line 1,578: | ||
-- 10 15 21 |
-- 10 15 21 |
||
-- 35 56 |
-- 35 56 |
||
-- 126 (unused)</ |
-- 126 (unused)</syntaxhighlight> |
||
=== gmp version === |
=== gmp version === |
||
{{libheader|Phix/mpfr}} |
{{libheader|Phix/mpfr}} |
||
<!--< |
<!--<syntaxhighlight lang=Phix>(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #008080;">include</span> <span style="color: #000000;">builtins</span><span style="color: #0000FF;">\</span><span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
<span style="color: #008080;">include</span> <span style="color: #000000;">builtins</span><span style="color: #0000FF;">\</span><span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
||
Line 1,604: | Line 1,604: | ||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d: %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">100</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">catalanB</span><span style="color: #0000FF;">(</span><span style="color: #000000;">100</span><span style="color: #0000FF;">)))})</span> |
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d: %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">100</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">catalanB</span><span style="color: #0000FF;">(</span><span style="color: #000000;">100</span><span style="color: #0000FF;">)))})</span> |
||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d: %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">250</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">catalanB</span><span style="color: #0000FF;">(</span><span style="color: #000000;">250</span><span style="color: #0000FF;">)))})</span> |
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d: %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">250</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">catalanB</span><span style="color: #0000FF;">(</span><span style="color: #000000;">250</span><span style="color: #0000FF;">)))})</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,619: | Line 1,619: | ||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
< |
<syntaxhighlight lang=PicoLisp>(de bino (N K) |
||
(let f |
(let f |
||
'((N) |
'((N) |
||
Line 1,632: | Line 1,632: | ||
(bino (* 2 N) N) |
(bino (* 2 N) N) |
||
(bino (* 2 N) (inc N)) ) ) ) |
(bino (* 2 N) (inc N)) ) ) ) |
||
(bye)</ |
(bye)</syntaxhighlight> |
||
=={{header|PureBasic}}== |
=={{header|PureBasic}}== |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang=PureBasic>#MAXNUM = 15 |
||
Declare catalan() |
Declare catalan() |
||
Line 1,661: | Line 1,661: | ||
Print(Str(cat)+" ") |
Print(Str(cat)+" ") |
||
Next |
Next |
||
EndProcedure</ |
EndProcedure</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,669: | Line 1,669: | ||
===Procedural=== |
===Procedural=== |
||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<syntaxhighlight lang=python>>>> n = 15 |
||
>>> t = [0] * (n + 2) |
>>> t = [0] * (n + 2) |
||
>>> t[1] = 1 |
>>> t[1] = 1 |
||
Line 1,680: | Line 1,680: | ||
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
||
>>> </ |
>>> </syntaxhighlight> |
||
{{Works with|Python|2.7}} |
{{Works with|Python|2.7}} |
||
< |
<syntaxhighlight lang=python>def catalan_number(n): |
||
nm = dm = 1 |
nm = dm = 1 |
||
for k in range(2, n+1): |
for k in range(2, n+1): |
||
Line 1,691: | Line 1,691: | ||
print [catalan_number(n) for n in range(1, 16)] |
print [catalan_number(n) for n in range(1, 16)] |
||
[1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]</ |
[1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]</syntaxhighlight> |
||
===Composition of pure functions=== |
===Composition of pure functions=== |
||
Line 1,700: | Line 1,700: | ||
{{Trans|Haskell}} |
{{Trans|Haskell}} |
||
{{Works with|Python|3.7}} |
{{Works with|Python|3.7}} |
||
< |
<syntaxhighlight lang=python>'''Catalan numbers from Pascal's triangle''' |
||
from itertools import (islice) |
from itertools import (islice) |
||
Line 1,833: | Line 1,833: | ||
# MAIN --- |
# MAIN --- |
||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
main()</ |
main()</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]</pre> |
<pre>[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]</pre> |
||
Line 1,839: | Line 1,839: | ||
=={{header|Quackery}}== |
=={{header|Quackery}}== |
||
< |
<syntaxhighlight lang=Quackery> [ [] 0 rot 0 join |
||
witheach |
witheach |
||
[ tuck + |
[ tuck + |
||
Line 1,853: | Line 1,853: | ||
drop ] is catalan ( n --> ) |
drop ] is catalan ( n --> ) |
||
15 catalan</ |
15 catalan</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,860: | Line 1,860: | ||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
< |
<syntaxhighlight lang=Racket> |
||
#lang racket |
#lang racket |
||
Line 1,872: | Line 1,872: | ||
;; -> '(1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 |
;; -> '(1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 |
||
;; 2674440 9694845) |
;; 2674440 9694845) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
(formerly Perl 6) |
(formerly Perl 6) |
||
{{works with|Rakudo|2015.12}} |
{{works with|Rakudo|2015.12}} |
||
<lang |
<syntaxhighlight lang=raku line>constant @pascal = [1], -> @p { [0, |@p Z+ |@p, 0] } ... *; |
||
constant @catalan = gather for 2, 4 ... * -> $ix { |
constant @catalan = gather for 2, 4 ... * -> $ix { |
||
Line 1,885: | Line 1,885: | ||
} |
} |
||
.say for @catalan[^20];</ |
.say for @catalan[^20];</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1 |
<pre>1 |
||
Line 1,911: | Line 1,911: | ||
===explicit subscripts=== |
===explicit subscripts=== |
||
All of the REXX program examples can handle arbitrary large numbers. |
All of the REXX program examples can handle arbitrary large numbers. |
||
< |
<syntaxhighlight lang=rexx>/*REXX program obtains and displays Catalan numbers from a Pascal's triangle. */ |
||
parse arg N . /*Obtain the optional argument from CL.*/ |
parse arg N . /*Obtain the optional argument from CL.*/ |
||
if N=='' | N=="," then N=15 /*Not specified? Then use the default.*/ |
if N=='' | N=="," then N=15 /*Not specified? Then use the default.*/ |
||
Line 1,921: | Line 1,921: | ||
@.ip=@.i; do k=ip by -1 for N; km=k-1; @.k=@.k+@.km; end /*k*/ |
@.ip=@.i; do k=ip by -1 for N; km=k-1; @.k=@.k+@.km; end /*k*/ |
||
say @.ip - @.i /*display the Ith Catalan number. */ |
say @.ip - @.i /*display the Ith Catalan number. */ |
||
end /*i*/ /*stick a fork in it, we're all done. */</ |
end /*i*/ /*stick a fork in it, we're all done. */</syntaxhighlight> |
||
'''output''' when using the default input: |
'''output''' when using the default input: |
||
<pre> |
<pre> |
||
Line 1,942: | Line 1,942: | ||
===implicit subscripts=== |
===implicit subscripts=== |
||
< |
<syntaxhighlight lang=rexx>/*REXX program obtains and displays Catalan numbers from a Pascal's triangle. */ |
||
parse arg N . /*Obtain the optional argument from CL.*/ |
parse arg N . /*Obtain the optional argument from CL.*/ |
||
if N=='' | N=="," then N=15 /*Not specified? Then use the default.*/ |
if N=='' | N=="," then N=15 /*Not specified? Then use the default.*/ |
||
Line 1,954: | Line 1,954: | ||
exit /*stick a fork in it, we're all done. */ |
exit /*stick a fork in it, we're all done. */ |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
@: parse arg !; return @.! /*return the value of @.[arg(1)] */</ |
@: parse arg !; return @.! /*return the value of @.[arg(1)] */</syntaxhighlight> |
||
'''output''' is the same as the 1<sup>st</sup> version. |
'''output''' is the same as the 1<sup>st</sup> version. |
||
===using binomial coefficients=== |
===using binomial coefficients=== |
||
< |
<syntaxhighlight lang=rexx>/*REXX program obtains and displays Catalan numbers from a Pascal's triangle. */ |
||
parse arg N . /*Obtain the optional argument from CL.*/ |
parse arg N . /*Obtain the optional argument from CL.*/ |
||
if N=='' | N=="," then N=15 /*Not specified? Then use the default.*/ |
if N=='' | N=="," then N=15 /*Not specified? Then use the default.*/ |
||
Line 1,970: | Line 1,970: | ||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
comb: procedure; parse arg x,y; if x=y then return 1; if y>x then return 0 |
comb: procedure; parse arg x,y; if x=y then return 1; if y>x then return 0 |
||
if x-y<y then y=x-y; _=1; do j=x-y+1 to x; _=_*j; end; return _/!(y)</ |
if x-y<y then y=x-y; _=1; do j=x-y+1 to x; _=_*j; end; return _/!(y)</syntaxhighlight> |
||
'''output''' is the same as the 1<sup>st</sup> version. |
'''output''' is the same as the 1<sup>st</sup> version. |
||
===binomial coefficients, memoized=== |
===binomial coefficients, memoized=== |
||
This REXX version uses memoization for the calculation of factorials. |
This REXX version uses memoization for the calculation of factorials. |
||
< |
<syntaxhighlight lang=rexx>/*REXX program obtains and displays Catalan numbers from a Pascal's triangle. */ |
||
parse arg N . /*Obtain the optional argument from CL.*/ |
parse arg N . /*Obtain the optional argument from CL.*/ |
||
if N=='' | N=="," then N=15 /*Not specified? Then use the default.*/ |
if N=='' | N=="," then N=15 /*Not specified? Then use the default.*/ |
||
Line 1,989: | Line 1,989: | ||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
comb: procedure expose !.; parse arg x,y; if x=y then return 1; if y>x then return 0 |
comb: procedure expose !.; parse arg x,y; if x=y then return 1; if y>x then return 0 |
||
if x-y<y then y=x-y; _=1; do j=x-y+1 to x; _=_*j; end; return _/!(y)</ |
if x-y<y then y=x-y; _=1; do j=x-y+1 to x; _=_*j; end; return _/!(y)</syntaxhighlight> |
||
'''output''' is the same as the 1<sup>st</sup> version. <br><br> |
'''output''' is the same as the 1<sup>st</sup> version. <br><br> |
||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang=ring> |
||
n=15 |
n=15 |
||
cat = list(n+2) |
cat = list(n+2) |
||
Line 2,007: | Line 2,007: | ||
see "" + (cat[i+1]-cat[i]) + " " |
see "" + (cat[i+1]-cat[i]) + " " |
||
next |
next |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 2,014: | Line 2,014: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
< |
<syntaxhighlight lang=tcl>def catalan(num) |
||
t = [0, 1] #grows as needed |
t = [0, 1] #grows as needed |
||
(1..num).map do |i| |
(1..num).map do |i| |
||
Line 2,024: | Line 2,024: | ||
end |
end |
||
p catalan(15)</ |
p catalan(15)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,031: | Line 2,031: | ||
=={{header|Run BASIC}}== |
=={{header|Run BASIC}}== |
||
< |
<syntaxhighlight lang=runbasic>n = 15 |
||
dim t(n+2) |
dim t(n+2) |
||
t(1) = 1 |
t(1) = 1 |
||
Line 2,039: | Line 2,039: | ||
for j = i+1 to 1 step -1: t(j) = t(j) + t(j-1 : next j |
for j = i+1 to 1 step -1: t(j) = t(j) + t(j-1 : next j |
||
print t(i+1) - t(i);" "; |
print t(i+1) - t(i);" "; |
||
next i</ |
next i</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 </pre> |
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 </pre> |
||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
< |
<syntaxhighlight lang=rust> |
||
fn main() |
fn main() |
||
Line 2,073: | Line 2,073: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 </pre> |
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 </pre> |
||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
< |
<syntaxhighlight lang=Scala>def catalan(n: Int): Int = |
||
if (n <= 1) 1 |
if (n <= 1) 1 |
||
else (0 until n).map(i => catalan(i) * catalan(n - i - 1)).sum |
else (0 until n).map(i => catalan(i) * catalan(n - i - 1)).sum |
||
(1 to 15).map(catalan(_))</ |
(1 to 15).map(catalan(_))</syntaxhighlight> |
||
{{Out}}See it in running in your browser by [https://scastie.scala-lang.org/2ybpRZxCTOyrx3mIy8yIDw Scastie (JVM)]. |
{{Out}}See it in running in your browser by [https://scastie.scala-lang.org/2ybpRZxCTOyrx3mIy8yIDw Scastie (JVM)]. |
||
=={{header|Scilab}}== |
=={{header|Scilab}}== |
||
<lang>n=15 |
<syntaxhighlight lang=text>n=15 |
||
t=zeros(1,n+2) |
t=zeros(1,n+2) |
||
t(1)=1 |
t(1)=1 |
||
Line 2,098: | Line 2,098: | ||
end |
end |
||
disp(t(i+1)-t(i)) |
disp(t(i+1)-t(i)) |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre style="height:20ex"> 1. |
<pre style="height:20ex"> 1. |
||
Line 2,117: | Line 2,117: | ||
=={{header|Seed7}}== |
=={{header|Seed7}}== |
||
< |
<syntaxhighlight lang=seed7>$ include "seed7_05.s7i"; |
||
const proc: main is func |
const proc: main is func |
||
Line 2,137: | Line 2,137: | ||
end for; |
end for; |
||
writeln; |
writeln; |
||
end func;</ |
end func;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,146: | Line 2,146: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
{{trans|Ruby}} |
{{trans|Ruby}} |
||
< |
<syntaxhighlight lang=ruby>func catalan(num) { |
||
var t = [0, 1] |
var t = [0, 1] |
||
(1..num).map { |i| |
(1..num).map { |i| |
||
Line 2,156: | Line 2,156: | ||
} |
} |
||
say catalan(15).join(' ')</ |
say catalan(15).join(' ')</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre> |
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre> |
||
=={{header|smart BASIC}}== |
=={{header|smart BASIC}}== |
||
< |
<syntaxhighlight lang=qbasic>PRINT "Catalan Numbers from Pascal's Triangle"!PRINT |
||
x = 15 |
x = 15 |
||
DIM t(x+2) |
DIM t(x+2) |
||
Line 2,174: | Line 2,174: | ||
NEXT m |
NEXT m |
||
PRINT n,"#######":t(n+1) - t(n) |
PRINT n,"#######":t(n+1) - t(n) |
||
NEXT n</ |
NEXT n</syntaxhighlight> |
||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
< |
<syntaxhighlight lang=tcl>proc catalan n { |
||
set result {} |
set result {} |
||
array set t {0 0 1 1} |
array set t {0 0 1 1} |
||
Line 2,189: | Line 2,189: | ||
} |
} |
||
puts [catalan 15]</ |
puts [catalan 15]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre> |
<pre>1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845</pre> |
||
=={{header|TI-83 BASIC}}== |
=={{header|TI-83 BASIC}}== |
||
< |
<syntaxhighlight lang=ti83b>"CATALAN |
||
15→N |
15→N |
||
seq(0,I,1,N+2)→L1 |
seq(0,I,1,N+2)→L1 |
||
Line 2,207: | Line 2,207: | ||
End |
End |
||
Disp L1(I+1)-L1(I) |
Disp L1(I+1)-L1(I) |
||
End</ |
End</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> 1 |
<pre> 1 |
||
Line 2,228: | Line 2,228: | ||
=={{header|Vala}}== |
=={{header|Vala}}== |
||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<syntaxhighlight lang=vala>void main() { |
||
const int N = 15; |
const int N = 15; |
||
uint64[] t = {0, 1}; |
uint64[] t = {0, 1}; |
||
Line 2,238: | Line 2,238: | ||
} |
} |
||
print("\n"); |
print("\n"); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,247: | Line 2,247: | ||
=={{header|VBScript}}== |
=={{header|VBScript}}== |
||
To run in console mode with cscript. |
To run in console mode with cscript. |
||
< |
<syntaxhighlight lang=vbscript>dim t() |
||
if Wscript.arguments.count=1 then |
if Wscript.arguments.count=1 then |
||
n=Wscript.arguments.item(0) |
n=Wscript.arguments.item(0) |
||
Line 2,266: | Line 2,266: | ||
next 'j |
next 'j |
||
Wscript.echo t(i+1)-t(i) |
Wscript.echo t(i+1)-t(i) |
||
next 'i</ |
next 'i</syntaxhighlight> |
||
=={{header|Visual Basic}}== |
=={{header|Visual Basic}}== |
||
{{trans|Rexx}} |
{{trans|Rexx}} |
||
{{works with|Visual Basic|VB6 Standard}} |
{{works with|Visual Basic|VB6 Standard}} |
||
<syntaxhighlight lang=vb> |
|||
<lang vb> |
|||
Sub catalan() |
Sub catalan() |
||
Const n = 15 |
Const n = 15 |
||
Line 2,288: | Line 2,288: | ||
Next i |
Next i |
||
End Sub 'catalan |
End Sub 'catalan |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre style="height:20ex"> |
<pre style="height:20ex"> |
||
Line 2,310: | Line 2,310: | ||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<syntaxhighlight lang=ecmascript>var n = 15 |
||
var t = List.filled(n+2, 0) |
var t = List.filled(n+2, 0) |
||
t[1] = 1 |
t[1] = 1 |
||
Line 2,319: | Line 2,319: | ||
System.write("%(t[i+1]-t[i]) ") |
System.write("%(t[i+1]-t[i]) ") |
||
} |
} |
||
System.print()</ |
System.print()</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,328: | Line 2,328: | ||
=={{header|Zig}}== |
=={{header|Zig}}== |
||
Uses comptime functionality to compile Pascal's triangle into the object code, then at runtime, it's simply a table lookup. (uses code from AKS primality task.) |
Uses comptime functionality to compile Pascal's triangle into the object code, then at runtime, it's simply a table lookup. (uses code from AKS primality task.) |
||
< |
<syntaxhighlight lang=Zig> |
||
const std = @import("std"); |
const std = @import("std"); |
||
const stdout = std.io.getStdOut().outStream(); |
const stdout = std.io.getStdOut().outStream(); |
||
Line 2,371: | Line 2,371: | ||
break :build coefficients; |
break :build coefficients; |
||
}; |
}; |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 2,393: | Line 2,393: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
{{trans|PARI/GP}} using binomial coefficients. |
{{trans|PARI/GP}} using binomial coefficients. |
||
< |
<syntaxhighlight lang=zkl>fcn binomial(n,k){ (1).reduce(k,fcn(p,i,n){ p*(n-i+1)/i },1,n) } |
||
(1).pump(15,List,fcn(n){ binomial(2*n,n)-binomial(2*n,n+1) })</ |
(1).pump(15,List,fcn(n){ binomial(2*n,n)-binomial(2*n,n+1) })</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,402: | Line 2,402: | ||
=={{header|ZX Spectrum Basic}}== |
=={{header|ZX Spectrum Basic}}== |
||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<syntaxhighlight lang=zxbasic>10 LET N=15 |
||
20 DIM t(N+2) |
20 DIM t(N+2) |
||
30 LET t(2)=1 |
30 LET t(2)=1 |
||
Line 2,410: | Line 2,410: | ||
70 FOR j=i+1 TO 2 STEP -1: LET t(j)=t(j)+t(j-1): NEXT j |
70 FOR j=i+1 TO 2 STEP -1: LET t(j)=t(j)+t(j-1): NEXT j |
||
80 PRINT t(i+1)-t(i);" "; |
80 PRINT t(i+1)-t(i);" "; |
||
90 NEXT i</ |
90 NEXT i</syntaxhighlight> |