Stirling numbers of the second kind: Difference between revisions
Added C++ solution
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
(Added C++ solution) |
||
Line 108:
12 0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1
Maximum Stirling number of the second kind with n = 100:
7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674
</pre>
=={{header|C++}}==
{{libheader|GMP}}
<lang cpp>#include <cstdint>
#include <iomanip>
#include <iostream>
#include <map>
#include <gmpxx.h>
using integer = mpz_class;
class stirling2
{
public:
integer get(int n, int k);
private:
std::map<std::pair<int, int>, integer> cache_;
};
integer stirling2::get(int n, int k)
{
if (k == 0 || n == 0)
return 0;
if (k == n)
return 1;
auto p = std::make_pair(n, k);
auto i = cache_.find(p);
if (i != cache_.end())
return i->second;
integer s = k * get(n - 1, k) + get(n - 1, k - 1);
cache_.emplace(p, s);
return s;
}
void print_stirling_numbers(stirling2& s2, int n)
{
for (int i = 0; i <= n; ++i)
{
for (int j = 0; j <= i; ++j)
std::cout << std::setw(8) << s2.get(i, j);
std::cout << '\n';
}
}
int main()
{
stirling2 s2;
std::cout << "Stirling numbers of the second kind:\n";
print_stirling_numbers(s2, 12);
std::cout << "Maximum value of S2(n,k) where n == 100:\n";
integer max = 0;
for (int k = 0; k <= 100; ++k)
{
integer s = s2.get(100, k);
if (s > max)
max = s;
}
std::cout << max << '\n';
return 0;
}</lang>
{{out}}
<pre>
Stirling numbers of the second kind:
0
0 1
0 1 1
0 1 3 1
0 1 7 6 1
0 1 15 25 10 1
0 1 31 90 65 15 1
0 1 63 301 350 140 21 1
0 1 127 966 1701 1050 266 28 1
0 1 255 3025 7770 6951 2646 462 36 1
0 1 511 9330 34105 42525 22827 5880 750 45 1
0 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1
0 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1
Maximum value of S2(n,k) where n == 100:
7769730053598745155212806612787584787397878128370115840974992570102386086289805848025074822404843545178960761551674
</pre>
| |||