Rosetta Code

Catalan numbers/Pascal's triangle: Difference between revisions

Page Discussion

Catalan numbers/Pascal's triangle (view source)

Revision as of 12:10, 12 November 2023

4,883 bytes added ,  6 months ago
m
→‎{{header|Wren}}: Changed to Wren S/H
(Added XPL0 example.)
m (→‎{{header|Wren}}: Changed to Wren S/H)
 
(6 intermediate revisions by 5 users not shown)
Line 361:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
</pre>
 
=={{header|BASIC}}==
==={{header|Applesoft BASIC}}===
{{trans|MSX-BASIC}}
<syntaxhighlight lang="qbasic">10 HOME
20 n = 15
30 DIM t(n+2)
50 t(1) = 1
55 PRINT "The first 15 Catalan numbers are: "; CHR$(10)
60 FOR i = 1 TO n
70 FOR j = i TO 1 STEP -1 : t(j) = t(j) + t(j-1) : NEXT j
80 t(i+1) = t(i)
90 FOR j = i+1 TO 1 STEP -1 : t(j) = t(j) + t(j-1) : NEXT j
100 PRINT i; ": "; t(i+1) - t(i)
120 NEXT i
130 END</syntaxhighlight>
 
==={{header|Chipmunk Basic}}===
{{trans|MSX-BASIC}}
{{works with|Chipmunk Basic|3.6.4}}
<syntaxhighlight lang="qbasic">100 cls
110 n = 15
120 dim t(n+2)
130 t(1) = 1
140 print "The first 15 Catalan numbers are: ";chr$(10)
150 for i = 1 to n
160 for j = i to 1 step -1 : t(j) = t(j)+t(j-1) : next j
170 t(i+1) = t(i)
180 for j = i+1 to 1 step -1 : t(j) = t(j)+t(j-1) : next j
190 print using "###";i;": ";
200 print using "#########";t(i+1)-t(i)
210 next i
220 end</syntaxhighlight>
 
