Я понял в чем проблема — вам кажется, что матожидание до первой встречи обратно пропорционально частоте встречи в бесконечной случайной строке. Это похоже на правду для точек на прямой. Средняя длина отрезка между двумя точками обратно пропорциональна их частоте. Но со строками это не так. Строку «aaa» можно наложить на другое ее вхождение, а строку «abc» — нельзя. При наложении двух строк связь матожидания расстояния между ними и частоты нарушается.
Похоже что вы не так поняли условие. В задаче просится мат. ожидание нажатий до ПЕРВОЙ встречи строки. Вы там считаете среднее количество вхождений и оно, действительно одинаково. Если бы обезьяна продолжала печатать после корректного набора и мы потом считали сколько раз она напечатала нужный нам текст, то было бы то, что вы сейчас считаете. Мы же после корректного набора обезьяну выгоняем.
тут дело в том, что для строки «aaa», когда набрано 2 первых символа при следующем символе «a» текст соберется, а для оставшихся 26-ти символов будет откат в 0 правильно набранных символов. Т.е. с вероятностью 1/26 набор закончится а с вероятностью 25/26 надо будет начинать набор с нуля. Для строки «abc» же, после корректного нажатия двух первых символов: с вероятностью 1/26 текст наберется, с вероятностью 1/26 будет снова набран первый символ «a» и останется набирать только 2, и с вероятностью 24/26 надо будет начинать с нуля. Именно из за этого перекоса в вероятностях сложнее закончить собирать первую строку.
Вы правы, стоило более четко формулировать задачу. Я добавил замечание про количество нажатий в статью, спасибо.
Согласно формуле, для строки «aaa» нужно 18278 нажатий в среднем, а для «abc» — 17576. Разница будет еще заметнее, если ограничится алфавитом только из трех букв (39 против 27).
Не могу найти источник, но где-то читал: предсказывают какой штамм гриппа будет в этом сезоне по сельсхохозяйственным исследованиям. Наиболее вероятный источник заразы — всякие с/х животные. Там новые штаммы мутируют и распространяются потом на людей. Конечно, могут и не угадать что именно через полгода вызовет эпидемию, но какой-то шанс предсказать все-таки есть.
Опять же, не придираясь к фразе, средняя оценка — это если входные данные случайны. А как вам уже ответили — это далеко не всегда так. Кроме того, если сервер можно подвесить каким-то запросом, который является худшим случаем, то это совсем не хорошо.
Извините, что вклиниваюсь, но сама фараза "смотря что подразумевать под O" просто требует комментария из-за ее абсурдности и противоречивости. Есть конкретное определение O() и не с потолка оно взято. Конкретные свойства делают это определение полезным на практике. И подразумевать под O() что-то другое никак нельзя.
Возможно тут дело в том, что 7zip рассчитан на одноразовую распаковку до работы с файлами, а png для распаковки каждый раз при просмотре. Мне кажется, что просмотр картинки в 7zip займет на порядки больше времени чем в специальных форматах. Кроме того из архива есть другие недостатки, скажем гораздо сложнее выдрать конкретную часть картинки или ее эскиз.
Проблема в том, что польза-то их личная, в долларах измеренная, а вред — он общественный. Деньги у копирастов немалые, вот они и лоббируют эти ужасные законы. И ничего тут не сделаешь.
Этот алгоритм — динамическое программирование. В таблице в n-ом столбце в k-ой строке подсчитано количество чисел длины n имеющих сумму цифр k (ведущие нули разрешены). Обозначим это количество через f(k,n) Пересчет такой таблицы тоже очень прост — последняя цифра может быть любой от 0 до 9. Количество таких билетов с последней цифрой i, длинной n, суммой всех цифр k — f(k-i,n-1). Если просуммировать по всем i, как раз будет формула — сложить 10 значений в предыдущем столбце, на той же строке и выше.
Отсюда же понятно, почему количество всех счастливых билетов — сумма квадратов чисел в столбце. Каждый билет составлен из двух половинок, половинки должны иметь одинаковую сумму. Квадраты получается потому, что можно взять любое число длины n с заданной суммой и в левую и в правую половину счастливого билета, поэтому f(k,n)*f(k,n) и будет количество счастливых билетов длины 2n с суммой в каждой половине k. Теперь остается только просуммировать по всем k.
Есть интересное рассуждение, из которого следует что мы почти наверняка в черной дыре. Есть только одно предположение — средняя плотность массы во вселенной больше некоторого эпсилон, большего нуля.
Рассмотрим шар радиуса R. В нем массы O(R^3). А радиус Шварцшильда (радиус черной дыры) пропорционален массе, т.е. R^3. Отсюда получается, что рассматривая все больший и больший шар в пространстве, рано или поздно радиус Шварцшильда превысит радиус шара, т.к. растет кубически относительно радиуса шара. Для любого стороннего наблюдателя это область пространства будет черной дырой.
Представить, что средняя плотность массы во вселенной равна нулю, очень сложно, так что мы скорее всего в черной дыре и есть. Если кто-нибудь укажет на ошибку в рассуждениях, буду благодарен — давно мучаюсь этим вопросом.
Биологическое оружие уже сейчас запрещено делать. Запрет ГМО, разрабатываемого в пищу и разумно контролируемого, никоим образом не изменяет уровень этого риска.
Единственное изменение в статье — это замечание в самом начале о том. что считать будем нажатия по клавишам а не время в секундах.
Согласно формуле, для строки «aaa» нужно 18278 нажатий в среднем, а для «abc» — 17576. Разница будет еще заметнее, если ограничится алфавитом только из трех букв (39 против 27).
Отсюда же понятно, почему количество всех счастливых билетов — сумма квадратов чисел в столбце. Каждый билет составлен из двух половинок, половинки должны иметь одинаковую сумму. Квадраты получается потому, что можно взять любое число длины n с заданной суммой и в левую и в правую половину счастливого билета, поэтому f(k,n)*f(k,n) и будет количество счастливых билетов длины 2n с суммой в каждой половине k. Теперь остается только просуммировать по всем k.
Идея в том, что очень большая черная дыра может иметь очень маленькую среднюю плотность. И, может быть, даже не иметь никакой сингулярности.
Рассмотрим шар радиуса R. В нем массы O(R^3). А радиус Шварцшильда (радиус черной дыры) пропорционален массе, т.е. R^3. Отсюда получается, что рассматривая все больший и больший шар в пространстве, рано или поздно радиус Шварцшильда превысит радиус шара, т.к. растет кубически относительно радиуса шара. Для любого стороннего наблюдателя это область пространства будет черной дырой.
Представить, что средняя плотность массы во вселенной равна нулю, очень сложно, так что мы скорее всего в черной дыре и есть. Если кто-нибудь укажет на ошибку в рассуждениях, буду благодарен — давно мучаюсь этим вопросом.