Задачка на сообразительность.

ааа, доперло. в качестве случайной он взял да и взял 5 штоле? нда, ниосилил сходу...

>ааа, доперло. в качестве случайной он взял да и взял 5 штоле?

СВ может принимать 5 (пять) значений. Всё, больше ничего не требуется.

вызываем 7 раз этот генератор. нумеруем эти вызовы.

если только один раз возвращается единица, то берем номаер этого генератора.

если единица не выпала, или выпала больше одного раза, повторяем

Вот так покатит. Смущает только время работы такой функции, но по-номальному вряд ли решить.

ну есть еще идея складыва нное количество раз результат этого генератора. Только тут проблема в том, что надо найти 7 равновероятных чисел, на бумаге это слишком муторно, но в принципе можно. Ну и занумеровать эти числа от 1 до 7

Неа. В действительности, генератор случайных чисел генерит случайные биты. :) Отсюда и будем плясать.

Сначала кастрируем наш генератор, чтобы он равновероятно выдавал 0 или 1. Это делаем так. Если наш генератор выдал 0, 1 или 2, считаем, что он выдал 0. Если он выдал 3, 4 или 5, считаем, что он выдал 1.

Кастрированный генератор с вероятность. 1/2 выдает 0 или 1, согласны? Это будем интерпретировать, как рендомный бит.

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

только пары 1 2 и 4 5 , нуля то нет, а 3 просто выбрасываем

как Ъ программисты надо разбить задачу из [1,5] -> [1,7] на 2 шага:

[1,5] -> [1,2] -> [1,7]

проще решать, потянтее кодить ;)

>> только пары 1 2 и 4 5 , нуля то нет, а 3 просто выбрасываем

Если одно чисто из пяти выкинуть, то либо у нас нарушается равномерность распределения, либо время работы алгоритма становится неопределённым.

равномерность сохраняется, время... есть другие варианты? время в бесконечность не уйдет, так что нормально)

>> время в бесконечность не уйдет, так что нормально)

На самом деле алгоритм будет работать сколько угодно. Может завершиться мгновенно, а может через 100 лет. Как повезёт =).

> время в бесконечность не уйдет, так что нормально)

Даже если время уйдет в бесконечность, но будет счетно, то все хорошо

угу, с такой же вероятностью, что все молекулы воздуха улетят из твоей комнаты.

>> угу, с такой же вероятностью, что все молекулы воздуха улетят из твоей комнаты.

Всё равно это плохое решение. Подозреваю что алгоритм с константным временем работы в данном случае вообще не существует... Хотя кто знает...

> Всё равно это плохое решение. Подозреваю что алгоритм с константным временем работы в данном случае вообще не существует... Хотя кто знает...

+inf чем не константа?

>> +inf чем не константа?

При чём тут это? Ты бы в своей программе стал использовать алгоритм который бы зависал на неопределённый срок?

И вообще, не нужно постить такое на ночь глядя =).

> Ты бы в своей программе стал использовать алгоритм который бы зависал на неопределённый срок?

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

> Внутри программы можно вызывать ГСЧ сколько угодно раз, естественно.

Вызывай семь раз, суммируй, результат дели на пять (с нормальным округлением).

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

>Ты бы в своей программе стал использовать алгоритм который бы зависал на неопределённый срок?

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

хохо, сумма равномерных распределений стремится к нормальному, теорвер надо было учить, быдлокодер

вы спрашивали кто такой быдлокодер? вот он

> хохо, сумма равномерных распределений стремится к нормальному,

В пределе?

Нормированная сумма, о светоч знаний.

>Подозреваю что алгоритм с константным временем работы в данном случае вообще не существует...

Точнее не существует алгоритма, который бы гарантированно запускал генератор ограниченное число раз (обозначим его за N). Задача фактически сводится к тому, чтобы расскидать 5^N элементарных равновероятных исходов на 7 одинаковых кучек, что невозможно по теореме об однозначном разложении на простые множетели.

