c# - 打印回文数字的更有效算法，它们对 2 的幂也是回文数字

Question

我正在寻找更有效的算法来打印回文数字(例如 1001)以及它们对 2 的幂 (1001 * 1001 = 1002001) 也是回文数字。在我的算法中，我认为我进行了不必要的检查以确定数字是否为回文。我该如何改进它？

在 [1000,9999] 范围内，我找到了这 3 个数字:1001、1111 和 2002。

这是我的算法:

for (int i = n; i <= m; i++)
{
    if (checkIfPalindromic(i.ToString()))
    {
        if (checkIfPalindromic((i * i).ToString()))
             Console.WriteLine(i);
    }
}

这是我判断数字是否回文的方法:

static bool checkIfPalindromic(string A)
{
    int n = A.Length - 1;
    int i = 0;
    bool IsPalindromic = true;

    while (i < (n - i))
    {
        if (A[i] != A[n - i])
        {
            IsPalindromic = false;
            break;
        }

        i++;
    }

    return IsPalindromic;
}

Answer 1

与其检查非常多的“回文”，不如只遍历回文可能更好。为此，只需遍历数字的前半部分，然后从中组成回文。

for(int half=10;half<=99;++half)
{
    const int candidate=half*100+Reverse(half);//may need modification for odd number of digits
    if(IsPalindrome(candidate*candidate))
        Output(candidate);
}

这将使您的程序 O(sqrt(m)) 而不是 O(m)，这可能会击败常数因子的所有改进。