Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=39031&view=findpost&p=1660426 Fri, 10 Aug 2007 12:12:09 +0000 теория вероятности задача https://forum.sources.ru/index.php?showtopic=39031&view=findpost&p=1660426 P(m,k)= сумма по i от 0 до k-m от C(k,i) * (n-1)^i /n^k]]> Го_ Алгоритмы https://forum.sources.ru/index.php?showtopic=39031&view=findpost&p=1660412 Fri, 10 Aug 2007 12:05:00 +0000 теория вероятности задача https://forum.sources.ru/index.php?showtopic=39031&view=findpost&p=1660412 Го_
поделишься?]]> amk Алгоритмы https://forum.sources.ru/index.php?showtopic=39031&view=findpost&p=1660286 Fri, 10 Aug 2007 10:31:00 +0000 теория вероятности задача https://forum.sources.ru/index.php?showtopic=39031&view=findpost&p=1660286 Цитата amk @
Существует достаточно эффективный алгоритм вычисления этой функции (типа треугольника Паскаля), сложности порядка O(m*k), требующий min(m,k) памяти.
Сложность O(k-m+ln(n)), память O(1)]]> Го_ Алгоритмы https://forum.sources.ru/index.php?showtopic=39031&view=findpost&p=1656275 Mon, 06 Aug 2007 11:53:00 +0000 теория вероятности задача https://forum.sources.ru/index.php?showtopic=39031&view=findpost&p=1656275 так слово "ab" из слова "abb" можно получить двумя способами, вычеркнув вторую или третью букву.

а по описанному алгоритму получаются слова
aab, aab, aba
bab, abb, abb

Легко заметить, что первое и второе слова совпадают, также как и пятое-шестое. Отсюда и вероятность больше в полтора раза.
Увеличивая длину слов таким подсчетом можно, думаю, вообще получить вероятность больше 1.

В принципе можно считать что искомая строка - это просто все символы записанные подряд. На результат это не повлияет.

Пусть Pn(m,k) вероятность того, что из произвольной строки длиной k можно указанным способом выбрать m необходимых.
Тогда имеем:
Pn(m,k) = 0, для m > k
Pn(m,m) = 1/nm, т.к. cуществует лишь одна строка необходимой длины из nm возможных
P(m,k) = 1/n*Pn(m-1,k-1) + (n-1)/n*P(m,k-1) = (Pn(m-1,k-1) + (n-1)*P(m,k-1))/n
Либо первый символ строки можно принять, либо придется искать в укороченной строке

Существует достаточно эффективный алгоритм вычисления этой функции (типа треугольника Паскаля), сложности порядка O(m*k), требующий O(m) памяти.]]> amk Алгоритмы https://forum.sources.ru/index.php?showtopic=39031&view=findpost&p=1655680 Sun, 05 Aug 2007 17:40:56 +0000 теория вероятности задача https://forum.sources.ru/index.php?showtopic=39031&view=findpost&p=1655680 esperanto
нужна целочисленная формула или асимптотичеcкая зависимость при больших x?]]> CD_Eater Алгоритмы https://forum.sources.ru/index.php?showtopic=39031&view=findpost&p=1655272 Sat, 04 Aug 2007 14:09:57 +0000 теория вероятности задача https://forum.sources.ru/index.php?showtopic=39031&view=findpost&p=1655272 CD_Eater Алгоритмы https://forum.sources.ru/index.php?showtopic=39031&view=findpost&p=1655253 Sat, 04 Aug 2007 13:34:28 +0000 теория вероятности задача https://forum.sources.ru/index.php?showtopic=39031&view=findpost&p=1655253 Тут такая бяка получается:
                x!
    P = -------------------
                         n
         n! * (x-n)! * n
]]> WargaL Алгоритмы https://forum.sources.ru/index.php?showtopic=39031&view=findpost&p=1655176 Sat, 04 Aug 2007 09:43:37 +0000 теория вероятности задача https://forum.sources.ru/index.php?showtopic=39031&view=findpost&p=1655176 Цитата WargaL @
Можно и так посчитать.

              x!
    P = ---------------
                     x
        (x-2)!  *  n

