この非常に興味深い質問に出くわしましたか？私は 3 億の SSN 番号 (9 桁の番号) を持っています
欠落している SSN 番号を見つけますか?
無制限のドライブ容量がありますが、RAM は 2MB しかありませんか?
2 に答える
3
要素が 1 つだけ欠落していると仮定すると..メモリの制約があるため、ファイルをメモリに部分的にロードする必要があるため、指定されたファイル 3*10pow(8)/2MB を分割し、以下のメソッドをファイルの一部に適用します (外部ソートから借用した手法)。この手法は、すべての要素の単純な XOR です。基本的な考え方はハミングコードから。1 から 2power(n-1) までのすべての要素を XOR すると、結果は zero になります。要素が欠落している場合、結果は欠落した数値になります。
多忙な方法では：1からnまでの自然数の算術和、つまりn（n + 1）/ 2を適用してから、1回のトラバーサルで指定された配列の合計を計算し、n（n + 1）/ 2の差を見つけることもできますと合計を取得しました。欠番を与える必要があります。10 億の合計は非常に大きな数です。
于 2012-09-18T06:48:58.587 に答える
2
最初に小さな問題を分析して、これを見てみましょう。9 つの一意の 1 桁の数字があり、欠落している 1 つを見つけようとしているとします。できることは、10 個の一意の 1 桁の数字を合計することです。
0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45
次に、持っている 9 つの数字を足し、差を引いて、欠けている数字を見つけることができます。同じ戦略を質問に適用できますが、可能であれば手作業で合計を求めたくないため、問題は合計を見つけることになります。
100 個の一意の 2 桁の数字の場合を見てみましょう。
最初の 10 個の数字 = 45 (上記のとおり)
次の 10 個の数字にはすべて追加の 10 + 1 桁の数値があり、結果は 145 になります。次の 10 個にはそれぞれ追加の 20 -> 245 があり、合計を持つ最後の 10 個の数字に到達するまで同様に続きます。これらをすべて足し合わせると 4950 になります。
では、桁数に関係するパターンを探してみましょう。
1 桁 = 45 (あまり進んでいませんが、検証する追加のデータ ポイントが得られます)
2 桁 = 4950
数字を加算する方法を考えてみましょう。最初に 2 桁のケースを見た方が簡単でしょう。
1 から 9 までの左端の数字を x としましょう。前の桁数の答えを 10 * に追加します (x -> 2 桁の解の場合、後で 1 つのゼロを使用します)。ここで、1 桁で見つけた答えを再び利用して、 10 * 10 + 20 * 10 + 30 * 10 + 40 * 10 + 50 * 10 + 60 * 10 + 70 * 10 + 80 * 10 + 90 * 10 = 10 * (10 + 20 + 30 + 40 + 50 + 60 + 70 + 80 + 90) = 100 * (1+2+3+4+5+6+7+8+9) = 100 * 45 = 4500. 次に、45 も 10 回あるので、米国 450。4500 + 450 = 4950。
ここで、再帰方程式に一般化します。
すべての n 桁の一意の数値の合計 =
1 (後ろに n 個のゼロ) * ans(n-1) + 1 (n-1 個のゼロ) * ans(n-1) + 1 (n-2 個のゼロ) * ans(n-2) ... 10 * 45 + 1 * 0
これでさらに因数分解が完了しましたが、明確にして、数学的な楽しみであなたの質問にも答えてくれることを願っています!
于 2012-09-18T06:36:07.117 に答える