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

Глава 4. Объем сообщения и рекурсивный алгоритм

Задача №7. Информационный объем памяти

Введем определения. Мощность алфавита – количество символов, используемых в алфавите. Обозначим буквой M.

Если нам нужно закодировать сообщение, написанное в алфавите мощностью M, при помощи компьютерных кодов, т.е. в алфавите мощностью 2, то для кодирования всех символов исходного алфавита нам нужно под каждый символ выделить такое количество бит i (вес одного символа), чтобы выполнялось условие M <= 2ⁱ.

Тогда информационный объем сообщения I, содержащего N символов, будет равен: I = n · i, где i– весь одного символа, n – число символов.

I = log₂ M · n (формула Хартли).

Если log₂M не является целым числом, округляем значение в большую сторону.

При оцифровке звука в памяти запоминаются только отдельные значения сигнала. Чем чаще записывается сигнал, тем лучше качество записи.

Частота дискретизации f – это количество преобразований аналогового сигнала в цифровой за одну секунду. Измеряется в Герцах (Гц).

Глубина кодирования (а также разрешение) – это количество бит, выделяемое на одно преобразование сигнала. Измеряется в битах (бит).

Возможна запись нескольких каналов: одного (моно),

двух (стерео), четырех (квадро).

Обозначим частоту дискретизации – f (Гц), глубину кодирования – B (бит), количество каналов – k, время записи – t (с).

Тогда объем записанного файла

V (бит) = f · B · k · t.

Объем изображения обозначим буквой V, тогда V=k*i, где k – разрешающая способность (количество пикселей по горизонтали и вертикали), i – количество бит для кодирования 1 пикселя (цвета). Количество цветов в изображении вычисляется по формуле N=2ⁱ

Пример 7.1

Растровое изображение в разрешении 300 ppi сохранили в палитре, содержащей 65536 цветов. Размер полученного изображения составил 40 Мбайт. После чего для места было решено использовать палитру, содержащую 256 цветов, и разрешение до 150 ppi. Известно, что цвет каждого пикселя кодируется возможным количеством бит, общим для всех пикселей. Определите размер после преобразования файла в Кбайт. В ответе запишите только число.

Решение:

Изменение разрешения – операция, которая меняет количество пикселей в документе по горизонтали и вертикали. Следовательно, при уменьшении разрешения вдвое количество пикселей уменьшится в 2*2= 4 раза (по вертикали 2 и горизонтали 2).

В начальном документе используется 2¹⁶ = 65536 цветов, значит, на один пиксель отводится по 16 бит. В преобразованном документе 2⁸=256 цветов, или на один пиксель отводится 8 бит. Следовательно, объем документа уменьшается вдвое (16/8=2).

В соответствии с этими выводами посчитаем объем преобразованного документа, переведя единицы измерения информации в килобайты. Т.е. если изображение изменили и оно уменьшилось, значит, начальный объем делим на изменения, которые посчитали выше. Итого имеем:

40/ (4*2) *2¹⁰ = 5120 (умножаем на 2^10, чтобы перевести в килобайты).

Ответ: 5120.

Пример 7.2

Для хранения произвольного растрового изображения размером 128×320 пикселей отведено 20 Кбайт памяти без учёта размера заголовка файла. Для кодирования цвета каждого пикселя используется одинаковое количество бит, коды пикселей записываются в файл один за другим без промежутков. Какое максимальное количество цветов можно использовать в изображении?

Решение:

Разрешение k=128*320, I=20КБ=20*2^10*2³ БИТ. I=k*i, i=I/k, i= (40*2¹⁰*2³) / (128*320) =8 – на каждый цвет 8 бита. Количество цветов найдем по формуле N=2ⁱ, N=2⁸=256.

Ответ: 256.

Пример 7.3

Музыкальный фрагмент длительностью 5 минут был записан в формате квадро (четырехканальная запись), частотой дискретизации 40 кГц и 16-ти битным разрешением. Сжатие данных не производилось. Определите объем получившегося файла в МБайтах. В качестве ответа укажите минимальное ЦЕЛОЕ количество Мбайт, которого будет достаточно для хранения файла.

Решение:

Найдем объем файла в битах:

𝑆 = 4 * (6 * 60) * (40 * 1000) * 16 = 921600000 бит. 5*60 – перевод в секунды, 40*1000 – перевод в герцы.

Переведем в МБайты:

