ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Ещё один случайный конь
61 сообщений из 61, показаны все 3 страниц
  все  
Ещё один случайный конь
    #39927231
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
Поскольку тервер здесь хорошо заходит, то почему бы и нет? )

Есть рандомайзер, который может возвращать только 0 или 1, причем вероятность 1 равна P1 (вещественное от 0 до 1), ну а вероятность 0 равна соответственно 1-P1.

С его помощью, не пользуясь никакими другими генераторами случайных чисел, написать функцию, которая возвращает равновероятно одно из пяти чисел: 0, 1, 2, 3, 4.

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

иными словами, в кодинге примерно так
Код: javascript
1.
2.
3.
4.
5.
function getRandom01234(randomizer) {
    randomizer.init(P1); // задаем P1
    ...
    // можно использовать randomizer.getRandom();
}



использовать randomizer.getRandom() во время работы функции можно не более N раз, и надо придумать алгоритм с как можно меньшим N.

функция должна уметь правильно отработать даже одноразово, то есть не сохраняя какое-либо состояние между вызовами.
...
Рейтинг: 0 / 0
16.02.2020, 22:14
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927282
АСУ ТПшник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
АСУ ТПшник
Участник
Умножаем 1 2 3 4 5 на рандомайзер. Как то так.
Нули убираем по условию if ==0 бла бла бла.
Он же рандомайзер единицу выдает?
Ну вот и получается что может циферка появится случайно а может будет уничтожена нулем.
...
Рейтинг: 0 / 0
17.02.2020, 09:23
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927286
АСУ ТПшник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
АСУ ТПшник
Участник
Не не сработает. Но подход именно в умножении. Толи нуль толи не нуль.

Почему у меня опять мозг закипел? Сдается что опять задача с подковыркой додумай сам.
...
Рейтинг: 0 / 0
17.02.2020, 09:29
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927287
АСУ ТПшник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
АСУ ТПшник
Участник
Я специально проигнорировал 0 1 2 3 4. Можно от результата просто единичку отнять.
Вот этот нуль в множестве все портит и сбивает с единственно правильного пути юного падавана :D
...
Рейтинг: 0 / 0
17.02.2020, 09:38
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927294
АСУ ТПшник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
АСУ ТПшник
Участник
Хмм.. Рандомайзер тыкает на одну из пяти величин, потом прогоняем через нуль не нуль путем умножения.
Вот как его заставить при входных 0-1 на пять величин тыкать. У меня чего в голове не сходится- наглядная равномерность решений. Так-то просто умножать в цикле и все более менее случайною.
...
Рейтинг: 0 / 0
17.02.2020, 10:04
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927320
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Имя пользователя1,

задай P = 0.5
тогда будет равновероятно выходить да\нет

Подбираем такое k, что 2^k > N
генерим наши k битов, число из полученных битов находится в диапазоне от 0 до 2^k-1
если получилось число меньше N, то возвращам
если получилось число >=N генерим заново
...
Рейтинг: 0 / 0
17.02.2020, 10:50
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927328
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
kealon(Ruslan)
Имя пользователя1,

задай P = 0.5
тогда будет равновероятно выходить да\нет

Подбираем такое k, что 2^k > N
генерим наши k битов, число из полученных битов находится в диапазоне от 0 до 2^k-1
если получилось число меньше N, то возвращам
если получилось число >=N генерим заново
это противоречит условию
Имя пользователя1
использовать randomizer.getRandom() во время работы функции можно не более N раз, и надо придумать алгоритм с как можно меньшим N.


