4

質問は理解できるほど単純だと思います。より明確にするために、例を示します。

2桁のパリンドロームのリストでは、7番目のパリンドロームは77です（1番目は11、2番目は22など）。

明らかにブルートフォースソリューションは存在しますが、効率的ではありません。

誰かが私に問題を解決するためのより良い解決策を提案できますか？

4

5 に答える 5

12

まず、桁の前半だけを見る必要があるため、問題を単純化できます（桁数が奇数の場合は切り上げます）。最初の数字のセットを有効数字と呼び、残りの数字を非有効数字と呼びます。

これは、有効数字以外の数字が有効数字と一致する必要があるためです（逆）。同じ先行有効数字と異なる非有効数字を持つ別の回文数を持つことはできません。有効数字は、回文数全体を決定します。

ここで、n番目の有効有効数字を生成するアルゴリズムを考え出す必要があります。これは、先行ゼロを許可した方が簡単なので、先行ゼロを許可するアルゴリズムを考え出し、アルゴリズムを微調整します。

最初のいくつかの回文（有効数字）は次のようになります。

  • 10000
  • 2：0001
  • 3：0002
  • ..。
  • 100：0099

したがって、（n-1）の小数表現を見つけることにより、n番目の数値の有効数字を見つけることができます。

先行ゼロを許可しない場合に機能するようにアルゴリズムを微調整するには、先行ゼロとして1から始めます。

  • 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進数で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

2桁のパリンドロームの場合、2つの連続するパリンドロームの差は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 に答える