ここでP

Question

の点の最大数を含む行を計算するプログラミングインタビューの要素からの問題である：

Pは、平面内のn個の点の集合とします。各点は整数座標を持つ。

一つアイデアが斜面からハッシュコードを計算することである：ここでP.

の点の最大数は、溶液からの引用である含む行を計算するための効率的なアルゴリズムを設計この線のy切片を二重の順序付けされたペアとして使用します。有限精度演算のため、異なるバケットに同一直線上にマップされる3つのポイントを持つことがあります。生成された均一な[0、1]乱数が[0.3,0.6]の場合、番号6が返されます。

より堅牢なハッシュ関数は、勾配とy切片を有理数として扱います。合理的なのは、順序付けられた整数のペアです：分子と分母。ハッシュ関数を適用する前に合理的な形式にする必要があります。 1つの標準的な形式は、分母を常に非負にし、分子に対して相対的に素数にすることである。 y軸に平行な線は特別な場合です。このような線については、y切片の代わりにx切片を使用し、1/0を傾きとして使用します。

私は理解していない部分はこれです：

私たちは、ハッシュ関数を適用する前に、標準的な形式に合理的を持参する必要があります。

ハッシュ関数を適用する前に合理的な形式にする必要があるのはなぜですか。

Answer 1

これらは（IMO）過度に正確です。それらは、有理数を、まったく別個の数として扱うのではなく、整列した整数の対として扱います。この定式化では、（1,2）と（3,6）は別々の有理数になります。 （1,2）と（3,6）は同じ有理数、すなわち（小数点で書くと）0.5であるという暗黙の仮定になります。

分母を非負にすると、（-1,2）と（1、-2）を同じ数として扱い、分母を分子に対して相対的に素数にすることは、 6）〜（1,2）