Catalan numbers: Difference between revisions
Content deleted Content added
→{{header|Pascal}}: add example |
|||
Line 1,402: | Line 1,402: | ||
The first version takes about 1.5 seconds to compute the millionth Catalan number, while the second takes 3.9 seconds. The naive implementation, for comparison, takes 21 minutes (850 times longer). In any case, printing the first 15 is simple: |
The first version takes about 1.5 seconds to compute the millionth Catalan number, while the second takes 3.9 seconds. The naive implementation, for comparison, takes 21 minutes (850 times longer). In any case, printing the first 15 is simple: |
||
<lang parigp>vector(15,n,Catalan(n))</lang> |
<lang parigp>vector(15,n,Catalan(n))</lang> |
||
=={{header|Pascal}}== |
|||
<lang pascal>Program CatalanNumbers(output); |
|||
function catalanNumber1(n: integer): double; |
|||
begin |
|||
if n = 0 then |
|||
catalanNumber1 := 1.0 |
|||
else |
|||
catalanNumber1 := double(4 * n - 2) / double(n + 1) * catalanNumber1(n-1); |
|||
end; |
|||
var |
|||
number: integer; |
|||
begin |
|||
writeln('Catalan Numbers'); |
|||
writeln('Recursion with a fraction:'); |
|||
for number := 0 to 14 do |
|||
writeln (number:3, round(catalanNumber1(number)):9); |
|||
end.</lang> |
|||
Output: |
|||
<pre> |
|||
:> ./CatalanNumbers |
|||
Catalan Numbers |
|||
Recursion with a fraction: |
|||
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 |
|||
</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |