最も近い回文数を見つけるという、よくあるインタビューの質問の 1 つに出くわしました。入力が127の場合、出力は131になり、125の場合、出力として121が得られるはずです。
ロジックを考え出すことはできますが、91、911 などの特定のケースではロジックが失敗します。これらの入力では 99 、919 が得られますが、正しい出力は 88 と 909 です。
アルゴリズムの手順は次のとおりです。
これは実際には興味深い問題です。明らかに、これを単なる力ずく以上のものにするためにやりたいことは、最上位桁を使用し、それらを最下位桁の位置に配置して回文を形成することです。（回文とオリジナルの違いを「距離」と呼ぶことにします）
そのことから、数値の最下位半分は無視できると言うつもりです。これは、実際には問題ではないためです (距離を決定する場合は重要ですが、それだけです)。
抽象的な数字を取ります: ABCDEF. A、B、C、D、E、F はすべてランダムな数字です。繰り返しますが、D、E、F は、回文を決定するために必要ではありません。数字の前半を後半にミラーリングすることです。明らかに、逆にしたくはありません。そうしないと、より有効な数字を変更して、元の数字から大きく離れてしまいます。
したがって、回文は になりABCCBAますが、既に述べたように、これが常に最短距離であるとは限りません。ただし、「解決策」はまだ形式でXYZZYXあるため、変更している数字の「重要性」を最小限に抑えることを考えると、C (または真ん中の数字) を変更する必要があることを意味します。
一歩下がって、その理由を見てみましょう。ABCCBA
A、これは最も重要でない位置、つまり右端にあるためです。ただし、最も重要でないものを変更するには、最も重要なものを変更する必要があります。アウトAです。BのでC、最終的に選択した数字になります。では、より近い可能性のある数値を取得するために変更Cする必要があることがわかったので、境界について考える必要があります。ABCDEFは私たちの元の数でありABCCBA、最も近い回文ではない場合、何が考えられるでしょうか? 上記の少し回り道に基づいて、 を変更することで見つけることができますC。したがって、ABCDEFより大きい場合ABCCBAと より小さい場合の 2 つのケースがありABCCBAます。
ABCDEFより大きい場合はABCCBA、 に 1 を加算しCます。T = C+1これで number が得られましたABTTBA。したがって、それを確認するためにテストし、そうであれば、それが最も近い回文ABCDEF - ABCCBA > ABCDEF - ABTTBA
であることがわかります。ABTTBAC にこれ以上変更を加えると、私たちはますます遠ざかってしまいます。
ABCDEFまたは、が より小さい場合はABCCBAから 1 を引きますC。としましょうV = C-1。がありABVVBA、上記と同じようにテストします:ABCDEF - ABCCBA > ABCDEF - ABVVBAそして、同じ解決策が得られます。
トリックは、ABCDEFは常に と の間ABTTBAにありABVVBA、これらの数の間の他の回文は だけですABCCBA。したがって、ソリューションには3つのオプションしかありません。と比較ABCDEFするABCCBA場合は、2 のみを確認する必要があります。
これを任意のサイズの数値に適応させるのは難しくないと思います。桁数が奇数の場合は、単にABCBA、ABVBAなどABTBA...
あなたの例のように、911を取ります.
911 - 919して911 - 909したがって、これにより一定時間アルゴリズムが得られます:)
コメントで指摘されているように、これは最悪の場合は一定時間ではありませんが（おっと）、ブルートフォースアプローチよりも確かに優れています。
これはあなたが持っているもののようですが、それ以外の場合は小さなプログラミングエラーのように見えるので、うまくいけば問題を明らかにするために詳しく説明したいと思いました.