S = 921600000/ (2¹⁰ *2¹⁰ * 8) =109,8=110 – округляем в большую сторону, если же округлять в меньшую сторону до 109, то объема не хватит для хранения файла.

Ответ: 109.

Пример 7.4

Музыкальный фрагмент был записан в формате стерео (двухканальная запись), оцифрован и сохранен в виде файла без использования сжатия данных. Размер полученного файла без учета размера заголовка файла – 45 Мбайт. Затем тот же музыкальный фрагмент был записан повторно в формате квадро, оцифрован с разрешением в 4 раза ниже и частотой дискретизации в 2 раза выше, чем в первый раз. Сжатие данных не производилось. Укажите размер в Мбайт файла, полученного при повторной записи. В ответе запишите только целое число, единицу измерения писать не нужно. Искомый объем не учитывает размера заголовка файла.

Решение:

Проанализируем условие.

Запись в формате стерео преобразовали в запись в формате квадро – это значит, что размер увеличен вдвое, то умножаем на 2.

Разрешение в 4 раза ниже – значит, делим на 4.

Частота дискретизации вдвое выше – размер в 2 раза больше, то умножаем на 2.

Следовательно, имеем:

45 ∙ 2 ∙ 2/4 = 45

Ответ: 45.

Пример 7.5

Музыкальный фрагмент был оцифрован и записан в виде файла без использования сжатия данных. Размер полученного файла составил 30 Мбайт. Получившийся файл был передан в город А по каналу связи за 15 секунд. Затем тот же музыкальный фрагмент был оцифрован повторно с разрешением в 2 раза меньше и частотой дискретизации в 3 раза выше, чем в первый раз. Сжатие данных не производилось. Полученный файл был передан в город Б за 9 секунд. Определите среднюю скорость передачи в пункт Б в Мбайт/сек.

Решение:

Формула скорости передачи:

𝑣 = 𝑆*t, где v – скорость передачи, S – объем файла, t – время передачи.

Узнаем размер преобразованного файла, аналогично предыдущей задаче.

𝑆2 = 30 ∙ 3/2 = 45

Найдем скорость:

𝑣2 = 45/9 = 5

Ответ: 5.

Пример 7.6

В велокроссе участвуют 28 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Какой объем памяти будет использован устройством, когда все спортсмены прошли финиш?

Решение:

По формуле Хартли, объем сообщения I, написанного в исходном алфавите мощностью M, содержащего N символов, будет равен: I = log₂M · N.

В нашем случае мощность алфавита (все символы, подлежащие кодированию) M = 28. N тоже = 28, так как все спортсмены прошли финиш.

Тогда I = log₂28 · 28 ≈ 5 · 28 = 140 бит. (берем цифру 5, т.к. нам нужно получить значение 2^x> =28, тогда x=5)

Ответ: 140.

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

Задача 7.7

Автоматическая фотокамера каждые 3 секунды создаёт черно-белое растровое изображение, содержащее 256 оттенков. Размер изображения – 128 x 192 пикселей. Все полученные изображения и коды пикселей внутри одного изображения записываются подряд, никакая дополнительная информация не сохраняется, данные не сжимаются. Сколько Мбайтов нужно выделить для хранения всех изображений, полученных за сутки?

Задача7.8

Музыкальный фрагмент длительностью 5 минут был записан в формате квадро (четырехканальная запись), частотой дискретизации 40 кГц и 16-ти битным разрешением.

Сжатие данных не производилось. Определите объем получившегося файла в МБайтах. В качестве ответа укажите минимальное ЦЕЛОЕ количество Мбайт, которого будет достаточно для хранения файла.

Задача №8. Комбинаторика

Комбинаторика (или комбинаторный анализ) – раздел математики, объектом исследования которого являются дискретные множества произвольной природы. Основной задачей комбинаторики является определение числа способов выполнения некоторых точно определенных операций или, другими словами, определение числа подчиненных тем или иным условиям комбинаций, которые можно составить из заданной совокупности объектов. Для решения комбинаторных задач из ЕГЭ необходимо знать 3 формулы и понимать, в каких задачах их можно применять. Факториалом числа n называется произведение всех натуральных чисел от 1 до числа n включительно: n! = 1 • 2 • 3 … • n. Число перестановок из n элементов равно факториалу. P_n=n! – формула говорит о том, что можно разместить n предметов на n различных местах, причем n встречается только один раз.

Пример 8.1

