Книга-тренажер: «Базовая подготовка к ЕГЭ по информатике в компьютерной форме». Авторский курс - страница 6

1) АххБ 3) хххх

2) АВхБ 4) АВББ

Решение:

Декодируем каждое слово сообщения. Первое слово: 11000 отличается от буквы А только одной позицией, поэтому на первом месте будет А. Второе слово: 11101 отличается от буквы В только одной позицией, поэтому на второй позиции будет В. Третье слово: 10001 отличается от любой буквы более чем одной позицией, поэтому третья позиция – x. Четвёртое слово: 11111 отличается от буквы Б только одной позицией, поэтому четвертая позиция – Б. Таким образом, ответ: АВхБ.

Ответ: 2.

Задачи для самостоятельного решения

Задача 4.4

По каналу связи передаются сообщения, содержащие только четыре буквы: М, А, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: М – 101, Р – 100, Т – 01. Укажите кодовое слово минимальной длины, которое можно использовать для буквы А. Если таких кодовых слов несколько, приведите кодовое слово с минимальным числовым значением.

Примечание. Условие Фано означает, что соблюдается одно из двух условий: либо никакое кодовое слово не является началом другого кодового слова, либо никакое кодовое слово не является окончанием другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Задача 4.5

По каналу связи передаются сообщения, содержащие только шесть букв: Я, Н, В, А, Р, Ь. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Н – 00, В – 01, Р – 10, Ь – 111. Укажите минимально возможную длину закодированной последовательности для слова ВАРВАР.

Алгоритм – это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность.

Алгоритм можно задать одним из следующих способов:

• словесное описание последовательности действий на

естественном языке;

• графическое изображение в виде блок-схемы;

• запись при помощи псевдокода (алгоритмического

языка);

• запись на языке программирования.

В этом типе задач рассматривается в основном словесное описание алгоритмов на естественном языке, а потому никаких специальных знаний для решения задачи не требуется. В данных типах задач используются разные исполнители – от чертежника, черепашки до автомата. Рассмотрим основные типы задач, которые здесь могут быть использованы.

Пример 5.1

Алгоритм получает на вход натуральное число N и строит по нему новое число R следующим образом:

1. Строится двоичная запись числа N.

2. Складываются все цифры полученной двоичной записи. В конец записи (справа) дописывается остаток от деления суммы на 2.

3. Предыдущий пункт повторяется для записи с добавленной цифрой.

4. Результат переводится в десятичную систему.

Пример. Дано число N = 13. Алгоритм работает следующим образом:

1. Двоичная запись числа N: 1101.

2. Сумма цифр двоичной записи 3, остаток от деления на 2 равен 1, новая запись 11011.

3. Сумма цифр полученной записи 4, остаток от деления на 2 равен 0, новая запись 110110.

4. Результат работы алгоритма R = 54.

При каком наименьшем числе N в результате работы алгоритма получится R> 170? В ответе запишите это число в десятичной системе счисления.

Решение: Рассмотрим первое попавшееся число, которое больше 170. 171=10101011. У этого числа отделим последние два разряда 171= 101010 | 11 не походит, т.к., выполняя второе правило, алгоритм сложит все единицы, которые стоят слева от вертикальной линии 1+1+1=3, а затем 3 разделим на 2 без остатка и получим 1 и запишем эту единица справа от числа 101010 1. Затем снова применим второе правило к получившемуся числу 101010 | 1. И получим уже новое число 101010 | 10. Получившееся число 10101010=170 по условию задачи должно быть равно 171. Понятно, что 171 не равно 170, поэтому число 171 не подходит. Берем число 172=10101100. Проверяем его на второе правило 2 раза и видим, что число 172 подходит. Осталось только число 10101100 без двух правых нулей перевести в десятичную систему счисления. Получаем 101011=43.