时间戳

首页 > 解决方案 > 我的值大于无符号整数的范围

c++ - 我的值大于无符号整数的范围

问题描述

我有这个练习：“考虑一些自然数n，如果它不是回文数，则以相反的顺序更改数字的顺序并将结果数与原始数相加。如果和不是回文数，重复对该总和进行相同的过程，直到获得回文数。上述过程是否对任何 n 都是有限的。如果是，则打印出过程数“

前任

输入：1 输出：0

输入：12 输出：1

我的问题是，当我遇到更大的数字（例如 19170）时，它将超过 unsigned long long int 的限制。如果有人可以解释或指导我找到可以帮助我进一步理解它的资源，那也很棒。

#include <iostream>
#include <math.h>
using namespace std;

bool check (long long int n)
{
 long long int clone_n=n,count=0,ans=0;
 while (clone_n!=0)
 {
     clone_n/=10;
     count++;
 }
 clone_n=n;
 for(int i=count;i>=0;i--)
 {
     ans+=(clone_n%10)*pow(10,i-1);
     clone_n/=10;
 }
 if(ans==n)
 {
     return true;
 }
 return false;
}


long long int reverse(long long int n)
{
 long long int clone_n=n,count=0,ans=0;
 while (clone_n!=0)
 {
     clone_n/=10;
     count++;
 }
 clone_n=n;
 for(int i=count;i>=0;i--)
 {
     ans+=(clone_n%10)*pow(10,i-1);
     clone_n/=10;
 }
 return ans;
}

int main()
{
 long long int n,count=0;
 cin>>n;
 if(check(n))
 {
     cout<<0;
     return 0;
 }
 else
 {
     while(check(n)!=1)
     {
         count++;
         n+=reverse(n);
     }
 }
 cout<<count;
}

我的代码也包含在链接中：https ://ideone.com/0p7JJU

标签： c++palindrome

解决方案

不会终止 OP 描述的算法的自然数称为 Lychrel 数。https://en.wikipedia.org/wiki/Lychrel_number

目前尚不清楚这些数字是否存在，正如 zkoza 在上述答案中正确猜测的那样，196 是最小的 Lychrel 数字候选者。

因此，这是一个特别难以解决的问题，但是，我想解决 OP 面临的特定溢出问题。正如评论中 maximum_prime_is_463035818 所指出的，没有任何整数表示的实际需要。

#include <iostream>

//take advantage of the fact that std::string use contiguous memory
bool is_palindrome(const char* first, const char* last)
{
    --last;
    while(first < last) {
        if (*first != *last)
            return false;
        ++first;
        --last;
    }
    return true;
}

std::string reverse_and_add(const std::string& digits)
{
    size_t size = digits.size();
    //the result string will be at least the same length
    std::string result(size,'0');
    int carry_over = 0;
    int ascii_zero = 48;
    for (size_t i = 0; i < size; i++) 
    {
        int front = digits.at(i) - ascii_zero;
        int back = digits.at(size - i - 1) - ascii_zero;
        int sum = front + back + carry_over;
        carry_over = sum / 10;
        int digit = sum >= 10 ? sum - 10 : sum;
        result[size - i - 1] = static_cast<char>(digit + ascii_zero);
    }
    //if at the last step we have a carry over we need to add an extra digit to
    //the string
    if (carry_over > 0)
        result = static_cast<char>(carry_over + ascii_zero) + result;
    return result;
}

void check(const std::string& s, int max_iteration)
{
    int counter = 0;
    std::string v(s);
    while(!is_palindrome(v.c_str(), v.c_str() + v.size()) && counter < max_iteration)
    {
        v = reverse_and_add(v);
        if (counter % 1000 == 0 && counter > 0)
            std::cout << "progressing iteration: " << counter << " string size: " << v.size() << std::endl;
        counter++;
    }
    if (counter == max_iteration)
        std::cout << "No result found" << std::endl;
    else
        std::cout << "result: " << counter << std::endl;
} 

int main()
{
    int max_iteration = 50000;
    check("187",max_iteration); // -> return 23
    check("19170", max_iteration); // -> doesn't find a solution
                                   // the final string is thousands of characters
}

更新

只是为了好玩，我运行了 196 到 1000000 位（1987 年花了 3 年时间），它在大约一个半小时内产生了相同的结果（这些硬件工程师很棒）。

结果：2415836 ./a.out 5315.83s 用户 21.29s 系统 99% cpu 1:29:12.58 总计

推荐阅读