Lah numbers: Difference between revisions
Added C++ solution
SqrtNegInf (talk | contribs) m (→{{header|Perl}}: Fix link: Perl 6 --> Raku) |
(Added C++ solution) |
||
Line 157:
Maximum value from the L(100, *) row:
44519005448993144810881324947684737529186447692709328597242209638906324913313742508392928375354932241404408343800007105650554669129521241784320000000000000000000000</pre>
=={{header|C++}}==
{{libheader|GMP}}
<lang cpp>// Reference: https://en.wikipedia.org/wiki/Lah_number#Identities_and_relations
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <map>
#include <gmpxx.h>
using integer = mpz_class;
class unsigned_lah_numbers {
public:
integer get(int n, int k);
private:
std::map<std::pair<int, int>, integer> cache_;
};
integer unsigned_lah_numbers::get(int n, int k) {
if (k == n)
return 1;
if (k == 0 || k > n)
return 0;
auto p = std::make_pair(n, k);
auto i = cache_.find(p);
if (i != cache_.end())
return i->second;
integer result = (n - 1 + k) * get(n - 1, k) + get(n - 1, k - 1);
cache_.emplace(p, result);
return result;
}
void print_lah_numbers(unsigned_lah_numbers& uln, int n) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= i; ++j)
std::cout << std::setw(11) << uln.get(i, j);
std::cout << '\n';
}
}
int main() {
unsigned_lah_numbers uln;
std::cout << "Unsigned Lah numbers up to L(12,12):\n";
print_lah_numbers(uln, 12);
std::cout << "Maximum value of L(n,k) where n == 100:\n";
integer max = 0;
for (int k = 0; k <= 100; ++k) {
integer s = uln.get(100, k);
if (s > max)
max = s;
}
std::cout << max << '\n';
return 0;
}</lang>
{{out}}
<pre>
Unsigned Lah numbers up to L(12,12):
1
2 1
6 6 1
24 36 12 1
120 240 120 20 1
720 1800 1200 300 30 1
5040 15120 12600 4200 630 42 1
40320 141120 141120 58800 11760 1176 56 1
362880 1451520 1693440 846720 211680 28224 2016 72 1
3628800 16329600 21772800 12700800 3810240 635040 60480 3240 90 1
39916800 199584000 299376000 199584000 69854400 13970880 1663200 118800 4950 110 1
479001600 2634508800 4390848000 3293136000 1317254400 307359360 43908480 3920400 217800 7260 132 1
Maximum value of L(n,k) where n == 100:
44519005448993144810881324947684737529186447692709328597242209638906324913313742508392928375354932241404408343800007105650554669129521241784320000000000000000000000
</pre>
=={{header|D}}==
| |||