[解決済み】2つの整数を1つにマッピングする、一意的かつ決定論的な方法
2022-04-04 03:37:06
質問
2つの正の整数A、Bがあるとする。この2つを組み合わせて1つの整数Cにしたい。
Cに結合する他の整数DとEは存在し得ない。 だから、加算演算子で組み合わせてもうまくいかない。例:30 + 10 = 40 = 40 + 0 = 39 + 1 連結もうまくいきません。例:"31" + "2" = 312 = "3" + "12"
この組み合わせ操作は、決定論的であるべきです(同じ入力で常に同じ結果を得る)。 そして は常に整数の正負どちらかの側で整数を生成する必要があります。
どのように解くのですか?
あなたは、双対的な
NxN -> N
マッピングを使用します。これらは、例えば、次のような場合に使用されます。
蟻継ぎ
. をご覧ください。
本PDF
の紹介は、いわゆる
ペアリングファンクション
. ウィキペディアでは、特定のペアリング関数、すなわち
カントールペアリング関数
:
3つの発言
- 他の方が明らかにしているように、ペアリング関数を実装するつもりなら、すぐに任意の大きさの整数(ビグナム)が必要だと分かるかもしれません。
- (a,b)と(b,a)のペアを区別したくない場合は、ペアリング関数を適用する前に、aとbをソートしてください。
-
実は、私は嘘をつきました。あなたが探しているのは双対的な
ZxZ -> N
マッピングを使用します。カントールの関数は非負の数に対してのみ有効です。しかし、これは問題ではありません。というのも、双対射を定義するのは簡単だからです。f : Z -> N
というように。- f(n) = n * 2 if n >= 0
- f(n) = -n * 2 - 1 if n < 0
関連
-
[解決済み] ソートされていない配列でバイナリサーチは使えるか?重複
-
[解決済み] 大きなӨ記号は具体的に何を表すのですか?
-
[解決済み] 0から9までのランダムな整数を生成する
-
[解決済み] Vimのマッピングコマンドであるremap, noremap, nnoremap, vnoremapの違いは何ですか?
-
[解決済み】ある整数が、値の集合がわかっている2つの整数(含む)の間にあるかどうかを判断する最速の方法
-
[解決済み】ソートアルゴリズムにおける安定性とは何ですか、なぜそれが重要なのですか?
-
[解決済み】ある点が2次元の三角形の中にあるかどうかを判断する方法は?[クローズド]
-
[解決済み】log(n!)=Θ(n-log(n))なのか?)
-
[解決済み】整数の流れから実行中央値を求める
-
[解決済み】HSLからRGBへの色変換
最新
-
nginxです。[emerg] 0.0.0.0:80 への bind() に失敗しました (98: アドレスは既に使用中です)
-
htmlページでギリシャ文字を使うには
-
ピュアhtml+cssでの要素読み込み効果
-
純粋なhtml + cssで五輪を実現するサンプルコード
-
ナビゲーションバー・ドロップダウンメニューのHTML+CSSサンプルコード
-
タイピング効果を実現するピュアhtml+css
-
htmlの選択ボックスのプレースホルダー作成に関する質問
-
html css3 伸縮しない 画像表示効果
-
トップナビゲーションバーメニュー作成用HTML+CSS
-
html+css 実装 サイバーパンク風ボタン
おすすめ
-
[解決済み] どちらが大きいですか?O(log*n)とO(loglog n)
-
[解決済み] ソートされていない配列でバイナリサーチは使えるか?重複
-
[解決済み] 再帰の複雑さ T(n) = T(n-1) + T(n-2) + C
-
[解決済み] O(log n)とは具体的にどういう意味ですか?
-
[解決済み] 深さ優先グラフアルゴリズムの時間複雑性【非公開
-
[解決済み】Redisに使用されている基礎的なデータ構造は何ですか?
-
[解決済み】2つの整数を1つにマッピングする、一意的かつ決定論的な方法
-
[解決済み】ssl証明書はどのように検証されるのですか?
-
[解決済み】スキップリストとバイナリサーチツリーの比較
-
[解決済み】円の円周上にある点を計算するには?