Нужен алгоритм, который гарантированно отработает не более чем за N использований. Для справки - можно управиться менее чем за 8
...
Рейтинг: 0 / 0
17.02.2020, 11:08
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927332
АСУ ТПшник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
АСУ ТПшник
Участник
Просто интересно. Судя по всему у вас уже есть решение. Вы его в конце обcуждения озвучите?
...
Рейтинг: 0 / 0
17.02.2020, 11:13
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927341
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
АСУ ТПшник
Просто интересно. Судя по всему у вас уже есть решение. Вы его в конце обcуждения озвучите?
решение есть, но, надеюсь, в этом топика народ сможет решить.
Если кому интересно узнать ответ, а искать его самостоятельно уже задолбало, то могу выслать под подписку о неразглашении ))
...
Рейтинг: 0 / 0
17.02.2020, 11:23
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927345
АСУ ТПшник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
АСУ ТПшник
Участник
Не не. Я просто с языковым барьером столкнулся. Мои изложения полной ерундой выходят? Задача в другом?
...
Рейтинг: 0 / 0
17.02.2020, 11:28
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927360
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
АСУ ТПшник
Не не. Я просто с языковым барьером столкнулся. Мои изложения полной ерундой выходят? Задача в другом?
задача именно в том, что написано в стартовом посте) никаких подвохов нет, всё сказано. Если что-то конкретно неясно, спрашивайте
...
Рейтинг: 0 / 0
17.02.2020, 11:49
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927376
АСУ ТПшник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
АСУ ТПшник
Участник
Ну смотрите.
авторЕсть рандомайзер, который может возвращать только 0 или 1, причем вероятность 1 равна P1 (вещественное от 0 до 1), ну а вероятность 0 равна соответственно 1-P1.

С его помощью, не пользуясь никакими другими генераторами случайных чисел, написать функцию, которая возвращает равновероятно одно из пяти чисел: 0, 1, 2, 3, 4.
Как мне кажется, равновероятно надо 0 или 1. Что тут писали уже 0,5 или ухищрения на эту тему.
Далее в цикле просто умножаем. Ноль или значение умножаемой цифры на выходе. Но раз в цикле то последовательность , скажем 32145. Уже псевдорандомайзер выходит. Надо раскидать циферки (их последовательность). Вот тут у меня затык. Как рандомайзером 0-1 это сделать.
...
Рейтинг: 0 / 0
17.02.2020, 12:15
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927379
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Имя пользователя1
Нужен алгоритм, который гарантированно отработает не более чем за N использований. Для справки - можно управиться менее чем за 8
фактически, при таких условиях не копить, не отсекать выходит нельзя
...
Рейтинг: 0 / 0
17.02.2020, 12:16
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927389
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
kealon(Ruslan)
Имя пользователя1
Нужен алгоритм, который гарантированно отработает не более чем за N использований. Для справки - можно управиться менее чем за 8
фактически, при таких условиях не копить, не отсекать выходит нельзя
да.
...
Рейтинг: 0 / 0
17.02.2020, 12:25
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927393
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
АСУ ТПшник
Ну смотрите.
авторЕсть рандомайзер, который может возвращать только 0 или 1, причем вероятность 1 равна P1 (вещественное от 0 до 1), ну а вероятность 0 равна соответственно 1-P1.

С его помощью, не пользуясь никакими другими генераторами случайных чисел, написать функцию, которая возвращает равновероятно одно из пяти чисел: 0, 1, 2, 3, 4.

Как мне кажется, равновероятно надо 0 или 1. Что тут писали уже 0,5 или ухищрения на эту тему.
Далее в цикле просто умножаем. Ноль или значение умножаемой цифры на выходе. Но раз в цикле то последовательность , скажем 32145. Уже псевдорандомайзер выходит. Надо раскидать циферки (их последовательность). Вот тут у меня затык. Как рандомайзером 0-1 это сделать.вероятность 1/2, разумеется, не подойдет.
но ведь мы можем поюзать генератор несколько раз. Очевидно, это будет больше одного раза, и даже больше двух.
...
Рейтинг: 0 / 0
17.02.2020, 12:30
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927395
АСУ ТПшник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
АСУ ТПшник
Участник
Запрос на подсказку - а ограничение в 0-5 принципиально? Думал тоже про двоичную систему, но ведь не там собака порылась?
...
Рейтинг: 0 / 0
17.02.2020, 12:34
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927410
АСУ ТПшник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
АСУ ТПшник
Участник
РндомайзерРезалт = вес циферки. Потом по весу выстраиваем и умножаем на 0 или 1. Както так. Вот не пойму чего - рандомайзер чего может выдавать ? Только 0 или 1? Не точность какая-то. Я бы сказал сознательное затуманивание исходной задачи. При чем тут подбор цифери P1? Ну дико искуственные условия же.
...
Рейтинг: 0 / 0
17.02.2020, 12:54
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927423
АСУ ТПшник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
АСУ ТПшник
Участник
Выставляем P1 равное единице и решаем совсем другую задачу. Но вот про вероятность непонятно все равно. Как может вероятность на 0-1 для отрезка 0-5 работать.
Точно искусственная задача. Со многими недосказанностями.
...
Рейтинг: 0 / 0
17.02.2020, 13:06
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927426
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
АСУ ТПшник
Както так. Вот не пойму чего - рандомайзер чего может выдавать ? Только 0 или 1? Не точность какая-то. Я бы сказал сознательное затуманивание исходной задачи. При чем тут подбор цифери P1?
рандомайзер может только 0 и 1

