Lychrel numbers: Difference between revisions
Added C++ solution
m (added whitespace to the task's preamble, aligned some columnar numbers.) |
(Added C++ solution) |
||
Line 614:
Calculation took 0:11 seconds.
End of program.
</pre>
=={{header|C++}}==
{{trans|D}}
{{libheader|Boost}}
<lang cpp>#include <iostream>
#include <map>
#include <vector>
#include <boost/multiprecision/cpp_int.hpp>
typedef boost::multiprecision::cpp_int integer;
integer reverse(integer n)
{
integer rev = 0;
while (n > 0)
{
rev = rev * 10 + (n % 10);
n /= 10;
}
return rev;
}
bool is_palindrome(integer num)
{
return reverse(num) == num;
}
void print_vector(const std::vector<integer>& vec)
{
if (vec.empty())
return;
auto i = vec.begin();
std::cout << *i++;
for (; i != vec.end(); ++i)
std::cout << ", " << *i;
std::cout << '\n';
}
int main()
{
std::map<integer, std::pair<bool, integer>> cache;
std::vector<integer> seeds, related, palindromes;
for (integer n = 1; n <= 10000; ++n)
{
std::pair<bool, integer> p(true, n);
std::vector<integer> seen;
integer rev = reverse(n);
integer sum = n;
for (int i = 0; i < 500; ++i)
{
sum += rev;
rev = reverse(sum);
if (rev == sum)
{
p.first = false;
p.second = 0;
break;
}
auto iter = cache.find(sum);
if (iter != cache.end())
{
p = iter->second;
break;
}
seen.push_back(sum);
}
for (integer s : seen)
cache.emplace(s, p);
if (!p.first)
continue;
if (p.second == n)
seeds.push_back(n);
else
related.push_back(n);
if (n == reverse(n))
palindromes.push_back(n);
}
std::cout << "number of seeds: " << seeds.size() << '\n';
std::cout << "seeds: ";
print_vector(seeds);
std::cout << "number of related: " << related.size() << '\n';
std::cout << "palindromes: ";
print_vector(palindromes);
return 0;
}</lang>
{{out}}
<pre>
number of seeds: 5
seeds: 196, 879, 1997, 7059, 9999
number of related: 244
palindromes: 4994, 8778, 9999
</pre>
| |||