pzh
написал 2 февраля 2005 года в 12:06 (810 просмотров)
Ведет себя
неопределенно; открыл 2 темы в форуме, оставил 6 комментариев на сайте.
Имеется 26 битная уникальная сигнатура вида 0111….1110( в средине только единички),
задача найти ее наличие, или ее начало в произвольном четырех байтном отрезке за минимальное количество операций.
Идеи есть ?
Буду благодарен даже за намеки на идеи.
Последние комментарии
- OlegL, 17 декабря в 15:00 → Перекличка 21
- REDkiy, 8 июня 2023 года в 9:09 → Как «замокать» файл для юниттеста в Python? 2
- fhunter, 29 ноября 2022 года в 2:09 → Проблема с NO_PUBKEY: как получить GPG-ключ и добавить его в базу apt? 6
- Иванн, 9 апреля 2022 года в 8:31 → Ассоциация РАСПО провела первое учредительное собрание 1
- Kiri11.ADV1, 7 марта 2021 года в 12:01 → Логи catalina.out в TomCat 9 в формате JSON 1
ecobeing.ru
Экология и вегетарианство на благо всем живым существам Планеты.
Примитивное решение в терминах SUS (Single Unix Specification):
Не тестировано. Худший случай — 6 итераций.
приведённое решение даёт ответ только для поиска сигнатуры целиком, в то время, как первоначальное условие такое:
Не совсем так по моему (мб я и ошибаюсь), решение находит полную сигнатуру и возвращает номер бита с которого она начинается или просто bool (см комментарий окло return). Если же задающий вопрос хотел найти и частичное вхождение, то вопрос не правильно сформулирован (опять же по-моему).
Кстати, в этом случае, с минимальными изменениями кода (1 строка) и увеличением количества итераций (2-ая строка) задача решается в лоб перебором. На таком размере данных и сигнатуры изобретать что-то более комплексное просто вредно для поизводительности.
Т.к. изменение тривиально, то оставим это в качестве упражнения.
Спасибо
Тривильное решение сейчас и работает, примерно в таком виде ))
А насчет изобретать, мысли все же бродят уж больно сигнатурка хитрая,
а количество операций все же хочется сократить.
Все равно большое спаибо за ответ.
Если сигнатура не меняется, то тогда сделайте loop unroll. Это наиболее быстрый путь если судить по исходному вопросу.
Полное вхождение — см. sas. Частичное, т.е. отрезок имеет вид
xx..xx011…11
(извините, если недопонял) примерно так:
идеи понял, премного благодарен )