он работает как "монета со смещенным центром тяжести" - можно задать вероятность выпадения орла, отличную от 1/2. Выбор этой вероятности - тоже часть алгоритма, можно выбрать удобную для себя.
...
Рейтинг: 0 / 0
17.02.2020, 13:07
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927454
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
АСУ ТПшник
Как может вероятность на 0-1 для отрезка 0-5 работать.
ну, например, с помощью двух бросков обычной монеты (с вероятностью орла 1/2) можно выбрать один вариант из 4

а тут надо один из пяти
...
Рейтинг: 0 / 0
17.02.2020, 13:34
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927480
Механик
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Механик
Участник
Имя пользователя1,

Я так понял, при равномерности умножением мы получаем 0 в половине случаев. Не проще ли набирать искомое число двоично как прятизначное?
...
Рейтинг: 0 / 0
17.02.2020, 14:14
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927517
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
Механик
Не проще ли набирать искомое число двоично как прятизначное?
не понял идею
...
Рейтинг: 0 / 0
17.02.2020, 15:00
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927562
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Механик
Имя пользователя1,

Я так понял, при равномерности умножением мы получаем 0 в половине случаев. Не проще ли набирать искомое число двоично как прятизначное?

2^4 = 3*5 + 1
всегда будет остаток, а значит конечность нельзя гарантировать
...
Рейтинг: 0 / 0
17.02.2020, 16:42
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927572
SpringMan
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SpringMan
Гость
Кидаем наш рандом N раз (четное). Если количество "единичек" меньше чем p1*N, то считаем что нам вернулось 0, иначе 1 (вероятность должны быть 0.5 у каждого)
Повторяем 3 раза, в итоге у нас 3 числа 0 или 1. Эти 3 числа переводим из двоичной системы в 10ую.
Ну и как выбрать нашу N, пусть N = 10 ^ (min(1, abs(px/(1-px)))), где x = min(p1, 1-p1)
Топорно, но должно быть равномерно.
Вообще N можно по Стьюденту наверное выбрать для красоты
...
Рейтинг: 0 / 0
17.02.2020, 16:57
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927574
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Имя пользователя1
Поскольку тервер здесь хорошо заходит, то почему бы и нет? )

Есть рандомайзер, который может возвращать только 0 или 1, причем вероятность 1 равна P1 (вещественное от 0 до 1), ну а вероятность 0 равна соответственно 1-P1.

С его помощью, не пользуясь никакими другими генераторами случайных чисел, написать функцию, которая возвращает равновероятно одно из пяти чисел: 0, 1, 2, 3, 4.

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


Есть совсем тупой способ
1. Складываем n random-чисел.
2. Исходя из ЦПТ считаем что получили Гаусс, берем и обратную функцию распределения.
3. Получаем равномерное распределение и квантуем на 5 значений.
...
Рейтинг: 0 / 0
17.02.2020, 17:01
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927576
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Гипотеза.

Данная задача не имеет решения если P - рациональная несократимая дробь вида m/n.
...
Рейтинг: 0 / 0
17.02.2020, 17:07
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927583
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
так, господа, я наверно не совсем явно выразился.

Р1 не зафиксировано в условии. Его надо придумать самому.

