0

数値を文字列に変換し、その文字列を逆にして、両方の文字列が等しいかどうかを比較します。

上記のアルゴリズムを使用して回文を見つけています。

問題は、10^50 から 10^100 までの回文数を検出したいのですが、この関数に時間がかかりすぎることです。

これを行うためのより高速なアルゴリズムまたはヒントはありますか?

4

3 に答える 3

1

k 桁の回文は何個ありますか? では、k+2 桁の回文はいくつあるでしょうか? 回文数の再帰を書くことができることを見てください。

P(n) を n 桁の回文数と定義します。任意に、0 桁の回文が 1 つだけあると仮定すると、P(0) = 1 になります。

同様に、1 桁の回文が 9 つあると述べるのも論理的であるように思われるため、P(1) = 9 です。また、2 桁の回文は簡単に作成して数えることができるため、P(2) も 9 です。

3 桁の回文を生成できますか? これを行うには、ゼロ以外の数字をすべての 1 桁の回文に追加/先頭に追加します。これでは x0x の回文が抜けているので、それらも追加します。

P(3) = P(1)*9 + 1*9 = (P(1) + 1)*9

5桁の回文はどうですか？繰り返しますが、ゼロ以外の数字を小さい順序の回文に追加して先頭に追加します。しかし、回文内にゼロが必要な場合について心配する必要があります。したがって、x0p0x は x000x と同様に回文です。

P(5) = P(3)*9 + P(1)*9 + 1*9 = (P(3) + P(1) + 1)*9

(さらに一歩進んで、P(1) に関して P(5) を書くことができます。)

したがって、P(5) = 900 となります。このような単純な主張を常に検証することをお勧めします。これにより、何も見逃していないという確信が持てるようになります。それを MATLAB で行います。

n = 10000:99999;
D = dec2base(n,10);
isp = sum(all(D == fliplr(D),2))

isp =
   900

上記のロジックを外挿して 7 桁の回文を計算すると、次の式が得られます。

P(7) = P(5)*9 + P(3)*9 + P(1)*9 + 1*9 = (P(5) + P(3) + P(1) + 1)*9

これは、P(7) = 9000 であることを示唆しています。繰り返しになりますが、この主張は力ずくでテストできます。

n = 1000000:9999999;
D = dec2base(n,10);
isp = sum(all(D == fliplr(D),2))
isp =

        9000

したがって、n が奇数の場合、n 桁の回文を数えるのは簡単に思えます。n 桁の回文を数えることは、n であっても同じくらい簡単です。それらの関係を導き出します。

于 2013-04-13T14:55:50.470 に答える
1

これには、より「組み合わせた」アプローチをとる必要があると思います。これらすべての数値をブルートフォースで処理するのではなく (おそらく、今日のコンピューティング能力では実行できないでしょう...)、次のように段階的に考えてください。

桁数が与えられた場合、回文になる可能な組み合わせはいくつありますか?

まず、数字がどのように機能するかを理解するために、桁数の少ない数字を見てみましょう。

  • 2 桁の数字の場合、最初の数字を選択した場合、数字を回文にする場合は 2 番目の数字を同じにする必要があります。つまり、基数 10 では、10 個の選択肢 (00 を 2 桁として数えた場合) または 9 個の選択肢 (そうでない場合、より理にかなっています) があります。

  • 3 桁の数字の場合、1 桁目を選択すると 3 桁目が固定されます。020これにより、9 つの選択肢が得られます (たとえば、3 桁とは呼びません)。中央の桁はまだ空いているので、さらに 10 個の独立した選択肢が得られます (中央の桁は 0 になる可能性があるため)。回文の総数は 9*10 = 90 で与えられます。

  • 4 桁の数字の場合、1 桁目と 2 桁目を個別に選択でき、3 桁目と 4 桁目が固定されます。最初は非ゼロでなければなりませんが、その後はゼロで問題ありません。9*10 = 90 回文。

  • 5桁の数字の場合、1、2、3番目を独立して選択し、4番目と5番目が固定されます。最初は非ゼロで、残りは完全に自由です: 9*10^2 = 900 回文。

これを一般化する準備ができたと思いますよね？

一般的なアプローチ

上記で、偶数桁の数字の場合は数字の半分の数字を個別に選択でき、奇数桁の数字の場合は真ん中の数字も選択できることに注意しました。最初の桁を 0 にすることはできませんが、他のすべての桁を降伏させることができます。つまり、N桁のある数値の場合、回文の選択肢の数は
P = 10 * 9 ceil( N / 2 )-1です。これが機能するには、N / 2が浮動小数点除算でなければならないことに注意してください。N = 7 の場合、3.5 が必要なので、4 に切り上げて、中央の桁も選択できます。

具体的な問題

10^50 から 10^100 までの回文数を数えるには、もう 1 つ必要な情報があります。これらの数の桁数について知っていることです。10 50から 10 51までの数はすべて50 桁なので (そして 10 100は回文ではないので)、残りは非常に単純です。

カウントを提供する python スニペット:

import math

palindromes = 0
for n in range(50):
    palindromes = palindromes + 10**math.ceil((n+50)/2.0)*0.9

または、まったく同じことを行うワンライナーを使用します。

import math
sum(.9*10**math.ceil((n+50)/2.0) for n in range(50))

これは、ほぼ 10 100ではなく、50 回の反復をループするため、どのコンピューターでもまったく問題ありません。9*10 N-1 = 0.9*10 Nであることにも注意してください。

于 2013-04-13T14:01:56.647 に答える