>В пределе?

>Нормированная сумма, о светоч знаний.

лол какой, это подразумевается по умолчанию

правильно ли это утверждение оно или нет, оно не означает невозможность создания подобного генератора, только лишь невозможность реализовать его подобным способом.

>правильно ли это утверждение оно или нет, оно не означает невозможность создания подобного генератора, только лишь невозможность реализовать его подобным способом.

Это еще почему?

Запоминать кенератор все равно ничего не может. Сгерерированное число не должно зависить от предистории. Если он чтото замопинает, то его можно заменить эквивалентным, который сначала генерит по старому алгоритму, затем пересчитывает запомненную инфу так, если бы исходный (тот который от 1 до 5) генерил до этого только еденички.

Если генератор иногда запускает исходный не N раз, а меньше, то тогда его можно заставить перед выдачей ответа запускить его недостающее кол-во раз в холостую.

Вот таким вот нехитрым образом и получается пространство из 5^N элементарных событий.

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

Mille pardons, madame. Преподавательская привычка к буквоедству.

Да по модулю 7 возьмите, ема-е!

Складываются два случайных числа, 1, 2 и 10 отбрасывается. Из результата вычитается 2

чаще всего будет 6 выпадать.

Без грязного хака с неопределенным временем работы и ненулевой вероятностью вечного никак.

P.S. Но можно сделать произвольно маленькое отклонение от идеально-равномерного распределение.

>Без грязного хака с неопределенным временем работы и ненулевой вероятностью вечного никак.

А я, похоже, знаю как сделать его определённым:)

>> А я, похоже, знаю как сделать его определённым:)

Выкладывай =).

> А я, похоже, знаю как сделать его определённым:)

давай выкладывай, посмотрим какой результат будет выдавать твоя система если все вызовы за "определённое время" покажут одинаковое число

Элементарная задача

m=0; for(i=0,i<7,i++){ m+=rand(1,5)*(10^i); } result = m%7+1;

>Элементарная задача

Элементарная ошибка ...

В чем?

(1..5) rep 7 и (6..0) rep 7 не симметричны относительно mod 7

s5=2.999981
13999888 14000069 14000121 14001334 13998588
s7=4.001658
142138 143193 143132 143108 142414 142869 143146 

нечетная строка среднее арифметическое, четная количество выпавших
 позиций. Соотв для исходного генератора от 1 до 5 и полученного
 через :

for(int i = 0; i < count; ++i){
        int d = 0;
        for(int j = 0; j < s; ++j){
            r5 = rnd();
            ++a5[r5-1];
            s5 += (double)r5;
            d += r5*5^i ;
        }

        r7 = d % 7 +1;
        ++a7[r7-1];
        s7 += (double) r7;
    }

от 1 до 7, вроде как все совпадает?

Выше я писал, что можно до сколь угодно малой погрешности довести, но 100% не будет.

100% не будет по определению.

Долго думал, пока получилось не очень:)

>ну есть еще идея складыва нное количество раз результат этого генератора.

Ясное дело, есть. Только нифига толкового придумать не получается.

>Только тут проблема в том, что надо найти 7 равновероятных чисел

Ага, а эти семь чисел, очевидно, должны получатсья сочетанием каких-то других. То есть их количество не может являться простым числом (см 7).

Ну либо отбрасывать "лишнее", как ты уже предложил.

>Сначала кастрируем наш генератор, чтобы он равновероятно выдавал 0 или 1. Это делаем так. Если наш генератор выдал 0, 1 или 2, считаем, что он выдал 0. Если он выдал 3, 4 или 5, считаем, что он выдал 1.

Сразу в мусор. Генератор не даёт нуля. Дальше можно не читать.

> Особенно про "от 0 до 1" и "равномерно" с учётом того, что представимых в машинном виде чисел на отрезке [0,1] конечное число и разбросаны они там достаточно хитрым образом.

ИХ там (0,1) МНОГО.