Код: javascript
1.
2.
3.
4.
5.
6.
function getRandom01234(randomizer) {
    var P1 = ...; // тут константа или выражение, должно оказаться вещественное между 0 и 1
    randomizer.init(P1); // задаем P1
    ...
    // можно использовать randomizer.getRandom();
}
...
Рейтинг: 0 / 0
17.02.2020, 17:16
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927585
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
SpringMan
Повторяем 3 раза, в итоге у нас 3 числа 0 или 1. Эти 3 числа переводим из двоичной системы в 10ую.
эти 3 бита задают числа от 0 до 7, а надо от 0 до 4
...
Рейтинг: 0 / 0
17.02.2020, 17:17
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927589
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
Соколинский Борис
Имя пользователя1
Поскольку тервер здесь хорошо заходит, то почему бы и нет? )

Есть рандомайзер, который может возвращать только 0 или 1, причем вероятность 1 равна P1 (вещественное от 0 до 1), ну а вероятность 0 равна соответственно 1-P1.

С его помощью, не пользуясь никакими другими генераторами случайных чисел, написать функцию, которая возвращает равновероятно одно из пяти чисел: 0, 1, 2, 3, 4.

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


Есть совсем тупой способ
1. Складываем n random-чисел.
2. Исходя из ЦПТ считаем что получили Гаусс, берем и обратную функцию распределения.
3. Получаем равномерное распределение и квантуем на 5 значений.
можно чуть подробнее, в идеале с примером?
...
Рейтинг: 0 / 0
17.02.2020, 17:20
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927590
SpringMan
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SpringMan
Гость
Точно, затупил(
В итоге надо придумать p1 и правило, чтобы минимизировать N?
...
Рейтинг: 0 / 0
17.02.2020, 17:20
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927591
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
SpringMan
Точно, затупил(
В итоге надо придумать p1 и правило, чтобы минимизировать N?
да.
...
Рейтинг: 0 / 0
17.02.2020, 17:23
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927597
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Имя пользователя1
Соколинский Борис
пропущено...


Есть совсем тупой способ
1. Складываем n random-чисел.
2. Исходя из ЦПТ считаем что получили Гаусс, берем и обратную функцию распределения.
3. Получаем равномерное распределение и квантуем на 5 значений.
можно чуть подробнее, в идеале с примером?


1. Задаем P=0.5 (или любое другое, без разницы).
2. Складываем N - результатов генератора (S)
3. Получаем нормированное значение X=(S-NP)/SQRT(NPQ).
4. Получаем Y=G(X), где G-функция cтандартного нормального распределения.
5. Считаем, что У распределен равномерно. Если Y>0.8 - результат 5, Y>0.6 - 4 и т.п.

Можно в excel-е модель сделать, там стат. функции есть.
...
Рейтинг: 0 / 0
17.02.2020, 17:34
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927601
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Все знают как работает арифметическое сжатие?
...
Рейтинг: 0 / 0
17.02.2020, 17:42
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927603
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
Соколинский Борис
1. Задаем P=0.5 (или любое другое, без разницы).
ну для 0.5 это сделать точно не получится, да и для многих других P тоже
Соколинский Борис
2. Складываем N - результатов генератора (S)
N здесь должно быть как можно меньше. У вас какое получается?
...
Рейтинг: 0 / 0
17.02.2020, 17:48
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927617
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Копипащу википедию
Арифметическое кодированиеПусть имеется некий алфавит, а также данные о частотности использования символов (опционально). Тогда рассмотрим на координатной прямой отрезок от 0 до 1.

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

Теперь возьмём символ из потока и найдём для него отрезок среди только что сформированных, теперь отрезок для этого символа стал рабочим. Разобьём его таким же образом, как разбили отрезок от 0 до 1. Выполним эту операцию для некоторого числа последовательных символов. Затем выберем любое число из рабочего отрезка. Биты этого числа вместе с длиной его битовой записи и есть результат арифметического кодирования использованных символов потока.
...
Рейтинг: 0 / 0
17.02.2020, 18:13
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927626
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
Соколинский Борис
1. Задаем P=0.5 (или любое другое, без разницы).

Если P==0 или P==1 тогда входная последовательность будет давать константу и без хранения состояния (по условию задачи) выход тоже будет константой.
...
Рейтинг: 0 / 0
17.02.2020, 18:37
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927629
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Имя пользователя1
ну для 0.5 это сделать точно не получится, да и для многих других P тоже
Понятно что там как-то с ошибкой дискретизации нужно бороться.

Соколинский Борис
2. Складываем N - результатов генератора (S)
N здесь должно быть как можно меньше. У вас какое получается?[/quote] По идее, чем больше - тем лучше.
Считается что в случае исходно равномерного распределения ЦПТ выполняется при n>10.
...
Рейтинг: 0 / 0
17.02.2020, 18:46
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927630
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Пример пришлось зиповать, не пропускает
...
Рейтинг: 0 / 0
17.02.2020, 18:48
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927642
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
Соколинский Борис,

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

можно для совсем маленького N получить точные равные вероятности
...
Рейтинг: 0 / 0
17.02.2020, 19:50
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927648
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Имя пользователя1,
Скажем так: с ростом N они будут сходится к точным значениям. Насколько быстро - нужно считать, а мне неохота.
Предлагаю этот вариант рассматривать как стартап.
...
Рейтинг: 0 / 0
17.02.2020, 20:13
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927651
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
ок, понял)
...
Рейтинг: 0 / 0
17.02.2020, 20:28
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927657
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Давайте возьмем P=0.25, Q=0.75 соотв.

И возьмем независимые события A, B которые выпадают с вероятностью P.

И нарисуем что-то вроде таблицы истинности для A,B где:
- есть объединение событий
- пересечение
- частные случаи. A=true, B=false e.t.c.

Посмотрим на нее с "прищуром". Возможно обозначится желаемая нами "половинка".
Думаю найдем быстро.

И чуть позже возьем более сложный случай. Как я предлагал для рациональной вероятности P=3/5, Q=2/5.
И посмотрим на аналогичную табличку для дробей. Там будет конечно посложнее.
Такие-же рациональные вероятности объединений и пересечений. Но вторая
табличка интереснее с точки зрения например доказательства того сколько
надо бросить таких "сложных костей" чтобы получить требуемую нами "половинку"
с нужной точностью.

Как в численном методе.
...
Рейтинг: 0 / 0
17.02.2020, 20:39
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927661
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
mayton,

ну примерно так правильный вариант и нашелся) только сначала надо придумать правильный подход, с которым всё ищется быстро. Задача на идею, а не на перебор 100500 вариантов
...
Рейтинг: 0 / 0
17.02.2020, 20:59
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927663
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Возможно мы подойдем к параметризованной формуле Бернулли где P - известно и (m,n) мы просто
вычислим.
...
Рейтинг: 0 / 0
17.02.2020, 21:03
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927692
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Имя пользователя1
mayton,

