B8 (повышенный уровень, время – 8 мин)
⇐ ПредыдущаяСтр 3 из 3 Тема: Анализ алгоритма построения последовательности. Что нужно знать: · в некоторых задачах (на RLE-кодирование, см. далее) нужно знать, что такое бит и байт, что байт равен 8 бит, что такое старший бит, как переводить числа из двоичной системы в десятичную · в классических задачах (на символьные цепочки) каких-либо особых знаний из курса информатики, кроме умения логически мыслить, не требуется Пример задания: Строки (цепочки символов латинских букв) создаются по следующему правилу. Первая строка состоит из одного символа – латинской буквы «А». Каждая из последующих цепочек создается такими действиями: в очередную строку сначала записывается буква, чей порядковый номер в алфавите соответствует номеру строки (на i -м шаге пишется « i »-я буква алфавита), к ней справа дважды подряд приписывается предыдущая строка. Вот первые 4 строки, созданные по этому правилу: (1) A (2) BAA (3) CBAABAA (4) DCBAABAACBAABAA Латинский алфавит (для справки): ABCDEFGHIJKLMNOPQRSTUVWXYZ Запишите семь символов подряд, стоящие в восьмой строке со 126-го по 132-е место (считая слева направо). Решение: 7) используя приведенное правило, можно построить следующие строки: (5) EDCBAABAACBAABAADCBAABAACBAABAA (6) FEDCBAABAACBAABAADCBAABAACBAABAAEDCBAABAACBAABAADCBAA ... 8) мы быстро убедимся, что следующие строки получаются достаточно длинные, и легко запутаться, отсчитывая символы с номерами 126-132 в восьмой строке 9) попробуем найти закономерности, позволяющие решить задачу без выписывания 8-ой строки; 10) прежде всего, заметим, что длины первых строк 1, 3, 7, 15, … – это числа вида 2i-1, где i – номер строки; таким образом, длина 7-ой строки – 127, а длина восьмой – 255 символов 11) восьмая строка строится так: восьмая буква латинского алфавита (H) и затем – два раза седьмая строка (сверху написаны номера символов)
12) символы 126-132 находятся на границе двух цепочек, повторяющих 7-ую строку; заметим, что в соответствии с заданным алгоритмом можно легко определить первые символы в 7-ой строке (GFEDC) и последние символы (AABAA) 13) далее сразу находим, что интересующая нас часть 8-ой строки имеет вид
14) таким образом, правильный ответ – BAAGFED.
Еще пример задания: Упаковка информации методом RLE-кодирования состоит в следующем. Упакованная последовательность содержит управляющие байты, за каждым управляющим байтом следует один или несколько байтов данных. Если старший бит управляющего байта равен 1, то следующий за управляющим байт данных при распаковке нужно повторить столько раз, сколько записано в оставшихся 7 битах управляющего байта. Если же старший бит управляющего байта равен 0, то надо взять несколько следующих байтов данных без изменения. Сколько именно – записано в оставшихся 7 битах управляющего байта. Например, управляющий байт 10000111 говорит о том, что следующий за ним байт надо повторить 7 раз, а управляющий байт 00000100 – о том, что следующие за ним 4 байта надо взять без изменений.
10000011 10101010 00000010 10101111 11111111 10000101 10101010. Сколько байт будет содержать данная последовательность после распаковки? Впишите в бланк только число. Решение: 1) обратите внимание, что в этой задаче НЕ нужно распаковывать последовательность, а нужно просто определить ее длину 2) проанализируем первый управляющий байт, 10000011; он начинается с 1 – это команда на повторение следующего символа; количество повторений записано в семи младших битах: 112 = 3 раза; значит, раскодирование первых двух байт дает 3 символа 3) следующий управляющий байт – третий, 00000010; его старший бит 0 говорит о том, что следующие 102 = 2 символа повторяются 1 раз; получаем еще 2 символа 4) следующий управляющий байт – шестой, 10000101; он говорит о том, что следующий за ним символ нужно повторить 1012 =5 раз; получаем еще 5 символов 5) полная длина распакованной последовательности равна 3 + 2 + 5 = 10 символов 6) вот итог нашего анализа:
7) таким образом, правильный ответ – 10. Еще пример задания: Строки (цепочки символов латинских букв) создаются по следующему правилу. Первая строка состоит из одного символа – латинской буквы «А». Каждая из последующих цепочек создается такими действиями: в очередную строку сначала записывается буква, чей порядковый номер в алфавите соответствует номеру строки (на i -м шаге пишется « i »-я буква алфавита), к ней справа дважды подряд приписывается предыдущая строка. Вот первые 4 строки, созданные по этому правилу: (1) A (2) BAA (3) CBAABAA (4) DCBAABAACBAABAA Латинский алфавит (для справки): ABCDEFGHIJKLMNOPQRSTUVWXYZ Сколько в восьмой строке букв, отличных от буквы «А»? Решение (1 вариант): 1) попробуем найти закономерность в изменении количества букв, отличных от буквы «A» 2) в первой строке 0 таких букв, во второй – 1 (удвоили число букв «не A» в предыдущей строке и добавили 1, поскольку в начало строки дописана буква «B») 3) аналогично находим, что в третьей строке – 3 нужных буквы, в 4-ой – 7 и т.д.
4) продолжим последовательность, каждый раз умножай предыдущее число на 2 и добавляя единицу: 5 строка – 15 6 строка – 31 7 строка – 63 8 строка – 127 5) «умные и ленивые» могут сообразить, эти числа задаются общей формулой , где N – номер строки, подстановка дает , что совпадает с полученным выше результатом 6) таким образом, правильный ответ – 127.
Пример задания: Производится одноканальная (моно) звукозапись с частотой дискретизации 16 кГц и глубиной кодирования 24 бита. Запись длится 1 минуту, ее результаты записываются в файл, сжатие данных не производится. Какое из приведенных ниже чисел наиболее близко к размеру полученного файла, выраженному в мегабайтах? 1) 0,2 2) 2 3) 3 4) 4 Решение: 17) так как частота дискретизации 16 кГц, за одну секунду запоминается 16000 значений сигнала 18) так как глубина кодирования – 24 бита = 3 байта, для хранения 1 секунды записи требуется 16000 ´ 3 байта = 48 000 байт (для стерео записи – в 2 раза больше) 19) на 1 минуту = 60 секунд записи потребуется 60 ´ 48000 байта = 2 880 000 байт, то есть около 3 Мбайт 20) таким образом, правильный ответ – 3.
Еще пример задания: Производится одноканальная (моно) звукозапись с частотой дискретизации 64Гц. При записи использовались 32 уровня дискретизации. Запись длится 4 минуты 16 секунд, её результаты записываются в файл, причём каждый сигнал кодируется минимально возможным и одинаковым количеством битов. Какое из приведённых ниже чисел наиболее близко к размеру полученного файла, выраженному в килобайтах? 1) 10 2) 64 3) 80 4) 512 Решение: 1) так как частота дискретизации 64 Гц, за одну секунду запоминается 64 значения сигнала 2) глубина кодирования не задана! 3) используется 32 = 25 уровня дискретизации значения сигнала, поэтому на один отсчет приходится 5 бит
4) время записи 4 мин 16 с = 4 ´ 60 + 16 = 256 с 5) за это время нужно сохранить 256 ´ 5 ´ 64 бит = 256 ´ 5 ´ 8 байт = 5 ´ 2 Кбайт = 10 Кбайт 6) таким образом, правильный ответ – 1.
[1] Как мы увидим далее, при использовании других методов решения, это условие принципиально облегчает решение данной задачи. Во всех известных автору вариантах подобных задач такое упрощающее условие было.
Воспользуйтесь поиском по сайту: ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|