Riordan numbers: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
(Added C++ solution) |
||
Line 115: | Line 115: | ||
The 1000th number is: 51077756867821111314...79942013897484633052 with 472 digits |
The 1000th number is: 51077756867821111314...79942013897484633052 with 472 digits |
||
The 10000th number is: 19927418577260688844...71395322020211157137 with 4765 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> |
</pre> |
||