Но как подобрали эти сиды? Брутфорсом? И какая вероятность найти seed, которое будет выдавать последовательность из 6 чисел?| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Java: Общие вопросы > Как это сделано? |
| Автор: Karadul 31.3.2013, 01:16 |
| http://ideone.com/ZdZB6C |
| Автор: Arantir 31.3.2013, 02:53 |
| Генерация чисел является http://ru.wikipedia.org/wiki/%D0%93%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D1%82%D0%BE%D1%80_%D0%BF%D1%81%D0%B5%D0%B2%D0%B4%D0%BE%D1%81%D0%BB%D1%83%D1%87%D0%B0%D0%B9%D0%BD%D1%8B%D1%85_%D1%87%D0%B8%D1%81%D0%B5%D0%BB. Это значит, что ряд чисел, выдаваемый генератором, детерминирован. Конструктор класса Random принимает аргументом сид. Для одного и того же сида ряд генерируемых чисел всегда одинаков. Вся суть вышеприведенной программы заключается в ловко подобранных сидах и символе, к которому прибавляются полученные псевдослучайные числа. |
| Автор: Stolzen 31.3.2013, 09:27 |
| http://stackoverflow.com/questions/15182496/why-does-this-code-print-hello-world |
| Автор: Karadul 31.3.2013, 16:56 |
| Это я уже сам понял Но как подобрали эти сиды? Брутфорсом? И какая вероятность найти seed, которое будет выдавать последовательность из 6 чисел? |
| Автор: Stolzen 31.3.2013, 18:26 |
| Посмотрите ссылку, там есть ответы на ваши вопросы |
| Автор: Karadul 31.3.2013, 21:53 |
| http://stackoverflow.com/a/15198628/2112218, я просто эти математические козюбрики плохо понимаю Я так понимаю, этот код уже - редкостный боян? |
| Автор: Stolzen 1.4.2013, 15:35 |
| Рассмотрим следующую задачу: Допустим, мы хотим получить слово "ЛЕНИН". Наш алфавит состоит из 33 букв и одного терминального символа, обозначающего конец последовательности, например '.'. Т.е. мы ищем слово "ЛЕНИН." Можно представить, что мы бросаем многогранник с 34-мя гранями 6 раз, и каждый раз записываем выпавшую букву. Пусть событие B - выпал "ЛЕНИН." p = p(B) = (1/34)^6 (34^6 - общее число исходов, 1 - число благоприятных исходов) q = p(не B) = 1 - p - выпал не "ЛЕНИН.". Теперь посчитаем сколько испытаний нужно провести, чтобы хотя бы раз выпал "ЛЕНИН.". Пусть событие А - при n испытаниях слово "ЛЕНИН" выпадает хотя бы один раз. Посчитаем n для P(A) = 0.9: q^n = P(не B)^n - вероятность того, что за n испытаний слово "ЛЕНИН." не выпадет ни разу. P(A) = 1 - P(не B)^n = 1 - q^n P(A) = 0.9 0.9 = 1 - q^n q^n = 0.1 n ln q = ln 0.1 n = ln 0.1 / ln q Подставляем q и получаем n = ~3.5 млрд раз. Т.е. для того, чтобы с вероятностью 0.9 хотя бы один раз выпало слово "ЛЕНИН." нам нужно провести около 3.5 млрд испытаний. Теперь оценим количество операций. Положим, что один бросок нашего многогранника есть одна операция. Далее, пусть в испытании мы бросаем буквы до тех пор, пока складывается нужно слово и прекращаем, как только выпало что-то другое. Т.е. если 1-й буквой выпала "Л" мы продолжаем, иначе останавливаемся. Пусть случайная величина X - количество операций для одного испытания. p = 33/34 вероятность того, что испытание прерывается q = 1/34 вероятность того, что испытание продолжается p_i - вероятность того, что испытание закончится после x_i операций. x_1 = 1, p_1 = q = 33/34 (только в 1 случае из 34 продолжаем, во всех остальных останавливаемся) x_2 = 2, p_2 = q^1 * p = 1/34 * 33/34 (вероятность того, что в прошлый раз выпала нужная буква и того, что в этот раз выпала ненужная) x_3 = 3, p_3 = q^2 * p = 1/34^2 * 33/34 x_4 = 4, p_4 = q^3 * p = 1/34^3 * 33/34 x_5 = 5, p_5 = q^4 * p = 1/34^4 * 33/34 x_6 = 6, p_6 = q^5 * 1 = 1/34^5 * 1 (вероятность того, что все 5 предыдущих раз выпала нужная буква * 1, т.к. 6-й раз мы бросаем в любом случае) Проверка: сумма всех вероятностей должна быть равна единице. sum(p_i) = (33*34^4 + 33*34^3 + 33*34^2 + 33*34 + 33 + 1) / 34^5 = 45435424 / 45435424 = 1 Найдем математическое ожидание нашей случайной величины M(X) = sum p_i * x_i ~ 1.0303 Т.е. в среднем за один эксперимент производится 1.0303 операции. N = n * 1.0303 ~ 3.6 млрд операций. Итого получаем, что нужно осуществить около 3.6 млрд операций, чтобы подобрать нужное слово длины 5 и оканчивающееся нулём. Не так уж и много для современных компьютеров - на моем ноутбуке почти всегда алгоритм завершается быстрее, чем за 30 секунд. |
| Автор: Karadul 1.4.2013, 19:27 |
| 2**32 (4 млрд) - worst case, при том, что можно искать параллельно несколько слов Все это верно, если буквы выпадают равновероятно. Надо бы посмотреть nextInt. |