Рассмотрим следующую задачу: 6 карточек пронумерованы числами 1, 2, 3, 4, 5, 6. Карточки наугад выкладываем в ряд. Сколько при этом можно получить различных шестизначных чисел?

Решение:

На первое место можно положить одну из 6 карточек. Для этого есть 6 способов. В каждом из этих 6 способов на второе место можно положить одну из оставшихся 5 карточек. Таким образом, существует 5 • 6 =30 способов, чтобы положить карточки на первое и второе места. В каждом из этих 30 способов на третье место можно положить одну из оставшихся 4 карточек. Следовательно, существует 4 • 5 • 6 = 120 способов, чтобы положить карточки на первое, второе и третье места. И так далее, пока не останется одна карточка. Таким образом, при выкладывании карточек можно получить 1*2*3*4*5*6! = 720=6! шестизначных чисел.

Ответ: 720.

Если же необходимо, можно разместить n предметов на n различных местах, причем n встречается любое количество раз, тогда применяем формулу P=n^m. n – количество символов в алфавите, m – количество вариантов, которое необходимо составить.

Пример 8.2

Некоторый алфавит содержит четыре различные буквы. Сколько пятибуквенных слов можно составить из букв данного алфавита (буквы в слове могут повторяться)?

Решение:

Количество символов в алфавите равно четырем, значит n=4. Количество вариантов, которое необходимо составить, равно 5, значит, m=5. P=4⁵=1024.

Ответ: 1024.

Размещениями из n элементов по m (мест) называются такие выборки, которые, имея по m элементов, выбранных из числа данных n элементов, отличаются одна от другой либо составом элементов, либо порядком их расположения.

Число размещений из n по m обозначается A_n^m и определяется по формуле:

A_n^m =n!/ (n – m)!

Пример 8.3

Необходимо выбрать в подарок 4 из 10 имеющихся различных книг. Сколькими способами можно это сделать?

Решение:

A₄¹⁰=10!/4!*6!=210

Ответ: 210.

Теперь разберем задания, которые можно решить ручным способом и с помощью компьютера.

Пример 8.4

Игорь составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Игорь использует трёхбуквенные слова, в которых могут быть только буквы Ш, К, О, Л, А, причём буква К появляется ровно 1 раз. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем. Сколько различных кодовых слов может использовать Игорь?

Способом решения задачи программирования на языке Python решение будет выглядеть так:

 
r = 0
for a in 'ШКОЛА': # задаем строку школа и в переменную а поочередно помещаем буквы из школа
    for b in 'ШКОЛА':
        for c in 'ШКОЛА':
            word = a + b + c # составляем трехбуквенное слово из всевозможных комбинаций
            if word.count('К') == 1: # если количество букв а ровно одному, то увеличиваем счетчик
                 r += 1
print(r)
 

Теперь решим эту же задачу ручным способом.

На первом месте может стоять 4 буквы, на втором – тоже 4 буквы, на третьем месте одна буква К. Итого получаем: 4*4=16, всего таких вариантов может быть 3. 16+16+16=48

Ответ: 48.

Пример 8.5

Игорь составляет 8-буквенные коды из букв И, Г, О, Р, Ь. Буквы О и Ь должны встречаться в коде ровно по одному разу, при этом буква Ь не может стоять на первом месте. Остальные допустимые буквы могут встречаться произвольное количество раз или не встречаться совсем. Сколько различных кодов может составить Игорь?

Данную задачу проще всего решить cпособом программирования на языке Python, попробуйте сами.

Решение:

 
r = 0
for a in 'ИГОР':
    for b in 'ИГОРЬ':
        for c in 'ИГОРЬ':
            for d in 'ИГОРЬ':
                for e in 'ИГОРЬ':
                    for f in 'ИГОРЬ':
                        for g in 'ИГОРЬ':
                            for i in 'ИГОРЬ':
                                word = a + b + c + d + e + f + g + i
                                if word.count («О») == 1 and                                             word.count («Ь») 
                               == 1 and word [0]!=«ь»:
                                    r += 1 # 0 встречается 1 раз, мягкий знак 1 раз и на первом месте не стоит мягкий знак
print(r)
 

Решим еще и ручным способом данную задачу.

Если буква «О» стоит на первом месте, то всего вариантов 3⁶=729. Т.к. буква «ь» знак может стоять только на 7-ми местах, то 729*7=5103 вариантов.

