Catalan numbers: Difference between revisions
Content deleted Content added
Basicgames (talk | contribs) |
Langurmonkey (talk | contribs) |
||
(24 intermediate revisions by 10 users not shown) | |||
Line 452:
14 2674440
15 9694845
==={{header|Applesoft BASIC}}===
{{works with|Chipmunk Basic}}
{{works with|QBasic}}
<syntaxhighlight lang="qbasic">10 HOME : REM 10 CLS for Chipmunk Basic/QBasic
20 DIM c(15)
30 c(0) = 1
40 PRINT 0, c(0)
50 FOR n = 0 TO 14
60 c(n + 1) = 0
70 FOR i = 0 TO n
80 c(n + 1) = c(n + 1) + c(i) * c(n - i)
90 NEXT i
100 PRINT n + 1, c(n + 1)
110 NEXT n
120 END</syntaxhighlight>
==={{header|BASIC256}}===
Line 515 ⟶ 531:
742900
2674440</pre>
==={{header|Chipmunk Basic}}===
{{works with|Chipmunk Basic|3.6.4}}
{{trans|Run BASIC}}
<syntaxhighlight lang="qbasic">10 FOR i = 1 TO 15
20 PRINT i;" ";catalan(i)
30 NEXT
40 END
50 SUB catalan(n)
60 catalan = 1
70 IF n <> 0 THEN catalan = ((2*((2*n)-1))/(n+1))*catalan(n-1)
80 END SUB</syntaxhighlight>
==={{header|Craft Basic}}===
<syntaxhighlight lang="basic">dim c[
let c[0] = 1
let p = n + 1
let c[p] = 0
let q = n - i
let c[p] = c[p] + c[i] * c[q]
next i
next n</syntaxhighlight>
{{out| Output}}<pre>
0 1
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|FreeBASIC}}===
Line 2,273 ⟶ 2,310:
=={{header|EasyLang}}==
<syntaxhighlight lang="text">
func catalan n
if n = 0
return
.
for i = 0 to 14
.
</syntaxhighlight>
=={{header|EchoLisp}}==
Line 2,937 ⟶ 2,953:
=={{header|Fōrmulæ}}==
{{FormulaeEntry|page=https://formulae.org/?script=examples/Catalan_numbers}}
'''Solution'''
'''Direct definition'''
[[File:Fōrmulæ - Catalan numbers 01.png]]
[[File:Fōrmulæ - Catalan numbers 02.png]]
'''Direct definition (alternative)'''
The expression <math>\frac{(2n)!}{(n+1)!\,n!}</math> turns out to be equals to <math>\prod_{k=2}^{n}\frac{n + k}{k}</math>
[[File:Fōrmulæ - Catalan numbers 03.png]]
(same result)
'''No directly defined'''
Recursive definitions are easy to write, but extremely inefficient (specially the first one).
Because a list is intended to be get, the list of previous values can be used as a form of memoization, avoiding recursion.
The next function make use of the "second" form of recursive definition (without recursion):
[[File:Fōrmulæ - Catalan numbers 04.png]]
[[File:Fōrmulæ - Catalan numbers 05.png]]
(same result)
=={{header|GAP}}==
<syntaxhighlight lang="gap">Catalan1 := n -> Binomial(2*n, n) - Binomial(2*n, n - 1);
Line 3,318 ⟶ 3,361:
</pre>
=={{header|JavaScript}}==
===Procedural===
<syntaxhighlight lang="javascript"><html><head><title>Catalan</title></head>
<body><pre id='x'></pre><script type="application/javascript">
Line 3,365 ⟶ 3,410:
14 2674440 2674440 2674440
15 9694845 9694845 9694845</pre>
===Functional===
Defining an infinite list:
<syntaxhighlight lang="javascript">(() => {
"use strict";
// ----------------- CATALAN NUMBERS -----------------
// catalansDefinitionThree :: [Int]
const catalansDefinitionThree = () =>
// An infinite sequence of Catalan numbers.
scanlGen(
c => n => Math.floor(
(2 * c * pred(2 * n)) / succ(n)
)
)(1)(
enumFrom(1)
);
// ---------------------- TEST -----------------------
// main :: IO ()
const main = () =>
take(15)(
catalansDefinitionThree()
);
// --------------------- GENERIC ---------------------
// enumFrom :: Enum a => a -> [a]
const enumFrom = function* (n) {
// An infinite sequence of integers,
// starting with n.
let v = n;
while (true) {
yield v;
v = 1 + v;
}
};
// pred :: Int -> Int
const pred = x =>
x - 1;
// scanlGen :: (b -> a -> b) -> b -> Gen [a] -> [b]
const scanlGen = f =>
// The series of interim values arising
// from a catamorphism over an infinite list.
startValue => function* (gen) {
let
a = startValue,
x = gen.next();
yield a;
while (!x.done) {
a = f(a)(x.value);
yield a;
x = gen.next();
}
};
// succ :: Int -> Int
const succ = x =>
1 + x;
// take :: Int -> [a] -> [a]
// take :: Int -> String -> String
const take = n =>
// The first n elements of a list,
// string of characters, or stream.
xs => Array.from({
length: n
}, () => {
const x = xs.next();
return x.done ? [] : [x.value];
}).flat();
// MAIN ---
return JSON.stringify(main(), null, 2);
})();</syntaxhighlight>
{{Out}}
<pre>[
1,
1,
2,
5,
14,
42,
132,
429,
1430,
4862,
16796,
58786,
208012,
742900,
2674440
]</pre>
=={{header|jq}}==
{{ works with|jq|1.4 }}
Line 3,624 ⟶ 3,778:
=={{header|langur}}==
{{trans|Perl}}
<syntaxhighlight lang="langur">val
val catalan = fn n:factorial(2 * n) / factorial(n+1) / factorial(n)
for i in 0..15 {
writeln "{{i:2}}: {{catalan(i):10}}"
}
writeln "10000: ",
</syntaxhighlight>
{{out}}
Line 3,682 ⟶ 3,838:
742900
2674440</pre>
=={{header|Logtalk}}==
For this task it is instructive to show a more general-purpose interface for sequences and an implementation of it for Catalan numbers.
First, <code>loader.lgt</code>:
<syntaxhighlight lang="logtalk">
:- initialization((
% libraries
logtalk_load(dates(loader)),
logtalk_load(meta(loader)),
logtalk_load(types(loader)),
% application
logtalk_load(seqp),
logtalk_load(catalan),
logtalk_load(catalan_test)
)).
</syntaxhighlight>
The interface is defined in <code>seqp.lgt</code> as a protocol:
<syntaxhighlight lang="logtalk">
:- protocol(seqp).
:- public(init/0). % reset to a beginning state if meaningful
:- public(nth/2). % get the nth value of the sequence
:- public(to_nth/2). % get from the start to the nth value of the sequence as a list
:- end_protocol.
</syntaxhighlight>
The implementation of a Catalan sequence generator is in <code>catalan.lgt</code>:
<syntaxhighlight lang="logtalk">
:- object(catalan, implements(seqp)).
:- private(catalan/2).
:- dynamic(catalan/2).
% Public interface.
init :- retractall(catalan(_,_)). % flush any memoized results
nth(N, V) :- \+ catalan(N, V), catalan_(N, V), !. % generate iff it's not been memoized
nth(N, V) :- catalan(N, V), !. % otherwise use the memoized version
to_nth(N, L) :-
integer::sequence(0, N, S), % generate a list of 0 to N
meta::map(nth, S, L). % map the nth/2 predicate to the list for all Catalan numbers up to N
% Local helper predicates.
catalan_(N, V) :-
N > 0, % calculate
N1 is N - 1,
N2 is N + 1,
catalan_(N1, V1), % via a recursive call
V is V1 * 2 * (2 * N - 1) // N2,
assertz(catalan(N, V)). % and memoize the result
catalan_(0, 1).
:- end_object.
</syntaxhighlight>
This is a memoizing implementation whose impact we will check in the test. The <code>init/0</code> predicate flushes any memoized results.
The test driver is a simple one that generates the first fifteen Catalan numbers four times, comparing times with and without memoization. From <code>catalan_test.lgt</code>:
<syntaxhighlight lang="logtalk">
:- object(catalan_test).
:- public(run/0).
run :-
% put the object into a known initial state
catalan::init,
% first 15 Catalan numbers, record duration.
time_operation(catalan::to_nth(15, C1), D1),
% first 15 Catalan numbers again, twice, recording duration.
time_operation(catalan::to_nth(15, C2), D2),
time_operation(catalan::to_nth(15, C3), D3),
% reset the object again
catalan::init,
% first 15 Catalan numbers, record duration.
time_operation(catalan::to_nth(15, C4), D4),
% ensure the results were the same each time
C1 = C2, C2 = C3, C3 = C4,
% write the results and durations of each run
write(C1), write(' '), write(D1), nl,
write(C2), write(' '), write(D2), nl,
write(C3), write(' '), write(D3), nl,
write(C4), write(' '), write(D4), nl.
% visual inspection should show all results the same
% first and final durations should be much larger
:- meta_predicate(time_operation(0, *)).
time_operation(Goal, Duration) :-
time::cpu_time(Before),
call(Goal),
time::cpu_time(After),
Duration is After - Before.
:- end_object.
</syntaxhighlight>
{{Out}}
The session at the top-level looks like this:
<pre>
?- {loader}.
% ... messages elided ...
% (0 warnings)
true.
?- catalan_test::run.
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845] 0.001603
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845] 0.000306
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845] 0.00026
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845] 0.001346
true.
</pre>
This test shows:
# The <code>nth/2</code> predicate works (since <code>to_nth/2</code> is implemented in terms of it).
# The <code>to_nth/2</code> predicate works.
# Memoization generates a speedup of between ~4.5× to ~6.2× over generating from scratch.
=={{header|Lua}}==
<syntaxhighlight lang="lua">-- recursive with memoization
Line 3,844 ⟶ 4,138:
/* both return [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440] */</syntaxhighlight>
=={{header|Miranda}}==
<syntaxhighlight lang="miranda">main :: [sys_message]
main = [Stdout (lay (map (show . catalan) [0..14]))]
catalan :: num->num
catalan 0 = 1
catalan n = (4*n - 2) * catalan (n - 1) div (n + 1)</syntaxhighlight>
{{out}}
<pre>1
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440</pre>
=={{header|Modula-2}}==
<syntaxhighlight lang="modula2">MODULE CatalanNumbers;
Line 3,910 ⟶ 4,228:
ReadChar
END CatalanNumbers.</syntaxhighlight>
=={{header|Nim}}==
<syntaxhighlight lang="nim">import math
Line 5,852 ⟶ 6,171:
{{libheader|Wren-fmt}}
{{libheader|Wren-math}}
<syntaxhighlight lang="
import "./math" for Int
var catalan = Fn.new { |n|
Line 5,915 ⟶ 6,234:
15 9694845
</pre>
=={{header|XLISP}}==
<syntaxhighlight lang="lisp">(defun catalan (n)
|