时间戳

首页 > 解决方案 > 用算法查找回文

c++ - 用算法查找回文

问题描述

我得到一个数字 N<=200，我需要仅使用此算法找到回文并输出回文和迭代次数：

1) 倒数

2）倒数+前一

例子：

1) N=99

出 99 0

2) N=69

69+96=165 165+561=726 726+627=1353 1353+3531=4884

出：4884 4

我的代码：

#include <iostream>

using namespace std;

int rev(int a)
{
    int b = 0;
    while (a)
    {
        b = 10 * b + a % 10;
        a /= 10;
    }

    return b;
}

int main()
{
    ios::sync_with_stdio(0);
    int n, c = 0;
    cin >> n;
    while (n != rev(n))
    {
        n = n + rev(n);
        c++;
    }
    cout << n << endl << c;
    return 0;
}

它仅适用于 100 个测试中的 70 个：(

你能帮我使它适用于所有测试吗？

标签： c++

解决方案

这只是整数溢出的问题。第一个实现是用 unsigned long long 实现的。它似乎有效，但未检测到一些溢出。

使用 __int128 执行了新的实现。此外，使用签名版本以便能够轻松检测溢出。

现在，对于介于 1 和 200 之间的 n，所有回文都被找到，除了 n = 196，它检测到溢出。

这是程序：

#include <iostream>

//using namespace std;

void print128 (__int128 a) {
    __int128 v64 = (__int128) 1 << 64;
    __int128 high128 = a / v64;
    __int128 low128 = a % v64;
    unsigned long long high =  high128;
    unsigned long long low =  low128;
    if (high > 0) std::cout << high;
    std::cout << low;
}

__int128 rev(__int128 a) {
    __int128  b = 0;
    while (a) {
    b = 10 * b + a % 10;
    a /= 10;
    }
    return b;
}

int main() {
    //std::ios::sync_with_stdio(0);

    int nerr = 0;
    int cmax = 100000;
    for (int n0 = 10; n0 <= 200; n0++) {
        bool overf = false;
        int c = 0;
        __int128  nrev;
        __int128 n = n0;
        while ((n != (nrev = rev(n))) && (c < cmax)) {
            if (nrev < 0) overf = true;
            n = n + nrev;
            if (n < 0) overf = true;
            c++;
        }
        std::cout << "n = " << n0 << " ";;
        if ((c == cmax) && !overf) {
            std::cout << " ERR0R\n";
            nerr++;
        } else if (overf) {
            std::cout << " OVERFLOW\n";
            nerr++;
        } else {            
            std::cout << " palym = ";
            print128 (n);
            std::cout << "  c = " << c << "\n";
        }
    }
    std::cout << "Nbre of errors = " << nerr << "\n";
    return 0;
}

问题是“196案怎么办？” 我们不知道是否存在解决方案，即是否存在收敛。此外，如果它收敛，我们不知道回文的大小可能是多少。尝试使用int更多位可能是一场漫长的比赛。更好的方法是实现一个专门的 int 类型来适应这个问题，即一个 int 向量，每个 int 介于 0 和 9 之间。对于这个算法，我们只需要执行两个操作，计算回文和加法。计算回文将是微不足道的，反转向量的元素（忽略第一个零），并且加法将很容易实现。此外，这样的添加将很容易检测到溢出。最后但并非最不重要的一点是，向量的大小可以针对每个n值进行调整，直到给定限制。

编辑：在评论中，Mark Ransom 提供了关于 Lychrel 数字的维基百科页面的链接，即算法不会收敛的数字。196是最低和最著名的“候选人莱克瑞尔”号码。196 是这样一个数字，只是推测而不是证明。已经进行了数十亿位数的实验，但没有找到这个数字的收敛性。

推荐阅读