ну примерно так правильный вариант и нашелся) только сначала надо придумать правильный подход, с которым всё ищется быстро. Задача на идею, а не на перебор 100500 вариантов
если p = a/m, b = m-a
то по идее, для удовлетворения условию задачи
многочлен (a + b) k должен разбиваться на 5 равных частей

что-то мне кажется, что таких чисел нет, хоть интуиция и шепчет на цепные дроби

PS: где вы работаете, что у вас такие задачи возникают?
...
Рейтинг: 0 / 0
17.02.2020, 22:28
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927695
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
kealon(Ruslan)
где вы работаете, что у вас такие задачи возникают?
да просто вспомнилась головоломка.
мне понравилось решение к ней, там всё сошлось ровненько.
...
Рейтинг: 0 / 0
17.02.2020, 22:43
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927698
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
итак, первая подсказка: можно обойтись всего 5 использованиями рандомайзера. Не знаю, минимум ли это, но кажется что меньше нельзя.

больше подсказок не будет.
...
Рейтинг: 0 / 0
17.02.2020, 22:46
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39927857
VladimirKr
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
VladimirKr
Участник
Соколинский Борис


Есть совсем тупой способ
1. Складываем n random-чисел.
2. Исходя из ЦПТ считаем что получили Гаусс, берем и обратную функцию распределения.
3. Получаем равномерное распределение и квантуем на 5 значений.


Проще можно. Сумма n независимых одинаково распределенных величин по модулю 5 будет стремиться к равномерному распределению на Z5, причем, достаточно быстро...
...
Рейтинг: 0 / 0
18.02.2020, 11:26
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39928065
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
VladimirKr,

