Stirling numbers of the second kind: Difference between revisions
++ Tcl
(Added Prolog Solution) |
(++ Tcl) |
||
Line 867:
func S2((0), _) { 0 }
func S2(n, k) is cached { S2(n-1, k)*k + S2(n-1, k-1) }</lang>
=={{header|Tcl}}==
{{trans|Java}}
<lang Tcl>proc S2 {n k} {
set nk [list $n $k]
if {[info exists ::S2cache($nk)]} {
return $::S2cache($nk)
}
if {($n > 0 && $k == 0) || ($n == 0 && $k > 0)} {
return 0
}
if {$n == $k} {
return 1
}
if {$n < $k} {
return 0
}
set n1 [expr {$n - 1}]
set k1 [expr {$k - 1}]
set r [expr {($k * [S2 $n1 $k]) + [S2 $n1 $k1]}]
set ::S2cache($nk) $r
}
proc main {} {
puts "Stirling numbers of the second kind:"
set max 12 ;# last table line to print
set L 8 ;# space to use for 1 number
puts -nonewline "n\\k"
for {set n 0} {$n <= $max} {incr n} {
puts -nonewline [format %${L}d $n]
}
puts ""
for {set n 0} {$n <= $max} {incr n} {
puts -nonewline [format %-3d $n]
for {set k 0} {$k <= $n} {incr k} {
puts -nonewline [format %${L}s [S2 $n $k]]
}
puts ""
}
puts "The maximum value of S2(100, k) = "
set previous 0
for {set k 1} {$k <= 100} {incr k} {
set current [S2 100 $k]
if {$current > $previous} {
set previous $current
} else {
puts $previous
puts "([string length $previous] digits, k = [expr {$k-1}])"
break
}
}
}
main</lang>
{{out}}
<pre>
Stirling numbers of the second kind:
n\k 0 1 2 3 4 5 6 7 8 9 10 11 12
0 1
1 0 1
2 0 1 1
3 0 1 3 1
4 0 1 7 6 1
5 0 1 15 25 10 1
6 0 1 31 90 65 15 1
7 0 1 63 301 350 140 21 1
8 0 1 127 966 1701 1050 266 28 1
9 0 1 255 3025 7770 6951 2646 462 36 1
10 0 1 511 9330 34105 42525 22827 5880 750 45 1
11 0 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1
12 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1
The maximum value of S2(100, k) =
7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674
(115 digits, k = 28)
</pre>
=={{header|zkl}}==
| |||