2つの要素を挿入した後に衝突が発生しない確率を計算するにはどうすればよいですか。答えは4/9ですが、4/9の様子がわかりません
質問する
395 次
2 に答える
1
これが適切なSOの質問であるかどうかはわかりませんが、ここに答えを示します。これは決して正当な数学的証明ではありませんが、機能します。
関数h（x）=（x ^ 2 + 1）mod3に対して、いくつかのサンプル値を入れましょう。
h（1）=（1 + 1）mod3 = 2mod3 = 2
h（2）=（4 + 1）mod3 = 5mod3 = 2
h（3）=（9 + 1）mod3 = 10mod3 = 1
h（4）= 17mod3 = 2
h（5）= 26mod3 = 2
h（6）= 37mod3 = 1
このパターンは、関数の性質（2乗および1の加算）により継続されます。
したがって、関数への入力が2と評価される可能性は（2/3）あり、1と評価される可能性は（1/3）あります。
2つの要素を挿入すると、衝突が発生する確率は、両方の入力が2と評価される確率に、両方が1と評価される確率を加えたものになります。これは次のとおりです。
（2/3）（2/3）+（1/3）（1/3）= 4/9 + 1/9 = 5/9
したがって、2つの入力が衝突しない確率は1-（5/9）です。
または4/9。
于 2013-03-08T20:55:19.873 に答える
0
そのパターンが成り立つ理由について少し背景を説明するために、すべての等価クラスmod 3、つまり{0、1、2}を検討してください。
もしそうならx mod 3 = 0、x^2 mod 3 = (x mod 3)(x mod 3) mod 3 = (0 * 0) mod 3 = 0分配法則によって、そうx^2 + 1 mod 3 = 1
もしそうならx mod 3 = 1、x^2 mod 3 = (x mod 3)(x mod 3) mod 3 = (1 * 1) mod 3 = 1そうx^2 + 1 mod 3 = 2
もしそうならx mod 3 = 2、x^2 mod 3 = (x mod 3)(x mod 3) mod 3 = (2 * 2) mod 3 = 1そうx^2 + 1 mod 3 = 2
それはまだ100％正式ではなく、枯渇による不格好な例ですが、このパターンが自然数和集合{0}に当てはまる理由がわかります。また、スタックでの数学の書式設定についてもっとよく知っていればよかったのですが。メタをヒットする時が来たとしましょう？:)
于 2013-03-08T21:38:05.483 に答える