配列を使用せずにいくつかの整数の中で最も出現している番号を取得してください

Question

免責事項：ここで理論的な質問は、を探していない正確な答えて、ちょっとインスピレーションを求めて！

この検討：

機能繰り返し呼び出されると（同じシードが同じ整数を返す）種子に基づいて整数を返します。あなたの仕事は、最も頻繁に返される整数を見つけることです。十分に簡単ですね。

but：上記の関数の戻り値を格納するために配列やフィールドを使用することはできません！

例：次に

int mostFrequentNumber = 0; 
int occurencesOfMostFrequentNumber = 0; 
int iterations = 10000000; 

for(int i = 0; i < iterations; i++) 
{ 
    int result = getNumberFromSeed(i); 
    int occurencesOfResult = magic(); 
    if(occurencesOfResult > occurencesOfMostFrequentNumber) 
    { 
     mostFrequentNumber = result; 
     occurencesOfMostFrequentNumber = occurencesOfResult; 
    } 
} 

getNumberFromSeed()場合戻る2,1,5,18,5,6と mostFrequentNumberはとoccurencesOfMostFrequentNumberなければならない5ためなければなりません3回返されます。

これは、2次元のリストを使用して結果と発生を簡単に解決できることがわかっています。しかし、何らかの配列、リスト、辞書などを使用することはできないと考えてください（おそらく、コードを実行しているシステムのメモリが限られているため、一度に十分な整数を格納できないこともあるし、先史時代のプログラミング言語コレクションの概念はありません）。

どうすればmostFrequentNumberとoccurencesOfMostFrequentNumberが見つかりますか？ magic()は何ですか？ （。あなたがサンプルコードに固執する必要はありません原因のいずれかのアイデアは大歓迎です！）

EDIT：同じシードを返すよう私は、getNumber()で返される整数はシードを使用して計算する必要があることを追加する必要があります同じ整数（すなわち、int result = getNumber(5);）は、常に同じ値をresultに割り当てます。

Answer 1

さてさて、私はまともな解決策を自分自身を見つけた：

int mostFrequentNumber = 0; 
int occurencesOfMostFrequentNumber = 0; 
int iterations = 10000000; 
int maxNumber = -2147483647; 
int minNumber = 2147483647; 

//Step 1: Find the largest and smallest number that _can_ occur 
for(int i = 0; i < iterations; i++) 
{ 
    int result = getNumberFromSeed(i); 
    if(result > maxNumber) 
    { 
     maxNumber = result; 
    } 
    if(result < minNumber) 
    { 
     minNumber = result; 
    } 
} 

//Step 2: for each possible number between minNumber and maxNumber, count occurences 
for(int thisNumber = minNumber; thisNumber <= maxNumber; thisNumber++) 
{ 
    int occurenceOfThisNumber = 0; 
    for(int i = 0; i < iterations; i++) 
    { 
     int result = getNumberFromSeed(i); 
     if(result == thisNumber) 
     { 
      occurenceOfThisNumber++; 
     } 
    } 
    if(occurenceOfThisNumber > occurencesOfMostFrequentNumber) 
    { 
     occurencesOfMostFrequentNumber = occurenceOfThisNumber; 
     mostFrequentNumber = thisNumber; 
    } 
} 

私は認めなければならないが、これは、最小と最大の可能性に応じて、長い時間がかかる場合があります。しかし、配列を使わなければ動作します。

Answer 2

仮説を立ててください。整数の分布を、たとえばNormalとします。

簡単に始める。 2つの変数を持つ

Nこれまでに読み込まれた要素の数

前記要素の平均。

両方の変数を0に初期化します。

あなたがM1 + (x - M1)/NするN + 1とM1する新しい値x更新Nを読むたび。

最後にM1はすべての値の平均と等しくなります。分布がNormalの場合、この値は高い頻度になります。

上記を改善してください。第3の変数を追加してください：

M2これまでに読んだすべての値xのすべての平均値は、(x - M1)^2です。

M2から0に初期化します。今や、10という要素のような小さなメモリが得られます。あなたは上記のようにしてM2などNとM1更新読むごとに新しい値xについて：すべてのステップM2で

M2 := M2 + (x - M1)^2 * (N - 1)/N 

を配布し、sqrt(M2)その標準偏差の分散です。

距離がM1で、それまでに読み取られた値の頻度がsqrt(M2)未満であることを覚えておきます。これにはいくつかの追加配列を使用する必要がありますが、実行する反復の回数が多いため、配列は非常に短くなります。この変更により、単純に上記のように平均（または平均）に答えるのではなく、最も頻繁に価値の高い値を推測することができます。

---

UPDATE

これはたくさんの部屋は、私が任意の特定の状況に提案してきたアプローチを検討し、適応のためにそこにあるインスピレーションのための洞察についてであることを考えます。問題は何も解決していないことを考えると、私が決めるために使用できるいくつかの定性的な情報があるかどうかを見てみましょう。ここではいくつかの考えが

1. 私は配布は、あなたがと考えるべきでノーマルであることを前提と言うときですデータにはどのような分布がありますか。アルゴリズムが最も頻繁な数を見つけることを意図されているとすれば、分布が一様ではないと仮定するのは良いことです。さんが出て見つけることができるかを確認するなどノーマル、対数正規、としてみましょう（詳細は以下。）

2. をゲームは完全に任意の配列の使用を許可しない場合は、罰金のみを追跡します、10の数字を言う。これにより、10人の候補者の出現回数を数えることができ、あなたの答えにもっと自信を持てるようになります。これを行うにあたり、あなたの仮説の分布に従って理論的に最も可能性の高い値の周りの候補を選んでください。

3. あなたは配列を使うことはできませんが、おそらく1回ではなく2回または3回の数字のシーケンスを読むことができます。その場合、あなたはその分布についての仮説が良いか悪いかをチェックするためにそれを一度読むことができます。たとえば、分散だけでなく歪度と尖度を計算すると、仮説を確認する要素が増えます。最初の読み取りは、いくつかの偏りがあることを示している場合たとえば、あなたは、代わりなどを対数正規分布を使用することができます

4. 最後に、おおよその答えを提供することに加えて、あなたは中に収集された情報を使用することができるだろうあなたの答えの周りの信頼の間隔を見積もるために読書。