Catalan numbers/Pascal's triangle: Difference between revisions
Line 114: | Line 114: | ||
=={{header|Python 2.7}}== |
=={{header|Python 2.7}}== |
||
<lang python> |
<lang python> |
||
def factorial(n): return reduce(lambda x,y:x*y,range(1,n+1),1) |
|||
def binomial(n, k): |
|||
⚫ | |||
⚫ | |||
⚫ | |||
return nt |
|||
def catalan_number(n): |
def catalan_number(n): |
||
⚫ | |||
return binomial(2*n,n)/(n+1) |
|||
⚫ | |||
⚫ | |||
return p/factorial(n) |
|||
print [catalan_number(n) for n in range(1, 16)] |
print [catalan_number(n) for n in range(1, 16)] |
||
Line 127: | Line 126: | ||
[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] |
||
</lang> |
</lang> |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
{{trans|C++}} |
{{trans|C++}} |
Revision as of 21:40, 13 November 2013
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.
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] + t[j - 1]; t[i + 1] = t[i]; foreach_reverse (immutable j; 2 .. i + 2) t[j] = 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
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
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 2.7
<lang python> def factorial(n): return reduce(lambda x,y:x*y,range(1,n+1),1)
def catalan_number(n):
p=1 for k in range(2,n+1): p *= (n+k) return p/factorial(n)
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>
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>
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
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