КНИГА-ТРЕНАЖЕР: «Базовая подготовка к ЕГЭ по информатике в компьютерной форме». Авторский курс. Евгений Леонидович Сидоркин
Чтение книги онлайн.

Читать онлайн книгу КНИГА-ТРЕНАЖЕР: «Базовая подготовка к ЕГЭ по информатике в компьютерной форме». Авторский курс - Евгений Леонидович Сидоркин страница 7

СКАЧАТЬ Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

      Задача 4.5

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

      Задача №5. Анализ, исполнение и построение линейного алгоритма для исполнителя

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

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

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

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

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

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

      языка);

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

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

      Пример 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 не подходит. СКАЧАТЬ