Stirling numbers of the first kind: Difference between revisions
Content added Content deleted
No edit summary |
|||
Line 883: | Line 883: | ||
19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000 |
19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000 |
||
(158 digits, k = 5)</pre> |
(158 digits, k = 5)</pre> |
||
=={{header|Nim}}== |
|||
A simple implementation using the recursive definition is enough to complete the task. |
|||
<lang Nim>import sequtils, strutils |
|||
proc s1(n, k: Natural): Natural = |
|||
if k == 0: return ord(n == 0) |
|||
if k > n: return 0 |
|||
s1(n - 1, k - 1) + (n - 1) * s1(n - 1, k) |
|||
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 ($s1(n, k)).align(10) |
|||
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 2 3 1 |
|||
4 0 6 11 6 1 |
|||
5 0 24 50 35 10 1 |
|||
6 0 120 274 225 85 15 1 |
|||
7 0 720 1764 1624 735 175 21 1 |
|||
8 0 5040 13068 13132 6769 1960 322 28 1 |
|||
9 0 40320 109584 118124 67284 22449 4536 546 36 1 |
|||
10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 |
|||
11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 |
|||
12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1</pre> |
|||
To find the maximum value of S1(n, k) for n = 100, we need to use a third party library such as “bignum”. But this is not enough. To avoid multiple computation of the same terms, we have to use a cache. Note also that this method has its limits as it depends on the allowed depth of recursion. Here, this is not a problem and the result is obtained almost instantaneously. |
|||
{{libheader|bignum}} |
|||
<lang Nim>import tables |
|||
import bignum |
|||
var cache: Table[(Natural, Natural), Int] |
|||
proc s1(n, k: Natural): Int = |
|||
if k == 0: return newInt(ord(n == 0)) |
|||
if k > n: return newInt(0) |
|||
if (n, k) in cache: return cache[(n, k)] |
|||
result = s1(n - 1, k - 1) + (n - 1) * s1(n - 1, k) |
|||
cache[(n, k)] = result |
|||
var max = newInt(-1) |
|||
for k in 0..100: |
|||
let s = s1(100, k) |
|||
if s > max: max = s |
|||
else: break |
|||
echo "Maximum Stirling number of the first kind with n = 100:" |
|||
echo max</lang> |
|||
{{out}} |
|||
<pre>Maximum Stirling number of the first kind with n = 100: |
|||
19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |