🎳 💮 📀 Go Palindromes 3を検索 💝 📹 💃🏻

前の部分で得られた一見良好な結果が「極大値」のみであることが判明した後、しばらく問題を放棄しました。条件を思い出させてください：

「10進数585は2進数で1001001001です。それは両方のベースでパリンドロームです。 n番目の回文数を見つけます。または、ロシア語で：「2進数システムの10進数585は1001001001のように見えます。両方の番号システムの回文です。 n番目の回文を見つけます。

しかし、根本的に異なる計算の複雑さを備えた、はるかに高速なアルゴリズムの存在自体は気にせず、最終的には分析に戻りました。

最終的に、アルゴリズムはそれほど複雑ではありませんでしたが、私の意見では、非常に美しいものでした。

元の説明と実装ではプレフィックスツリーを使用していますが、私の意見では、アルゴリズムの数学を少し深く理解することで、より単純で高速な構造を扱うことができます。例を使用してアルゴリズムを解析するのが最善だと思います。

幅が8の 10進数パリンドロームの中からバイナリパリンドロームを探します。元の回文は正確に9000です：10000001から99999999まで。

次に、2セットの数値を取得します。

A [ 90 ] = { 10 0000 01、11 0000 11、12 0000 21 、...、 98 0000 89、99 0000 99 }
B [ 100 ] = { 00 0000 00、00 0110 00、00 0220 00 、...、 00 9889 00、00 9999 00 }

これらのセットを正式に説明すると、セットAは幅8の 10進パリンドロームのサブセットであり、その中央の4桁はゼロであり、セットBは0 、幅2の10進パリンドロームのセット、 10 ³倍、幅4の 10進パリンドロームのセット、 10 ² 。

非公式の場合、セットAはすべての可能な「エッジ」であり、セットBはすべての幅が8の 10進数回文の「中間」です。明らかに、幅8のすべての10進パリンドロームのセットは、セットAおよびBの要素のすべてのペアワイズ合計のセットです。

for each (a in A) { for each (b in B) { palindrome = a + b; } }

さらに、簡潔にするために、「セットAの要素」の代わりに「a」を使用し、「セットBの要素」の代わりに「b」を使用します。

次に、両方のセットの要素を2進数システムに変換します。

A

10000001 100110 001001011010 000001

11000011 101001 111101100011 001011

12000021 101101 110001101100 010101

...

98000089 101110 101110101110011 011001

99000099 101111 001101001111100 100011

00000000 000000

00011000 10101011 111000

00022000 101010111 110000

...

00988900 11110001011011 100100

00999900 11110100000111 011100

私はすべてのaに6桁の上位および下位桁を選択し、すべてのbに6桁の下位桁を選択しました。幅6は偶然選択されませんでした-これは最大2で、「エッジ」の幅A = 10 ²を超えません。

ここで、各aを取得し、bを追加することによってそれから形成されるすべての回文が共通しているものを確認します。しかし、共通しているのは、それらがすべてそれ自体と次の要素Aの間の間隔にあるということです。

たとえば、a = 10000001の場合、それから形成されるすべての10進パリンドローム{10000001、10011001、10022001、...、10988901、10999901}は間隔[10000001、11000011）にあります。

つまり、a = 10000001から形成される10進パリンドロームはすべて、次の6桁の2進数でのみ開始できます。

100110-最初の2進数a = 10000001

100111

101000

101001-最初の2進数a = 11000011

したがって、バイナリパリンドロームであるために、これらの10進数パリンドロームはすべて、最初のバイナリ桁の逆順列でのみ終了できます。

100110-> 011001

100111-> 111001

101000-> 000101

101001-> 100101

そして、a = 10000001自体が2進数000001で終わる場合、考えられるすべてのbのうち、2進数で終わるものにのみ関心があります。

011001-000001 = 011000

111001-000001 = 111000

000101-000001 = 000100

100101-000001 = 100100

そのようなbについてのみ、10000001 + bがバイナリ回文であるかどうかを確認する必要があります。

このアプローチを使用して、区間[1、N]のベースBASE ₀ 、BASE ₁で回文を見つけるアルゴリズムは、次のように記述できます。

[1の各幅Wに対して、BASE _0の桁数N]

BASE ₀を使用してセットAおよびBを生成します。 エッジ幅AW _A = O（W / 4）、W A≥W _B

アイテムAとBをBASEに変換します₁

BASE _1の最後の桁でバスケット別にアイテムBをソートします

セットAの各a

可能な初期数字a + bのセットの各Xについて

で終わるすべてのbについて（Xはaの終了数字です）

a + bがBASE _1の回文であるかどうかを確認します

残念ながら、アルゴリズムの計算の複雑さを厳密に証明する方法を忘れてしまったので、いくつかの考慮事項を示します。

セットAおよびBにはO（N ^1/4 ）要素が含まれます。
各aについて、平均して、最大でXのBASE ₀バリアントがあります。

（最初に、BASE _{1で対象と}なる最初の数字の幅を選択して、結果の数値がBASE ₀ ^{W _A以下}になり、最大（A）がBASE ₀で最小（A）より大きくなるようにします。）
各Xについて、平均で、 BASE _1個の異なるbsのみがチェックされます。

（Xは均等に分布し、 BASE _1の最後の桁aとはほとんど相関しません_。したがって、bを持つ各バスケットは均等に選択され、 BASEにはそのようなバスケットがbの₁倍しかありません。）
回文の確認にはまだO（log（N））が必要です。

一般的に、アルゴリズムの計算の複雑さはO（N ^1/4 * log（N）* BASE ₀ * BASE ₁ ）であると仮定します。

このアルゴリズムの最初の実装は、数桁速く予測できました。最適化に少し時間を費やした後、計算時間を0.01秒強にし、以前のアルゴリズムよりも1000倍高速にしました。この結果は最終的に私を満足させたが、 2 ⁶⁰より大きい数でそれをテストしたいという欲求が非常に自然に生じた。この時点で、Encyclopedia of Integer Sequences で興味のあるシーケンスをすでに発見していました。二重パリンドロームのリストには122個のメンバーがあり、そのうち最大のものは131ビットで構成されていました。これは印象的でしたが、対数複雑度アルゴリズムをまだ誰も考え出していないことを間接的に示しました。

課題は深刻でした-そのような結果を得た人々がアルゴリズムの開発に多大な努力を注いだことに疑いはありませんでした、そして、彼らは確かにその後の検索に数日と数週間のマシン時間を費やす準備ができていました。したがって、少なくともアルゴリズムを繰り返すのに必要な時間を概算することにしました。

2 ^131/2 ⁶⁰ = 2 ⁷¹

2 ^{71 * 1/4} < 2 ¹⁸ = 262144

2 ^60の制限に0.01秒が必要な場合、私のアルゴリズムは約1時間でこのタスクに対処することになっていることがわかりました！私はキャッチを感じましたが、挑戦はすでに受け入れられました。

継続する。

Go Palindromes 3を検索

More articles: