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

((rnd() << 1) || rnd()) >> 1

два раза вызываем ГСЧ, суммирумем результат, если он больше семи - повторяем до тех пор пока не будет меньше семи.

При суммировании не получится равномерного распределения.

А почему не брать просто сумму по модулю 7 (остаток от деления на 7, 0==7)?

мой ответ:

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

Следующий шаг.

т.к. 7 - 5 = 2, то, следует прибавить генератор от 1 до 5 умноженный на два к генератору 1 до 5. Ну или просто умножить на три.

Да, такой счетчик, если не будет работать бесконечно три раза - никогда не достигнет до значение 7 - 0.3

вобщем так думаю. критика и помои принимаются =)

гм, декремент первого rnd нужен исчо

Есть предложение в ответах обосновывать равномерность полученного результата, а то химичить с числами до получения 7 все могут :)

> следует прибавить генератор от 1 до 5 умноженный на два к генератору 1 до 5. Ну или просто умножить на три.

здесь имелось ввиду округление в меньшую сторону, т.е. 0.3 Но есть такая идея(и теорема должна быть тоже), что случайный сигнал от нуля до единицы в пределе сыммы усредняется до 0.5

по крайней пере так должно быть чисто из практических соображений.

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

>Есть предложение в ответах обосновывать равномерность полученного результата, а то химичить с числами до получения 7 все могут :)

7 - три младших бита. Генератор выдает равновероятно

001
010
011
101

т.е. не хватает

110
111

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

> естественно равно середине отрезка

середина отрезка от 1 до 5 это 2,5(ну или там какой коэффициент поставить). Умножаем на три верхний предел, и берем нижний. оба подставляем в два аргумента функции rand(min,max), полчуаем в пределе рандомное число от 1 до 7-ми(имхо вполне законно).

Предложу решение. Берем 2 реализации случайной величины. Всего возможно 5^2 = 25 различных значений. Разбиваем это чило на 7 групп по 3 пары. Это 21 вариант. Если в результате опыта выпали остальные 4, то генерим новую пару и вперед.

В общем случае нужно искать решение уравнения 5^n = m*7 в целых n и m, что невозможно для 5 и 7, очевидно.

запускаем ГСЧ 7 раз, результат суммируем и делим на 5

> прибавить к результату тем или иным способом.

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

Сейчас лень - завтра проверю все способы :) Если получится в эксперименте равномерное распределение, то будем считать что оно так :). В формализм не полезем.

>Вот этот шаг неочевиден.

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

Неравномерное распределение на выходе гарантировано.

PS: А вообще это одна из задач на собеседовании в MS. И на самом деле я бы за сборник таких задач денег-бы заплатил, если с решениями. Довольно развивает, а на собеседовании помогает еще и увидеть как человек думает.

>середина отрезка от 1 до 5 это 2,5

Нарисуй на бумажке в клеточку числовую ось и удивись :)

> Если в результате опыта выпали остальные 4, то генерим новую пару и вперед.

...и для любого сколь угодно большого T, с ненулевой вероятностью делаем больше T шагов.

> Берем 2 реализации случайной величины. Всего возможно 5^2 = 25 различных значений.

стоп, откуда? как я понимаю формулу C(n,k)=n!/((n-k)!k!)

Это означает число возможных сочетаний n элементов по k позициям.

т.е. если у тебя есть 12 пронуумерованных стульев, то 4-мя способами ты их можешь расставить промеж собой C(n,k)=n!/((n-k)!k!) число раз.

Но в данном случае ты говоришь следующее(поправь если я не прав в рассуждении):

Берем 2 реализации случайной величины. Всего возможно 5^2 = 25 различных значений. Что такое 5?

Предположим задачу: На материнской плате имеется 5 джамперов, каждый из которых имеет положение либо 1 либо 0. Вопрос, сколько возможно пунктов в описании к задаче, чтобы описать все возможные комбинации этих джамперов? Мой ответ 2^5

Предположим еще одну задачу, где на мамке есть всего два джампера, которые каждый из них может находиться в 5 разных положениях. Вопрос, сколькими способами можно описать такой пакетник джамперов? Мой ответ 5^2

Но исходя из этих двух задач следует, что 2^5 != 5^2 , хотябы из соображений четности.

Но ты вообще предполагаешь, что 5 это какаято случайная величина, но она как бы конкретна.

Не совсем понял комментарий, можно пояснить? Что такое Т?

ну да, да, да, от 0 до 5, я хотел изложить идею.

Генератор не может генерить равномерно, ибо это будет нифига не генератор случайных чисел :-)

в первом опыте может быть 1, 2, 3, 4 или 5. Во втором для каждой из этих величин может быть 1, 2, 3, 4 или 5. Итого 25 сочетании. Считаем, что (1,2) и (2,1) - это разные вещи.

Теорвер совсем не учил?

Перечитал исходный пост, приношу извинения. Первое слово "равномерно" там лишнее.

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

Домножь нацело и не парь мозга.

А, понял. Ну да, есть такое дело. На практике все-же вероятность довольно мала :). В любом случае получим решение в стиле MS :)

Сразу видно знающего человека.

Что и на что домножить?

Домножить на 7, разделить на 5 и округлить до ближайшего %)

Не теребите мне мозг. Нет таких генераторов.

Исходный генератор --- от 0 до 1 равномерно,
на его основе строятся все остальные,
в том числе {0,1,2,3,4,5} и {0,1,2,3,4,5,6,7}.

Предложенная задача достойна индуса.

Только быдлокодер будет делать
[0,1] => {0,1,2,3,4,5} => {0,1,2,3,4,5,6,7}
вместо
[0,1] => {0,1,2,3,4,5,6,7}

Шутка, разумеецо %)

>Предложенная задача достойна индуса.

сказано же - "из тестов M$"

Но в условии задачи именно такой генератор. И никто не гоаорил про комп. Может это у меня карточки с числами.

> Берем 2 реализации случайной величины. Всего возможно 5^2 = 25 различных значений.

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

А подмена задачи - это чисто по-русски?

Заменяем 1 на 0, 2 на 1 итд

Создаем число 0,abcdef..... в 5 системе счисления. Переводим в 7 систему счисления. добавляем к каждой цифре 1.

Получаем результат.

> Домножить на 7, разделить на 5 и округлить до ближайшего %)

Обоснуй, что будет равномерно.

> Что и на что домножить?

Голову на урановый лом. Слушай, ты же у нас умный и читать умеешь:

http://ru.wikipedia.org/wiki/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD...

А я бы забил хер на исходную программу и написал новую, благо условие задачи позволяет.

Чорт, пойду пива выпью, ЛОР стал нереально уныл, безнадёжен и скучен.

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

Да это типичная задачка на задротство: если чел будет ковырять - то в спецы, если пошлёт в х*й и заставит интервьюэра самого решать - то в боссы однозначно.

>> Берем 2 реализации случайной величины. Всего возможно 5^2 = 25 различных значений.

>стоп, откуда? как я понимаю формулу C(n,k)=n!/((n-k)!k!)

Вилфред последние мозги пропил. Глядите, дети, чего бывает.

Написано там всё правильно - 5х5=25. В букваре можно поглядеть, почему так.

> Исходный генератор --- от 0 до 1 равномерно, на его основе строятся все остальные

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

P.S. man 3 rand. Можно и в исходники заглянуть.

Вызываем два раза, получаем равномерное от 1 до 25 (пятеричная система, бла-бла-бла...) Если попали от 1 до 7 - возвращаем результат; если не попали - повторяем с самого начала.

>Генератор не может генерить равномерно, ибо это будет нифига не генератор случайных чисел :-)

Это ещё почему? Равномерно распределённая СВ - уже не случайная?

вот его цитата:

> в первом опыте может быть 1, 2, 3, 4 или 5. Во втором для каждой из этих величин может быть 1, 2, 3, 4 или 5. Итого 25 сочетании. Считаем, что (1,2) и (2,1) - это разные вещи.

я не понял, че чел сказал этим сообщением. что значит "(1,2) и (2,1) - это разные вещи". даогадывюсь конешно. но смысл загадки непонятен. может быть они имеет ввиду какуюннить хрень, которой научил его препод, и которая используется в какойннить ss18 . я уже к таким штучкам в последнее время изначально с интересом подхожу/

запустить 7 раз по [1,5], сложить и взять по модулю 7? или не то?

>запустить 7 раз по [1,5], сложить и взять по модулю 7? или не то?

Не то.

> я не понял, че чел сказал этим сообщением. что значит "(1,2) и (2,1) - это разные вещи". даогадывюсь конешно. но смысл загадки непонятен. может быть они имеет ввиду какуюннить хрень, которой научил его препод, и которая используется в какойннить ss18 . я уже к таким штучкам в последнее время изначально с интересом подхожу/

Это всё от телека у современной молодёжи, насмотрятся битв экстрасексов, а потом начинают дурные задачки сочинять, вместо кошерного бизнеса. Вот что я скажу. Забей, короче, лучше бизнес-проект продумаю, даю хинт: продажа кастомных дистров центоси и фряхи за деньги.