Riordan numbers: Difference between revisions
Added C++ solution
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
(Added C++ solution) |
||
Line 115:
The 1000th number is: 51077756867821111314...79942013897484633052 with 472 digits
The 10000th number is: 19927418577260688844...71395322020211157137 with 4765 digits
</pre>
=={{header|C++}}==
{{libheader|GMP}}
<syntaxhighlight lang="cpp">#include <iomanip>
#include <iostream>
#include <gmpxx.h>
using big_int = mpz_class;
class riordan_number_generator {
public:
big_int next();
private:
big_int a0_ = 1;
big_int a1_ = 0;
int n_ = 0;
};
big_int riordan_number_generator::next() {
int n = n_++;
if (n == 0)
return a0_;
if (n == 1)
return a1_;
big_int a = (n - 1) * (2 * a1_ + 3 * a0_) / (n + 1);
a0_ = a1_;
a1_ = a;
return a;
}
std::string to_string(const big_int& num, size_t n) {
std::string str = num.get_str();
size_t len = str.size();
if (len > n)
str = str.substr(0, n / 2) + "..." + str.substr(len - n / 2);
return str;
}
int main() {
riordan_number_generator rng;
std::cout << "First 32 Riordan numbers:\n";
int i = 1;
for (; i <= 32; ++i) {
std::cout << std::setw(14) << rng.next()
<< (i % 4 == 0 ? '\n' : ' ');
}
for (; i < 1000; ++i)
rng.next();
auto num = rng.next();
++i;
std::cout << "\nThe 1000th is " << to_string(num, 40) << " ("
<< num.get_str().size() << " digits).\n";
for (; i < 10000; ++i)
rng.next();
num = rng.next();
std::cout << "The 10000th is " << to_string(num, 40) << " ("
<< num.get_str().size() << " digits).\n";
}</syntaxhighlight>
{{out}}
<pre>
First 32 Riordan numbers:
1 0 1 1
3 6 15 36
91 232 603 1585
4213 11298 30537 83097
227475 625992 1730787 4805595
13393689 37458330 105089229 295673994
834086421 2358641376 6684761125 18985057351
54022715451 154000562758 439742222071 1257643249140
The 1000th is 51077756867821111314...79942013897484633052 (472 digits).
The 10000th is 19927418577260688844...71395322020211157137 (4765 digits).
</pre>
| |||