Если буква «О» стоит 2-ом месте, то, зная, что мягкий знак не на первом, то остается 729*6=4374 вариантов с мягким знаком, где, буква «О» может стоять на 2,3,4,5,6,7,8 местах – итого имеем 7 мест для буквы О. Итак сложим варианты, в которых буква «О» стоит на первом месте и где буква «О» стоит на втором месте, 5103+4374*7=35721

Ответ: 35721

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

Задача 8.6

Семен составляет слова из букв А, Б, В, Г, Д, Е, Ж. Сколько слов длиной 6 может составить Семен? Если на первой и последней позициях могут быть только гласные буквы, на остальных – только согласные. Под словом понимается любая буквенная последовательность, необязательно осмысленная. Каждая буква может входить в слово любое количество раз.

Задача 8.7

Семен составляет слова путем перестановки букв в слове ОБОЙМА. Сколько слов может составить Семен, если гласные и согласные буквы должны чередоваться? Под словом понимается любая буквенная последовательность, необязательно осмысленная.

Задача 8.8

Вася составляет 5-буквенные слова, в которых есть только буквы З, И, М, А, причём в каждом слове есть ровно одна гласная буква и она встречается ровно 1 раз. Каждая из допустимых согласных букв может встречаться в слове любое количество раз или не встречаться совсем. Словом, считается любая допустимая последовательность букв, необязательно осмысленная.

Сколько существует таких слов, которые может написать Вася?

Глава 5. Электронные таблицы и текстовый редактор

Задача №9. Электронные таблицы

В этом разделе будет дана теоретическая часть по заданиям в Microsoft Excel. Необходимо знать и понимать, как работают функции:

=Сумм () – суммирует значения выделенного диапазона;

=Суммесли () – позволяет суммировать ячейки, которые удовлетворяют определенному критерию (заданному условию).

Диапазон – ячейки, которые следует оценить на основании критерия (заданного условия).

