Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Из общих соображений... 02.12.01 13:35 Число просмотров: 990
Автор: Chingachguk <Chingachguk> Статус: Member
|
> - есть блок некоторых данных > - нужно составить такую последовательность, которая не > встречается в этих данных
Если покажется фуфлом, прошу сильно не бить ! ;)
Пусть есть блок размером N байт. Предположим худшее - в нем все байты очень хорошо псевдослучайные.
Очевидно, почти наверняка последовательность в 1 байт в нем есть.
Оценим вероятность нахождения последовательности в K байт, K<N.
Начнем с позиции 1: |--------------------------------------(Длина N) |--------(Длина K)
Всего есть последовательностей длиной K с первой позиции 256^K.
Вероятность совпадения в первой позиции - 1/256^K.
Последовательности длиной K могут начинаться с позиций числом N-K,
те всего вариантов (N-K) * 256^K.
Из них заданных последовательностей - (N-K)*(256^(K-1)).
Значит, надо искать с такого K, чтобы число таких последовательностей было очень мало, те
(N-K)*(256^(K-1)) -> 0.
|
|
|