близко, по условию не интересно, надо поровну

так бы бери P=0.5 и k= s* fi(N), и всё
...
Рейтинг: 0 / 0
18.02.2020, 16:13
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39928144
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
VladimirKr
Соколинский Борис


Есть совсем тупой способ
1. Складываем n random-чисел.
2. Исходя из ЦПТ считаем что получили Гаусс, берем и обратную функцию распределения.
3. Получаем равномерное распределение и квантуем на 5 значений.


Проще можно. Сумма n независимых одинаково распределенных величин по модулю 5 будет стремиться к равномерному распределению на Z5, причем, достаточно быстро...

Автор нам дал не 5 величин а 5 битов. Тоесть 5 единичек. С косой гистограммой.
...
Рейтинг: 0 / 0
18.02.2020, 18:49
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39928387
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
что-то заглохло всё)
пока самая дельная мысль высказана в одном из сообщений Майтона
...
Рейтинг: 0 / 0
19.02.2020, 12:44
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39928414
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
У меня абсолютно точно не получается, ошибка в третьем знаке.
P=0.4, Q=0.6

Если A0=1 (P=0.4)
считаем количество выпадений единиц в последующих четырех испытаниях.
В случаях:
1, 2 (P=0.4992) возвращаем 0
0, 3, 4 возвращаем 1

если A0=0 (P=0.6)
считаем количество выпадений единиц в последующих четырех испытаниях.
В случаях:
2 (P=0.3456) возвращаем 2
3 (P=0.3456) возвращаем 3
0,1, 4 (P=0.3008) возвращаем 4

P(0)=0.19968
P(1)=0.20032
P(2)=0.200736
P(3)=0.200736
P(4)=0.18528
...
Рейтинг: 0 / 0
19.02.2020, 13:30
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39928432
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Если запустить оптимизатор, при P=0,402536732528652 невязка уменьшается на 4%.

P(0)=0,202445054
P(1)=0,200091678
P(2)=0,20734612
P(3)=0,205168341
P(4)=0,184948806
...
Рейтинг: 0 / 0
19.02.2020, 14:07
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39928449
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
Соколинский Борис,

приближение неплохое)
...
Рейтинг: 0 / 0
19.02.2020, 14:19
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39928794
VladimirKr
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
VladimirKr
Участник
Имя пользователя1
что-то заглохло всё)
пока самая дельная мысль высказана в одном из сообщений Майтона


Ну, после подсказки, что количество срабатывания датчика равно 5, задачу можно сформулировать так: найти p и разбиение соответствующего вероятностного пространства Бернулли из 5-ти (2^5=32) испытаний на 5 равновероятных подмножеств.

мой ответ: p=1/2-sqrt(10)/10, то есть p такое, что p*(1-p)=1/5

разбиения в файле
...
Рейтинг: 0 / 0
20.02.2020, 10:51
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39928795
VladimirKr
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
VladimirKr
Участник
VladimirKr
Имя пользователя1
что-то заглохло всё)
пока самая дельная мысль высказана в одном из сообщений Майтона


Ну, после подсказки, что количество срабатывания датчика равно 5, задачу можно сформулировать так: найти p и разбиение соответствующего вероятностного пространства Бернулли из 5-ти (2^5=32) испытаний на 5 равновероятных подмножеств.

мой ответ: p=1/2-sqrt(10)/10, то есть p такое, что p*(1-p)=1/5

разбиения в файле


очепятка p=1/2-sqrt(5)/10
...
Рейтинг: 0 / 0
20.02.2020, 10:52
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39928831
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
VladimirKr,

да, всё верно.

при такой вероятности, 32 исхода можно разделить на 16 пар, в каждой паре два "поразрядно противоположных" исхода, тогда будет одна пара с вероятностью 1/5, 5 пар с вероятностью каждой 2/25, и 10 пар по 1/25, что легко разбивается на 5 равных кучек.

Майтон правильно заметил вот что:
mayton
Гипотеза.

Данная задача не имеет решения если P - рациональная несократимая дробь вида m/n.