==={{header|GW-BASIC}}===
{{works with|PC-BASIC|any}}
{{works with|BASICA}}
{{works with|QBasic}}
{{works with|MSX BASIC}}
The [[#GW-BASIC|GW-BASIC]] solution works without any changes.
 
==={{header|MSX Basic}}===
{{works with|MSX BASIC|any}}
<syntaxhighlight lang="qbasic">100 CLS
110 N = 15
120 DIM T(N+2)
130 T(1) = 1
140 PRINT "The first 15 Catalan numbers are: "; CHR$(10)
150 FOR I = 1 TO N
160 FOR J = I TO 1 STEP -1 : T(J) = T(J) + T(J-1) : NEXT J
170 T(I+1) = T(I)
180 FOR J = I+1 TO 1 STEP -1 : T(J) = T(J) + T(J-1) : NEXT J
190 PRINT USING "###: #########";I; T(I+1) - T(I)
200 NEXT I
210 END</syntaxhighlight>
{{out}}
<pre>The first 15 Catalan numbers are:
 
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>
 
==={{header|QBasic}}===
The [[#MSX-BASIC|MSX-BASIC]] solution works without any changes.
 
==={{header|XBasic}}===
{{trans|MSX-BASIC}}
{{works with|Windows XBasic}}
<syntaxhighlight lang="qbasic">PROGRAM "Pascal's triangle"
VERSION "0.0000"
 
 
DECLARE FUNCTION Entry ()
 
 
FUNCTION Entry ()
N = 15
DIM T[N+2]
T[1] = 1
 
PRINT "The first 15 Catalan numbers are: "; CHR$(10)
FOR I = 1 TO N
FOR J = I TO 1 STEP -1
T[J] = T[J] + T[J-1]
NEXT J
T[I+1] = T[I]
FOR J = I+1 TO 1 STEP -1
T[J] = T[J] + T[J-1]
NEXT J
PRINT FORMAT$("###",I); ": "; FORMAT$("#########",(T[I+1] - T[I]))
NEXT I
 
END FUNCTION
END PROGRAM</syntaxhighlight>
 
==={{header|Yabasic}}===
{{trans|MSX-BASIC}}
<syntaxhighlight lang="vb">n = 15
dim t(n+2)
t(1) = 1
print "The first 15 Catalan numbers are: \n"
for i = 1 to n
for j = i to 1 step -1
t(j) = t(j) + t(j-1)
next j
t(i+1) = t(i)
for j = i+1 to 1 step -1
t(j) = t(j) + t(j-1)
next j
print i using("###");
print ": ";
print t(i+1)-t(i) using ("#########")
next i</syntaxhighlight>
 
=={{header|Batch File}}==
<syntaxhighlight lang="dos">@echo off
Line 543 ⟶ 669:
=={{header|Delphi}}==
See [https://rosettacode.org/wiki/Catalan_numbers/Pascal%27s_triangle#Pascal Pascal].
=={{header|EasyLang}}==
{{trans|AWK}}
<syntaxhighlight lang="easylang">
print 1
for n = 2 to 15
num = 1
den = 1
for k = 2 to n
num *= n + k
den *= k
cat = num / den
.
print cat
.
</syntaxhighlight>
 
 
=={{header|EchoLisp}}==
<syntaxhighlight lang="scheme">
Line 568 ⟶ 711:
→ 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
</syntaxhighlight>
 
=={{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.
Line 1,373 ⟶ 1,517:
2674440
9694845</pre>
 
=={{header|Maxima}}==
<syntaxhighlight lang="maxima">
/* The Catalan triangle can be generated using genmatrix */
genmatrix(lambda([n,k],if n>=k then binomial(n+k-1,k-1)-2*binomial(n+k-2,k-2) else 0),15,15)$
 
/* The Catalan numbers are in the main diagonal */
makelist(%[i,i],i,1,15);
</syntaxhighlight>
{{out}}
<pre>
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440]
</pre>
 
=={{header|Nim}}==
{{trans|Python}}
Line 1,981 ⟶ 2,139:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
</pre>
=={{header|RPL}}==
We have taken the opportunity provided by the task to develop a routine that recursively computes Pascal's triangle.
If the challenge was to look for high Catalan numbers, memoizing the triangle would make sense.
{{works with|Halcyon Calc|4.2.8}}
{| class="wikitable"
! RPL code
! Comment
|-
|
≪ '''IF THEN''' LAST 1 + → n1
≪ n1 2 - '''PASLIN'''
{ } n1 + RDM
DUP ARRY→ DROP n1 ROLLD n1 →ARRY +
≫ '''ELSE''' [ 1 ] '''END'''
≫ ‘'''PASLIN'''’ STO
≪
DUP DUP + '''PASLIN'''
SWAP GETI ROT ROT GET SWAP -
≫ ‘'''CATLN'''’ STO
|
'''PASLIN''' ''( n -- [ 1..(n,p)..1 ] ) ''
get previous line
add a zero at tail
duplicate it, rotate right coeffs and sum
'''CATLN''' ''( n -- C(n) )''
get Pascal_line(2n)
return line[n+1]-line[n]
|}
{{in}}
<pre>
≪ { } 1 15 FOR j CATLN j + NEXT ≫ EVAL
</pre>
{{out}}
<pre>
1: { 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 }
</pre>
Runs in 119 seconds on an HP-28S.
===Fast, idiomatic approach===
Using the built-in <code>COMB</code> function, which returns coefficients of Pascal's triangle:
≪ { } 1 15 '''FOR''' j
j DUP + j COMB LAST 1 - COMB - + '''NEXT'''
≫ EVAL
Same output than above, runs in 2.4 seconds on an HP-28S.
 
=={{header|Ruby}}==
<syntaxhighlight lang="tcl">def catalan(num)
Line 1,997 ⟶ 2,204:
[1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]
</pre>
 
=={{header|Run BASIC}}==
<syntaxhighlight lang="runbasic">n = 15
Line 2,265 ⟶ 2,473:
=={{header|Wren}}==
{{trans|C++}}
<syntaxhighlight lang="ecmascriptwren">var n = 15
var t = List.filled(n+2, 0)
t[1] = 1
Line 2,280 ⟶ 2,488:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
</pre>
 
=={{header|XPL0}}==
{{trans|C++}}
Line 2,296 ⟶ 2,505:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 </pre>
=={{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 test for primes|AKS primality task]].)
<syntaxhighlight lang="zig">
const std = @import("std");
const stdout = std.io.getStdOut().outStream();
 
pub fn main() !void {
const stdout = std.io.getStdOut().writer();
 
var n: u32 = 1;
while (n <= 15) : (n += 1) {
Line 2,320 ⟶ 2,530:
const rmax = 68;
 
// evaluated and created at compile-time
const pascal = build: {
@setEvalBranchQuota(100_000);
Line 2,359 ⟶ 2,570:
15 9694845
</pre>
 
=={{header|zkl}}==
{{trans|PARI/GP}} using binomial coefficients.
PureFox
9,476

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/340709...352094"