Получите самое большое число среди нескольких целых чисел без использования массивов

Question

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: Достаточно теоретический вопрос здесь, не ищите правильно answere, просто прося о каком-то вдохновении!

Рассмотрим это:

Функция называется повторно и возвращает целые числа, основанные на семена (то же семян возвращает то же целое число). Ваша задача - выяснить, какое целое число возвращается чаще всего. Легко, правда?

Но: Вам не разрешено использовать массивы или поля для хранения возвращаемых значений указанной функции!

Пример:

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 раз.

Я знаю, что это можно легко решить, используя двумерный список для хранения результатов и событий. Но представьте на минуту, что вы не можете использовать какие-либо массивы, списки, словари и т. Д. (Возможно, потому, что система с запущенным кодом имеет такую ​​ограниченную память, что вы не можете хранить достаточно целых чисел сразу или потому, что ваш доисторический язык программирования не имеет понятия коллекций).

Как найти mostFrequentNumber и occurencesOfMostFrequentNumber? Что делает magic() do ?? (. Из потому что вы не должны придерживаться примера кода Любые идеи приветствуются!)

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

Вывести гипотезу: Предположим, что распределение целых чисел является, например, нормальным.

Старт простой. Имеют две переменные

. N Число элементов, которые были прочитаны до сих пор

. M1 среднее значение указанных элементов.

Инициализировать обе переменные до 0.

Каждый раз, когда вы читаете новое значение x обновление N быть N + 1 и M1 быть M1 + (x - M1)/N.

В конце M1 будет равен среднему значению всех значений. Если распределение было Normal, это значение будет иметь высокую частоту.

Теперь улучшите вышеуказанное.Добавьте третью переменную:

M2 среднее значение для всех (x - M1)^2 для всех значений x.

Инициализировать M2 до 0. Теперь получите небольшую память, например, 10 элементов или около того. Для каждого нового значения x, что вы читаете обновление N и M1 как выше и M2 как:

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

На каждом шаге M2 является дисперсия распределения и sqrt(M2) его стандартного отклонения.

По мере того, как вы продолжаете, помните частоты только тех значений, которые были прочитаны до сих пор, расстояния до M1 составляют менее sqrt(M2). Для этого требуется использование некоторого дополнительного массива, однако массив будет очень коротким по сравнению с большим количеством итераций, которые вы будете запускать. Эта модификация позволит вам лучше угадать наиболее частое значение вместо простого ответа на средний (или средний), как указано выше.

---

UPDATE

Учитывая, что речь идет о идеи для вдохновения есть много места для рассмотрения и адаптации подхода я предложил какой-либо конкретной ситуации. Вот некоторые мысли

1. Когда я говорю предположить, что распределение Нормальное вы должны думать о нем, как: Учитывая, что проблема не имеет решения, давайте посмотрим, если есть какая-то качественная информация, которую я могу использовать, чтобы решить, какое распределение будет иметь данные. Учитывая, что алгоритм предназначен для нахождения наиболее частого числа, должно быть хорошо предположить, что распределение неравномерно. Давайте попробуем с Normal, Логнормального и т.д., чтобы увидеть, что можно узнать (подробнее об этом ниже).

2. Если игра полностью запрещает использование любого массива, то хорошо, следить только , скажем, 10 номеров. Это позволит вам подсчитать появление 10 лучших кандидатов, что даст больше уверенности в вашем ответе. При этом выбирайте своих кандидатов по теоретической наиболее вероятной стоимости в соответствии с распределением вашей гипотезы.

3. Вы не можете использовать массивы, но, возможно, вы можете прочитать последовательность чисел два или три раза, а не один раз. В этом случае вы можете прочитать его один раз, чтобы проверить, хороша ли или нет ли гипотеза о его распределении. Например, если вы вычисляете не только дисперсию, но и асимметрию и эксцесс, у вас будет больше элементов для проверки вашей гипотезы. Например, если первое чтение указывает на то, что есть некоторая предвзятость, вы могли бы использовать Логнормальное распределение вместо и т.д.

4. Наконец, в дополнение к предоставлению приблизительный ответ вы могли бы использовать информацию, собранную в ходе чтение для оценки интервала доверия вокруг вашего ответа.