это элементарно доказывается: если P = m/n, где m > 1 и НОД(n, m) = 1, то у всех (кроме одного) исходов вероятностного пространства k испытаний будет вероятность вида m * (натуральное_число) / n^k, такая же вероятность будет у 4 из 5 кучек, а это нельзя сократить до 1/5
...
Рейтинг: 0 / 0
20.02.2020, 12:23
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39929159
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Имя пользователя1
VladimirKr,

да, всё верно.

при такой вероятности, 32 исхода можно разделить на 16 пар, в каждой паре два "поразрядно противоположных" исхода, тогда будет одна пара с вероятностью 1/5, 5 пар с вероятностью каждой 2/25, и 10 пар по 1/25, что легко разбивается на 5 равных кучек.

Майтон правильно заметил вот что:
mayton
Гипотеза.

Данная задача не имеет решения если P - рациональная несократимая дробь вида m/n.


это элементарно доказывается: если P = m/n, где m > 1 и НОД(n, m) = 1, то у всех (кроме одного) исходов вероятностного пространства k испытаний будет вероятность вида m * (натуральное_число) / n^k, такая же вероятность будет у 4 из 5 кучек, а это нельзя сократить до 1/5
слабоватое доказательство
во первых, исходов будет 2^k с вероятностью вида: m^i*(n-m)^(k-i)/n^k
во вторых, нужно только что бы из числителей этих исходов можно было набрать 5 одинаковых сумм

очевидно например, что это нельзя сделать если n не кратен 5
очевидно, что m^k и (n-m)^k каждый должны быть < n^k/5

остальное совсем не очевидно

так что вопрос про отсутствие решения в целых числах я думаю ещё не закрыт
...
Рейтинг: 0 / 0
20.02.2020, 19:31
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39929170
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
попробую чуть подробнее.

напомню, что рассматриваем m/n, такое что m и n взаимно просты, и m > n-m (то есть берем большую из вероятностей орла и решки), откуда m > 1, так как случай р=1/2 очевидно не подходит.

kealon(Ruslan)
во первых, исходов будет 2^k с вероятностью вида: m^i*(n-m)^(k-i)/n^k
согласен.
причем есть только один исход (n-m)^k/n^k, остальные будут содержать m в числителе.

kealon(Ruslan)
во вторых, нужно только что бы из числителей этих исходов можно было набрать 5 одинаковых сумм
согласен.

однако все суммы числителей, кроме одной (той самой, в которую попадет (n-m)^k) будут делиться на m, так как все слагаемые этих четырёх сумм делятся на m.

но тогда каждая из этих четырёх сумм не может быть пятой частью от n^k, так как n^k не делится на m (m и n - взаимно простые), значит не делится на сумму.
...
Рейтинг: 0 / 0
20.02.2020, 20:17
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39929280
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Имя пользователя1
но тогда каждая из этих четырёх сумм не может быть пятой частью от n^k, так как n^k не делится на m (m и n - взаимно простые), значит не делится на сумму.
вот теперь не поспоришь, занятное доказательство :-).
выходит, что решения нет для любых целых m, n

остались следующие очевидные неравенства
p^k * N <= 1
(1 - p)^k * N <= 1

Теперь бы понять как можно найти k, общую формулу для p и как искать комбинации
...
Рейтинг: 0 / 0
21.02.2020, 08:06
| Ответить | Цитировать | Написать  
Ещё один случайный конь
    #39929288
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
kealon(Ruslan)
Теперь бы понять как можно найти k, общую формулу для p и как искать комбинации
если требуется минимальный k для равновероятного выбора одного числа из N, то задача весьма сложная и многоплановая...

по правде сказать, я не до конца уверен в минимуме для N=5.

сам по себе подход, когда берем

для многих чисел дает не минимум. Например для 6 это не прокатит: для 6 можно сделать за 5 вызовов рандомайзера, а при такой вероятности за 5 не получится, P 5 > 1/6

в общем, здесь всё просто и понятно только для степени двойки )
...
Рейтинг: 0 / 0
21.02.2020, 09:29
| Ответить | Цитировать | Написать  
61 сообщений из 61, показаны все 3 страниц
  все  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Ещё один случайный конь
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]