Занимательные задачи

1.Передача текста.

   При передаче текстового сообщения возможна ошибка при приеме любой буквы. Для повышения надежности можно передавать каждый символ дважды, но тогда поиск правильного вида сообщения производится перебором всех возможных комбинаций символов из «поврежденных» пар с поиском среди полученных вариантов осмысленных. Как модифицировать описанный метод передачи, чтобы дешифровку сообщений мог производить компьютер? Какой вариант модификации является оптимальным (требующим минимального увеличения длительности сообщения)? (Вероятность ошибочного приема более одного символа подряд считать равной нулю).

   Решение.

   Оптимальным вариантом, при котором расшифровка принятого текста может производиться компьютером (не понимающим смысла слов и интерпретирующим их только как последовательности байтов - кодов символов), является передача каждого символа трижды с исправлением возможных ошибок методом «голосования». Если в результате сбоя какой-либо из триад один символ отличается от двух других, именно они и показывают верный ответ. Число 3 является в указанных условиях необходимым и достаточным: другие количества повторов при увеличении длительности передачи практически не повышают ее надежность по сравнению с трехкратным повторением. 2. Серии Штермера.

   В начале 20 века при попытке определить методом радиолокации высоту расположения в атмосфере ионизированного (отражающего радиолучи) слоя был обнаружен интересный эффект. Эхо каждого посланного в небо радиосигнала было двойным: один ответный сигнал был отражен от слоя, а происхождение второго было неизвестно, причем интервалы между этими парами сигналов были разными. Записанные последовательности длительностей этих пауз (которые позже были названы сериями Штермера - по фамилии ученого, производившего эксперименты) до сих пор будоражат умы многих исследователей, считающих их посланиями другой цивилизации.

   Попробуйте помочь ученым и расшифровать две приведенные ниже серии Штермера, учитывая, что, по существующей гипотезе, последовательность двоичных представлений чисел-длительностей без учета незначащих нулей представляет собой зашифрованное изображение.       а) 19, 128, 4, 17, 196, 768, 72, 56, 19, 128, 1024, 11, 252, 20480, 98, 118, 54, 10, 4, 42, 71, 138, 16, 69, 48;       б) 7, 28, 68, 4, 47, 1, 30, 33, 400, 30, 35, 46, 5, 17, 74, 19, 39, 7, 17, 124, 5, 25.

   Решение.       а) преобразуем первую серию в последовательность бит: 19 - 10011, 128 - 10000000, 4 - 100, 17 - 10001, 196 - 11000100, 768 - 1100000000, 72 - 1001000, 56 - 111000, 19 - 10011, 128 - 10000000, 1024 - 10000000000, 11 - 1011, 252 - 11111100, 20480 - 101000000000000, 98 - 1100010, 118 - 1110110, 54 - 110110, 10 - 1010, 4 - 100, 42 - 101010, 71 - 1000111, 138 - 10001010, 16 - 10000, 69 - 1000101, 48 - 110000.

   Подсчитаем общее количество бит: оно равно 169. Это число характерно тем, что из трех его делителей - 1, 13, 169 - первый и последний тривиальны, а оставшийся является простым числом, причем 169 - квадрат этого числа: 169=13*13. Предположим, что число 13 определяет размеры (в точках) квадратной картинки, которая, согласно гипотезе, зашифрована в сообщении. Начертим на клетчатой бумаге квадрат со стороной 13 клеток и перепишем значения бит подряд слева направо сначала в клетки первого ряда (верхнего), затем второго и т.д. вплоть до последнего. А теперь закрасим клетки, содержащие 1. Что получилось?       б) преобразуем аналогичным образом в последовательность бит вторую серию: 7 - 111, 28 - 11100, 68 - 1000100, 4 - 100, 47 - 101111, 1- 1, 30 - 11110, 33 - 100001, 400 - 110010000, 30 - 11110, 35 - 100011, 46 - 101110, 5 - 101, 17 - 10001, 280 - 100011000, 17 - 10001, 74 - 1001010, 19 - 10011, 39 - 100111, 7 - 111, 17 - 10001, 124 - 1111100, 5 - 101, 25 - 11001.

   Подсчитав количество бит, получим число 125. Его нетривиальным делителем является число 5, причем 125=5*5. Предположим, что здесь мы имеем дело с «трехмерной» картинкой, или с пятью квадратными рисунками размером 5 на 5 точек каждый. Вычертим их рядом на клетчатой бумаге и заполним клетки битами также, как в предыдущем случае: сначала весь первый квадрат, затем второй и так до последнего. Закрасим клетки, содержащие 1. Что получилось на этот раз? 3. Решить арифметический ребус, т. е. Поставить в соответствие каждой букве в равенстве цифру (разные буквы обозначают разные цифры):

      ДА^Д= РАД.

   Решение.

   В десятичной системе счисления при записи натуральных чисел цифры, участвующие в записи числа указывают последовательно справа налево вес цифры в числе (количество единиц, затем десятков …), например,

     &nbsp45 = 4 * 10 + 5;      &nbsp432 = 4 *100 + 3 * 10 + 2. В данном ребусе таким же образом нужно получить числа ДА и РАД.

         ДА = Д * 10 + А          РАД = Р * 100 +А * 10 +Д. Далее организуем перебор значений переменных Р, А, Д (три вложенных цикла). нц для Р от 1 до 9    нц для А от 1 до 9       нц для Д от 0 до 9          если Д < > Р и Д < > А и Р < >А             то ДА : = Д * 10 + А; РАД : = Р * 100 + А * 10 + Д                если ДА ** Д = РАД                   то вывод РАД                все             все          кц       кц кц Ответ: 25²= 625. 4. а) Предложите самый простой способ кодирования любого текста так, чтобы шифровка и дешифровка могли осуществляться одним и тем же устройством (с помощью одной и той же операции над кодами символов). б) как шифровать текст с паролем (пароль - любое число о 1 до 255) с сохранением универсальности работы устройства?

   Решение. а) самый простой способ такой шифровки текста - заменять все единичные биты в двоичном коде символа на нулевые и наоборот, включая незначащие нули, т. е. Производить инверсию байта. Тогда вид символов будет изменяться довольно непредсказуемым на первый взгляд образом. Дешифровка производится обратной заменой, т. е. тоже инверсией. Операция дешифровки полностью идентична операции шифровки; б) шифровку с паролем будем в этом случае выполнять при помощи логической операции XOR, операндами которой являются байт-код символа и байт-пароль. Для шифровки потребуется повторно выполнить операцию XOR (используя то же самое число-пароль). Это возможно благодаря тому, что XOR относится к числу симметричных логических операций. 5. Незнайка написал послание и подписался одним зашифрованным словом, используя код, состоящий из 0 и 1. Им был выбран самый простой способ кодировки текста 32 букв алфавита( е = е). Знайка быстро расшифровал сообщение, распознав количество букв в нем, и посоветовал Незнайке быть поскромнее и более изобретательным. Определите ключ (принцип) шифровки и расшифруйте слово-подпись:

     &nbsp011111001111000010100100001101

   Решение. Нужно каждой букве русского алфавита задать номер от 0 до 31. Максимальный номер (31) можно представить как двоичное число 31 =11111. Так как номеров больших 31 нет, то для кодирования русских букв достаточно пятизначного двоичного числа. Дальше необходимо разбить цепочку - шифр на группы из пяти знаков справа налево.      &nbsp01111 = 15 - П      &nbsp10011 = 19 - У      &nbsp11000 = 24 - Ш      &nbsp10100 = 10 - К      &nbsp01000 = 8 - И      &nbsp01101 = 13 - Н.