4

我认为这个问题很简单，可以理解。为了更清楚，我举个例子：

在 2 位回文列表中，第 7 个回文是 77（第 1 个是 11，第 2 个是 22，依此类推）。

显然存在蛮力解决方案，但效率不高。

谁能建议我一些更好的解决方案来解决这个问题？

4

5 回答 5

12

首先，我们可以简化问题，因为我们只需要查看数字的前半部分（如果有奇数位，则四舍五入）。我将称第一组数字为有效数字，其余为非有效数字。

这是因为非有效数字必须与有效数字匹配（相反）。不可能有另一个具有相同前导有效数字和不同非有效数字的回文数。有效数字决定了整个回文数。

现在，我们只需要想出一个算法来生成第 n 个有效数字。如果我们允许前导零，这会更容易，所以我们将提出允许前导零的算法，然后调整算法。

前几个回文（有效数字）将是：

  • 1：0000
  • 2：0001
  • 3：0002
  • ...
  • 100：0099

所以我们可以通过求 (n-1) 的十进制表示来找到第 n 个数的有效数字。

为了在不允许前导零时调整算法以使其工作，我们将从一开始作为前导数字：

  • 1：1000
  • 2：1001
  • 3：1002
  • ...
  • 100：1099

这归结为找到 (n-1) + 1000 = n + 999 的十进制表示并扩展为完整的回文：

示例：找到长度为 9 的第 113 个回文。

  • 确定要查看的位数：向上取整（9 / 2）= 5 --> 只查看前 5 位数字。
  • 查找要添加的数字以消除前导零：10^(5-1) = 10000
  • 使用公式：(113 - 1) + 10000 = 10112
  • 扩展为回文：101121101

附带说明一下，该算法也可以推广到查找任何有序符号集（或字母表）的第 n 个回文。

广义算法：

给定：找到回文数n，回文有m个符号作为数字，有p个符号（十进制的 10 个符号）

  • 令q = 上限（m / 2）
  • 设偏移量= p ^ ( q - 1)
  • 设数字= ( n - 1) +偏移量
  • 让答案是数字展开为回文
于 2012-08-12T21:58:11.303 回答
5

前几个 7 位回文是：

  • 1000001
  • 1001001
  • 1002001
  • 1003001
  • ...
  • 1009001
  • 1010101
  • 1011101
  • ...

我认为很容易从第n个 m位回文的模式中看出......

于 2012-08-12T21:05:58.600 回答
2

当位数为偶数时，只需从 100..0 开始取第 n 个位数减半的数，其中长度为位数的一半。回文就是这个数字，后面跟着它的镜子。

对于奇数位数，只需取该数字一半的上限，然后以相同的方式从 100...0 开始计数。然后回文是这个数字，后面跟着它的镜像，去掉了第一个数字。

第 65 个 10 位数字：

65 + 9999 = 10064

1006446001

第 10298 个 13 位数字：

10298 + 999999 = 1010297

1010297920101

于 2012-08-12T21:27:56.577 回答
0

对于两位数的回文数，两个连续的回文数之差是 11。

于 2012-12-06T09:56:56.660 回答
-3

就像是：

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
using namespace std;

void reverseString(char *dest,char *src){
 char *iter=src;
 while (*iter) iter++;
 while (iter!=src){
  iter--;
  *dest=*iter;
   dest++;
 }
 *dest=0;
}

char *pal(int n,int len){
  char *tmp=new char[len/2+2];
  char *out=new char[len+1];
  sprintf(out,"%i",n+int(pow(10.0,(len+1)/2-1))-1);
  reverseString(tmp,out); //copy reversed out into tmp
  strcat(out,tmp+len%2);
  delete []tmp;
return out;
}

int main(){
 cout<<pal(4,7)<<endl;
}
于 2012-08-12T21:14:40.607 回答