Anonymous user
Stirling numbers of the second kind: Difference between revisions
→{{header|Nim}}
(→{{header|Ruby}}: added Ruby) |
|||
Line 834:
7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674
(115 digits, k = 28)</pre>
=={{header|Nim}}==
As for Stirling numbers of first kind, a simple program using recursive definition is enough to solve the task when not using big numbers.
<lang Nim>import sequtils, strutils
proc s2(n, k: Natural): Natural =
if n == k: return 1
if n == 0 or k == 0: return 0
k * s2(n - 1, k) + s2(n - 1, k - 1)
echo " k ", toSeq(0..12).mapIt(($it).align(2)).join(" ")
echo " n"
for n in 0..12:
stdout.write ($n).align(2)
for k in 0..n:
stdout.write ($s2(n, k)).align(8)
stdout.write '\n'</lang>
{{out}}
<pre> k 0 1 2 3 4 5 6 7 8 9 10 11 12
n
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</pre>
Now, to solve the second part of the task, we have to use big numbers. As for Stirling numbers of first kind, we also use a cache to avoid to repeat multiple times the same computations.
{{libheader|bignum}}
<lang Nim>import tables
import bignum
var cache: Table[(Natural, Natural), Int]
proc s2(n, k: Natural): Int =
if n == k: return newInt(1)
if n == 0 or k == 0: return newInt(0)
if (n, k) in cache: return cache[(n, k)]
result = k * s2(n - 1, k) + s2(n - 1, k - 1)
cache[(n, k)] = result
var max = newInt(-1)
for k in 0..100:
let s = s2(100, k)
if s > max: max = s
else: break
echo "Maximum Stirling number of the second kind with n = 100:"
echo max</lang>
{{out}}
<pre>Maximum Stirling number of the second kind with n = 100:
7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674</pre>
=={{header|Perl}}==
| |||