ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Ещё один случайный конь
25 сообщений из 61, страница 2 из 3
  2  все
Ещё один случайный конь
    #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
| Ответить | Цитировать | Написать  
25 сообщений из 61, страница 2 из 3
  2  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Ещё один случайный конь
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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