Catalan numbers/Pascal's triangle: Difference between revisions
Add Seed7 example |
|||
Line 360: | Line 360: | ||
{{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|Seed7}}== |
|||
<lang seed7>$ include "seed7_05.s7i"; |
|||
const proc: main is func |
|||
local |
|||
const integer: N is 15; |
|||
var array integer: t is [] (1) & N times 0; |
|||
var integer: i is 0; |
|||
var integer: j is 0; |
|||
begin |
|||
for i range 1 to N do |
|||
for j range i downto 2 do |
|||
t[j] +:= t[j - 1]; |
|||
end for; |
|||
t[i + 1] := t[i]; |
|||
for j range i + 1 downto 2 do |
|||
t[j] +:= t[j - 1]; |
|||
end for; |
|||
write(t[i + 1] - t[i] <& " "); |
|||
end for; |
|||
writeln; |
|||
end func;</lang> |
|||
{{out}} |
|||
<pre> |
|||
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 |
|||
</pre> |
|||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
Revision as of 17:51, 25 June 2014
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
The task is to print out the first 15 Catalan numbers by extracting them from Pascal's triangle, see Catalan Numbers and the Pascal Triangle.
Ada
Uses package Pascal from the Pascal triangle solution[[1]]
<lang Ada>with Ada.Text_IO, Pascal;
procedure Catalan is
Last: Positive := 15; Row: Pascal.Row := Pascal.First_Row(2*Last+1);
begin
for I in 1 .. Last loop Row := Pascal.Next_Row(Row); Row := Pascal.Next_Row(Row); Ada.Text_IO.Put(Integer'Image(Row(I+1)-Row(I+2))); end loop;
end Catalan;</lang>
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
AutoHotkey
<lang AutoHotkey>/* Generate Catalan Numbers // // smgs: 20th Feb, 2014
- /
Array := [], Array[2,1] := Array[2,2] := 1 ; Array inititated and 2nd row of pascal's triangle assigned INI := 3 ; starts with calculating the 3rd row and as such the value Loop, 31 ; every odd row is taken for calculating catalan number as such to obtain 15 we need 2n+1 { if ( A_index > 2 ) { Loop, % A_INDEX { old := ini-1, index := A_index, index_1 := A_index + 1 Array[ini, index_1] := Array[old, index] + Array[old, index_1] Array[ini, 1] := Array[ini, ini] := 1 line .= Array[ini, A_index] " " } ;~ MsgBox % line ; gives rows of pascal's triangle ; calculating every odd row starting from 1st so as to obtain catalan's numbers if ( mod(ini,2) != 0) { StringSplit, res, line, %A_Space% ans := res0//2, ans_1 := ans++ result := result . res%ans_1% - res%ans% " " } line := ini++ } } MsgBox % result</lang>
- Produces:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
C++
<lang cpp>// Generate Catalan Numbers // // Nigel Galloway: June 9th., 2012 //
- include <iostream>
int main() {
const int N = 15; int t[N+2] = {0,1}; for(int i = 1; i<=N; i++){ for(int j = i; j>1; j--) t[j] = t[j] + t[j-1]; t[i+1] = t[i]; for(int j = i+1; j>1; j--) t[j] = t[j] + t[j-1]; std::cout << t[i+1] - t[i] << " "; } return 0;
}</lang>
- Produces:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
D
<lang d>void main() {
import std.stdio;
enum uint N = 15; uint[N + 2] t; t[1] = 1;
foreach (immutable i; 1 .. N + 1) { foreach_reverse (immutable j; 2 .. i + 1) t[j] += t[j - 1]; t[i + 1] = t[i]; foreach_reverse (immutable j; 2 .. i + 2) t[j] += t[j - 1]; write(t[i + 1] - t[i], ' '); }
}</lang>
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
Icon and Unicon
The following works in both languages. It avoids computing elements in Pascal's triangle that aren't used.
<lang unicon>link math
procedure main(A)
limit := (integer(A[1])|15)+1 every write(right(binocoef(i := 2*seq(0)\limit,i/2)-binocoef(i,i/2+1),30))
end</lang>
Sample run:
->cn 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 ->
J
<lang j> Catalan=. }:@:(}.@:((<0 1)&|:) - }:@:((<0 1)&|:@:(2&|.)))@:(i. +/\@]^:[ #&1)@:(2&+)</lang>
- Example use:
<lang j> Catalan 15 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
</lang>
A structured derivation of Catalan follows:
<lang j> o=. @: NB. Composition of verbs (functions)
( PascalTriangle=. i. ((+/\@]^:[)) #&1 ) 5
1 1 1 1 1 1 2 3 4 5 1 3 6 10 15 1 4 10 20 35 1 5 15 35 70
( MiddleDiagonal=. (<0 1)&|: ) o PascalTriangle 5
1 2 6 20 70
( AdjacentLeft=. MiddleDiagonal o (2&|.) ) o PascalTriangle 5
1 4 15 1 5
( Catalan=. }: o (}. o MiddleDiagonal - }: o AdjacentLeft) o PascalTriangle o (2&+) f. ) 5
1 2 5 14 42
Catalan
}:@:(}.@:((<0 1)&|:) - }:@:((<0 1)&|:@:(2&|.)))@:(i. +/\@]^:[ #&1)@:(2&+)</lang>
Mathematica
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. <lang Mathematica>nextrow[lastrow_] := Module[{output},
output = ConstantArray[1, Length[lastrow] + 1]; Do[ outputi + 1 = lastrowi + lastrowi + 1; , {i, 1, Length[lastrow] - 1}]; output ]
pascaltriangle[size_] := NestList[nextrow, {1}, size] catalannumbers[length_] := Module[{output, basetriangle},
basetriangle = pascaltriangle[2 length]; list1 = basetriangle# *2 + 1, # + 1 & /@ Range[length]; list2 = basetriangle# *2 + 1, # + 2 & /@ Range[length]; list1 - list2 ]
(* testing *) catalannumbers[15]</lang>
- Output:
{1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845}
MATLAB / Octave
<lang MATLAB>p = pascal(17); diag(p(2:end-1,2:end-1))-diag(p,2)</lang> Output:
ans = 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
PARI/GP
<lang parigp>vector(15,n,binomial(2*n,n)-binomial(2*n,n+1))</lang>
- Output:
%1 = [1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845]
Perl
<lang Perl>use constant N => 15; my @t = (0, 1); for(my $i = 1; $i <= N; $i++) {
for(my $j = $i; $j > 1; $j--) { $t[$j] += $t[$j-1] } $t[$i+1] = $t[$i]; for(my $j = $i+1; $j>1; $j--) { $t[$j] += $t[$j-1] } print $t[$i+1] - $t[$i], " ";
}</lang>
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
Perl 6
<lang perl6>constant @pascal = [1], -> @p { [0, @p Z+ @p, 0] } ... *;
constant @catalan = gather for 2, 4 ... * -> $ix {
my @row := @pascal[$ix]; my $mid = +@row div 2; take [-] @row[$mid, $mid+1]
}
.say for @catalan[^20];</lang>
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 35357670 129644790 477638700 1767263190 6564120420
Python
<lang python>>>> n = 15 >>> t = [0] * (n + 2) >>> t[1] = 1 >>> for i in range(1, n + 1): for j in range(i, 1, -1): t[j] += t[j - 1] t[i + 1] = t[i] for j in range(i + 1, 1, -1): t[j] += t[j - 1] print(t[i+1] - t[i], end=' ')
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
>>> </lang>
<lang python>def catalan_number(n):
nm = dm = 1 for k in range(2, n+1): nm, dm = ( nm*(n+k), dm*k ) return nm/dm
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]</lang>
Racket
<lang Racket>
- lang racket
(define (next-half-row r)
(define r1 (for/list ([x r] [y (cdr r)]) (+ x y))) `(,(* 2 (car r1)) ,@(for/list ([x r1] [y (cdr r1)]) (+ x y)) 1 0))
(let loop ([n 15] [r '(1 0)])
(cons (- (car r) (cadr r)) (if (zero? n) '() (loop (sub1 n) (next-half-row r)))))
- -> '(1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900
- 2674440 9694845)
</lang>
REXX
<lang rexx>/*REXX program obtains Catalan numbers from Pascal's triangle. */ numeric digits 200 /*might have large Catalan nums. */ parse arg N .; if N== then N=15 /*Any args? No, then use default*/ @.=0; @.1=1 /*stem array default, 1st value. */
do i=1 for N; ip=i+1 do j=i by -1 for N; jm=j-1; @.j=@.j+@.jm; end /*j* @.ip=@.i; do k=ip by -1 for N; km=k-1; @.k=@.k+@.km; end /*k* say @.ip-@.i end /*i* /*stick a fork in it, we're done.*/</lang>
output when using the default input:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
Run BASIC
<lang runbasic>n = 15 dim t(n+2) t(1) = 1 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 t(i+1) - t(i);" "; next i</lang>
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
Ruby
<lang tcl>def catalan(num)
t = [0, 1] #grows as needed 1.upto(num).map do |i| i.downto(1){|j| t[j] += t[j-1]} t[i+1] = t[i] (i+1).downto(1) {|j| t[j] += t[j-1]} t[i+1] - t[i] end
end
puts catalan(15).join(", ")</lang>
- Output:
1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845
Seed7
<lang seed7>$ include "seed7_05.s7i";
const proc: main is func
local const integer: N is 15; var array integer: t is [] (1) & N times 0; var integer: i is 0; var integer: j is 0; begin for i range 1 to N do for j range i downto 2 do t[j] +:= t[j - 1]; end for; t[i + 1] := t[i]; for j range i + 1 downto 2 do t[j] +:= t[j - 1]; end for; write(t[i + 1] - t[i] <& " "); end for; writeln; end func;</lang>
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
Tcl
<lang tcl>proc catalan n {
set result {} array set t {0 0 1 1} for {set i 1} {[set k $i] <= $n} {incr i} {
for {set j $i} {$j > 1} {} {incr t($j) $t([incr j -1])} set t([incr k]) $t($i) for {set j $k} {$j > 1} {} {incr t($j) $t([incr j -1])} lappend result [expr {$t($k) - $t($i)}]
} return $result
}
puts [catalan 15]</lang>
- Output:
1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845