Критерий – определяет, какие ячейки из диапазона будут выбраны (записывается в кавычках). Например =СУММЕСЛИ (B2:B25;"> 5») – суммирует ячейки в диапазоне от B2 до B25, если их значения больше 5;

=счетесли () – можно подсчитать количество ячеек, отвечающих определенному условию (например, число клиентов в списке из определенного города). Например, =СЧЁТЕСЛИ (A2:A5;«Лондон») – подсчитывает количество ячеек в диапазоне от А2 до А5, в которых есть слово Лондон;

=СРЗНАЧ () – считает среднее арифметическое по заданному диапазону;

=Макс () и = Мин () – подсчитывает максимальное и минимальное значение в заданном диапазоне.

Microsoft Excel (в дальнейшем просто – Excel) – это программа выполнения расчетов и управления так называемыми электронными таблицами. Excel позволяет выполнять сложные расчеты, в которых могут использоваться данные, расположенные в разных областях электронной таблицы и связанные между собой определенной зависимостью. Для выполнения таких расчетов в Excel существует возможность вводить различные формулы в ячейки таблицы. Excel выполняет вычисления и отображает результат в ячейке с формулой. Важной особенностью использования электронной таблицы является автоматический пересчет результатов при изменении значений ячеек. Excel также может строить и обновлять графики, основанные на введенных числах. Адрес ячейки в электронных таблицах состоит из имени столбца и следующего за ним номера строки, например. Для написания формул используют адреса ячеек и знаки арифметических операций (+, -, *, /, ^). Формула начинаетcя знаком =. Диапазон ячеек обозначается следующим образом:

A1:D4 (диапазон всех ячеек прямоугольника от A1, A2, A3, A4, B1, B2, B3, B4, С1, С2, С3, С4, D1, D2, D3, D4).

Адреса ячеек бывают относительными, абсолютными и смешанными. Они по-разному ведут себя при копировании формулы из ячейки в ячейку.

Относительная адресация. Если в ячейке B2 мы напишем формулу =D1+3, то таблица воспримет это как «взять значение ячейки на две правее и на одну выше текущей и прибавить к нему 3».

То есть адрес D1 воспринимается таблицей как положение относительно ячейки, куда вводится формула. Такой адрес называется относительным. При копировании такой формулы в другую ячейку таблица автоматически пересчитает адрес относительно нового расположения формулы:

Абсолютная адресация. Если нам не нужно, чтобы адрес пересчитывался при копировании формулы, мы можем его «закрепить» в формуле – поставить знак $ перед буквой и индексом ячейки: =$D$1+3. Такой адрес называется абсолютным. Такая формула не будет изменяться при копировании, т.е. адрес останется тем же =$D$1+3.

Смешанная адресация. Если же мы хотим, чтобы при копировании формулы автоматически пересчитывался, к примеру, только индекс ячейки, а буква оставалась неизменной, мы можем «закрепить» в формуле только букву (или наоборот): =$D1+3. Такой адрес называется смешанным. При копировании формулы будет меняться только индекс в адресе ячейки, т.е. будет меняться цифра 1 на какую-то другую в зависимости от места вставки формулы:

Пример 9.1

Откройте файл электронной таблицы, содержащей вещественные числа, – результаты ежечасного измерения температуры воздуха на протяжении трёх месяцев. Найдите разность между максимальным значением температуры и её средним арифметическим значением.

В ответе запишите только целую часть получившегося числа.

Решение:

Ссылка на файл с решением https://yadi.sk/i/spSGUCu09Ijfhg

С помощью функции находим =МАКС (B37:Y92) =38 – находим максимальное значение. Далее с помощью функции =СРЗНАЧ (B2:Y92) =23,7 – находим среднее арифметическое значение. Находим разность =B95-E95=38—23,7=14,3

Ответ: 14.

Пример 9.2

Электронная таблица содержит результаты ежечасного измерения температуры воздуха на протяжении трёх месяцев. Определите, сколько раз за время наблюдений температура в 8:00 была выше среднесуточной температуры того же дня.

Решение:

Ссылка на файл с решением https://yadi.sk/i/r5lpexM6ha21AA

Подсчитаем среднесуточную температуру по дням. В ячейки z2 введем формулу =СРЗНАЧ (B2:Y2). Протянем ее вниз до z92, чтобы относительно скопировались значения, которые находятся в скобках формулы. После подсчитаем, когда температура была выше среднесуточной. Для этого в ячейки АА2 введем формулу =ЕСЛИ (J2> Z2;1;0). Протянем ее вниз до AA92, чтобы относительно скопировались значения, которые находятся в скобках формулы. Подсчитаем количество таких дней через формулу =СУММ (AA2:AA92) =30.

Ответ: 30.

Пример 9.3

В ячейке C2 записана формула =$T$3+D2. Какой вид приобретет формула, после того как ячейку C2 скопируют в ячейку B1?

1) =$D$3+D2 2) =$T$3+C1

3) =$T$3+E3 4) =$F$4+D2

Решение:

Место расположения формулы меняется с C2 на B1, т.е. формула сдвигается на одну ячейку влево и на одну ячейку вверх (буква «уменьшается» на единицу и индекс уменьшается на единицу). Значит, так же изменятся все относительные адреса, а абсолютные (закрепленные знаком $) останутся неизменными: =$T$3+С1. Можно также открыть программу Excel, ввести формулу, что в условии задачи, скопировав формулу =$T$3+D2 и вставив в B1, мы поймем, что это формула =$T$3+С1

Ответ: 2.

Пример 9.4

Дан фрагмент электронной таблицы:

В ячейку D1 введена формула =$B$1*В1+С2, а затем скопирована в ячейку D2. Какое значение в результате появится в ячейке D2?

1) 14 2) 10 3) 16 4) 24

Решение:

Место расположения формулы меняется с D1 на D2, т.е. буква не меняется, а индекс увеличивается на 1. Значит, формула примет вид: =$B$1*В2+С3. Подставим в формулу числовые значения ячеек:1*5+9=14. Правильный ответ указан под номером 1.

Ответ: 1.

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

Задача 9.5

Откройте файл электронной таблицы 9—0.xls (ссылка на файл https://yadi.sk/i/4Op4P__V2HdB-g), содержащей вещественные числа, – результаты ежечасного измерения температуры воздуха на протяжении трёх месяцев. Найдите разность между средним арифметическим и минимальным значениями температуры в июне во второй половине дня (с 12:00). В ответе запишите только целую часть получившегося числа.

Задача 9.6

Электронная таблица содержит результаты ежечасного измерения температуры воздуха на протяжении трёх месяцев. (ссылка на файл https://yadi.sk/i/q7ALBqaJzAOUiw) Определите, сколько раз за время измерений результат очередного измерения оказывался выше результата предыдущего на 2 и более градусов.