Нельзя так посчитать :)
Подставьте x=3, n=2
Этот случай легко проверить на бумажке - должна получиться вероятность 1/2
А по этой формуле получается 3/4]]> CD_Eater Алгоритмы https://forum.sources.ru/index.php?showtopic=39031&view=findpost&p=1655169 Sat, 04 Aug 2007 09:20:14 +0000 теория вероятности задача https://forum.sources.ru/index.php?showtopic=39031&view=findpost&p=1655169 Во-первых, число возможных комбинаций не x^n, а n^x(разница существенна).
Во-вторых, всего возможных комбинаций, которые можно добавить не (x-n)^n,а n^(x-n)(такаяже ошибка).
Сочетать надо n элементов из x (C(x,n)),а можно (x-n) элементов из x т.е. (C(x,x-n)). Результат одинаков.
В итоге получаем следующее:


          x-n                     x-n
         n     *  C(x,x-n)       n     *  C(x,n)
    P = -------------------  =  ----------------- ;
                 x                      x
               n                      n
              
    где
                   x!
    C(x,x-n)= --------------
               n! *  (x-n)!
              
                   x!
    C(x,n)= --------------
             (x-n)!  *  n!

вот, где-то так.


Можно и так посчитать.

              x!
    P = ---------------
                     x
        (x-2)!  *  n


Но уж если говорить на чистоту, это тот же способ, только я сократил выражение, упростив его.]]> WargaL Алгоритмы https://forum.sources.ru/index.php?showtopic=39031&view=findpost&p=253029 Thu, 27 Nov 2003 04:37:52 +0000 теория вероятности задача https://forum.sources.ru/index.php?showtopic=39031&view=findpost&p=253029 в этом предположении продолжаем.
1. всего возможных вариантов х^п. (1)
2. всего возможных благоприятных вариантов вот столько.
будем генерировать слово в из х букв в два подхода, сначала генерируются буквы нашего п-слова, а затем, все остальные буквы.
вероятность сгенерить нужное нам слово из п букв 1/п^п.
рассчитаем скольки способами мы можем получить возможный вариант дальнейшего получения. возьмем слово из п букв, которое нам надо.
нам надо добавить к нему х-п букв, чтобы получить слово длиной х букв.
всего возможных комбинаций, которые можно добавить (х-п)^п.
теперь надо расставить одну из таких комбинаций. мы можем ставить буквы этой комбинации между буквами нашего данного слова длиной х-п, до и после его букв, т.е. всего к = п + 1 место. а посчитать количество расставлений можно вот так. это все равно, что в к урн расложить м = х - п шаров. а разложить все равно, что в последовательности(т.е. где-то между или до или после можно несколько подряд) из м единиц поставить к - 1 палочеку |. это получается С(k + m - 1, к - 1) - Расстановки с повторениями,
т.е. в итоге всего способов
С(п + 1 + х - п - 1, п + 1 - 1)*(х-п)^п*р(сгенерить нужное нам слово из п букв) = С(х, п)*(х-п)^п/п^п. (1)
а потом делим (2) на (1)

р =(п* х)^п/С(х, п)*(х-п)^п

вроде бы, когда п = 1, а х =2, то р = 1, что вроде как правильно. даже, если я где-то ошибку допустил, то все равно мне кажется можно до ума довести и получить правильный ответ. ]]> experimenter Алгоритмы https://forum.sources.ru/index.php?showtopic=39031&view=findpost&p=252842 Wed, 26 Nov 2003 18:07:59 +0000 теория вероятности задача https://forum.sources.ru/index.php?showtopic=39031&view=findpost&p=252842
берется случайная последовательность букв длиной х>п.

имеется слово длиной п, каждая буква в нем появляется ровно один раз.

какова вероятность что стерев из х необходимое кол-во букв можно получить это слово.(буквы можно стирать любые) ]]> esperanto Алгоритмы