私は最近、創造的なベースでの数字の巧妙な使用に部分的または全体的に基づいている非常に多くのアルゴリズムがあることに気付きました. 例えば：
私の質問は、直感や証明の重要なステップとして巧妙な数体系を使用するアルゴリズムが他にあるでしょうか? . このテーマについて講演をまとめることを考えているので、引き出さなければならない例が多ければ多いほどよい.
Chris Okasaki は、彼の著書Purely Functional Data Structuresに、「数値表現」について説明している非常に優れた章を持っています。基本的には、数値の何らかの表現を取り、それをデータ構造に変換します。フレーバーを与えるために、その章のセクションを次に示します。
蒸留された最高のトリックのいくつか：
また、その章の参考文献リストは次のとおりです。
「3 進数は、シェルピンスキー三角形やカントール集合などの自己相似構造を便利に伝えるために使用できます。」ソース
「2D ヒルベルト曲線の表現には 4 進数が使用されます。」ソース
「4 分の 1 の虚数のシステムは、1955 年にドナルド クヌースによって高校の科学の才能検索への提出で最初に提案されました。これは、虚数 2i をベースとして使用する非標準の位置の数のシステムです。数字の 0、1、2、3 だけを使用してすべての複素数を表します。」ソース
「ローマ数字は 2 進法です。」ソース
「2 と 3 以外のすべての素数は、2 と 3 を除いて、基数 6 で表されると、最後の桁として 1 または 5 を持つため、セナリーは素数の研究に役立つと考えられます。」ソース
「Sexagesimal (基数 60) は、基数が 60 の数字システムです。紀元前 3 千年紀の古代シュメール人に由来し、古代バビロニア人に受け継がれ、現在でも修正された形で測定に使用されています。時間、角度、および角度である地理座標。」ソース
等...
このリストは良い出発点です。
先日あなたの質問を読みましたが、今日は問題に直面しました。セットのすべてのパーティションを生成するにはどうすればよいですか？私が思いついた解決策、そして私が使用した解決策（おそらくあなたの質問を読んだため）はこれでした：
（p）パーティションが必要な、（n）個の要素を持つセットの場合、ベース（p）のすべての（n）桁の数字を数えます。
各番号はパーティションに対応しています。各桁はセット内の要素に対応し、桁の値は要素を配置するパーティションを示します。
それは驚くべきことではありませんが、きちんとしています。それは完全で、冗長性を引き起こさず、任意のベースを使用します。使用するベースは、特定のパーティショニングの問題によって異なります。
私は最近、0から2 n -1までの数値のバイナリ表現に基づいて辞書式順序でサブセットを生成するためのクールなアルゴリズムに出くわしました。これは、数値のビットを使用して、セットに選択する要素を決定し、ローカルで並べ替えます。それらを辞書式順序にするために生成されたセット。興味があれば、ここに記事を投稿します。
また、多くのアルゴリズムはスケーリングに基づいており（Ford-Fulkerson max-flowアルゴリズムの弱多項式バージョンなど）、入力問題の数値の2進表現を使用して、大まかな近似を段階的に完全な解に改良します。
正確には巧妙な基数システムではありませんが、基数システムの巧妙な使用法：ファンデルコルプト数列は、数値の基数n表現を逆にすることによって形成される低差異のシーケンスです。これらは、このような2次元ハルトン列を構築するために使用されます。
行列の乗算を高速化するための二重基数システムについて、漠然と覚えています。
ダブルベースシステムは、1 つの番号に対して 2 つのベースを使用する冗長システムです。
n = Sum(i=1 --> l){ c_i * 2^{a_i} * 3 ^ {b_i}, where c in {-1,1}
冗長とは、1 つの数値をさまざまな方法で指定できることを意味します。
Vassil Dimitrov、Todor Cooklev による記事「Hybrid Algorithm for the Computation of the Matrix Polynomial」を探すことができます。
私ができる最善の短い概要を提供しようとしています。
彼らは行列多項式を計算しようとしていましたG(N,A) = I + A + ... + A^{N-1}。
N がコンポジットG(N,A) = G(J,A) * G(K, A^J)であると仮定すると、J = 2 を適用すると、次のようになります。
/ (I + A) * G(K, A^2) , if N = 2K
G(N,A) = |
\ I + (A + A^2) * G(K, A^2) , if N = 2K + 1
また、
/ (I + A + A^2) * G(K, A^3) , if N = 3K
G(N,A) = | I + (A + A^2 + A^3) * G(K, A^3) , if N = 3K + 1
\ I + A * (A + A^2 + A^3) * G(K, A^3) , if N = 3K + 2
これらの方程式の一部が最初のシステムで高速であり、2 番目のシステムでより優れていることは "明らか" (冗談) であるため、 に応じて最適なものを選択することをお勧めしますN。しかし、これには 2 と 3 の両方に対して高速な剰余演算が必要になります。これが二重基数が登場する理由です。基本的に、それらの両方に対して剰余演算を高速に実行して、組み合わせたシステムを提供できます。
/ (I + A + A^2) * G(K, A^3) , if N = 0 or 3 mod 6
G(N,A) = | I + (A + A^2 + A^3) * G(K, A^3) , if N = 1 or 4 mod 6
| (I + A) * G(3K + 1, A^2) , if N = 2 mod 6
\ I + (A + A^2) * G(3K + 2, A^2) , if N = 5 mod 6
私はこの分野の専門家ではないので、より良い説明については記事を参照してください。
これは、「偽造コイン」の問題を解決するために3進数を使用することに関する良い投稿です（通常のコインのバッグから1つの偽造コインを検出し、バランスをできるだけ少なくする必要があります）。
RadixSort は、さまざまな基数を使用できます。 http://en.wikipedia.org/wiki/Radix_sort バケツソートのかなり興味深い実装。
文字列のハッシュ ( Rabin-Karpアルゴリズムなど) では、多くの場合、文字列が n 桁 (n は文字列の長さ、b は十分な大きさの選択された基数) で構成される基数 b として評価されます。たとえば、文字列「ABCD」は次のようにハッシュできます。
'A'*b^3+'B'*b^2+'C'*b^1+'D'*b^0
文字を ASCII 値に置き換え、b を 256 にすると、次のようになります。
65*256^3+66*256^2+67*256^1+68*256^0
ただし、ほとんどの実際のアプリケーションでは、結果の値は、結果を十分に小さく保つために、適切なサイズの数値を法として取得されます。
Exponentiation by squaring is based on binary representation of the exponent.
（Hackers Delightすべてのプログラマーが私の目に知っておくべき本）には、ベースとしての-2（はい、右負数ベース）や-1 + i（虚数単位sqrt（-1）としてのi）などの異常なベースに関する完全な章があります。ベース。また、私は最良のベースが何であるかを計算するのが良いです（ハードウェア設計の観点から、それを読みたくないすべての人のために：方程式の解はeなので、2または3で行くことができます、3は少し良いでしょう（係数2）の1.056倍優れていますが、技術的にはより実用的です）。
私の頭に浮かぶ他のことは、グレーカウンター（このシステムで1ビットの変更のみを数える場合、メタスタビリティの問題を減らすためにハードウェア設計でこのプロパティを使用することがよくあります）またはすでに述べたハフマンエンコーディングの一般化-算術エンコーディングです。
私は2進数をグレイコードに変換するためにこれが本当に好きです：http：//www.matrixlab-examples.com/gray-code.html
暗号化では、整数環 (剰余算術) と有限体が広範に使用されます。これらの操作は、整数係数を持つ多項式の動作に直感的に基づいています。
ベース2を使用する私のお気に入りの1つは、算術符号化です。アルゴリズムのハートが2進数で0から1までの数値の表現を使用するため、これは珍しいことです。
素晴らしい質問です。リストは確かに長いです。時間を伝えることは、混合ベースの単純なインスタンスです (日 | 時間 | 分 | 秒 | 午前/午後)
興味があれば、メタベースの列挙 n タプル フレームワークを作成しました。これは、基本番号付けシステムの非常に甘い構文糖衣です。まだリリースされていません。自分のユーザー名に電子メールを送信します (gmail で)。
AKSがそうかもしれません。