Тур 1 Вариант 1 Задача 4 "Детали"

Задача 4

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

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

В ответе укажите целое число.

Решение:

Мощность алфавита – это количество символов в этом алфавите. Если алфавит имеет мощность К, то количество всех возможных «слов» (символьных цепочек) длиной N (без учета смысла) равно  Q=K^N.

С помощью М бит можно закодировать 2^М различных вариантов (чисел).

1)    Посчитаем количество бит, необходимых для кодирования  детали первым и вторым способом, при К=2, используется набор из двух разных символов При первом способе каждый символ кодируется 1 битом. 2¹=2.  3·1=3, т.е. вся конструкция кодируется 3 битами. При втором способе, количество деталей, которые можно закодировать 2³ = 8. Для кодирования необходимо 3 бита. В первом случае требуется столько же бит информации для записи обозначения одной детали, сколько и во втором случае.

2)  Продолжим:

К=	Способ 1	Способ 2	Разница
3 4	3·2=6	33 = 27 < 25 43 = 26	6 − 5 = 1 6 − 6 = 0
5	3·3=9	53 = 125 < 27	9 − 7 = 2

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

Ответ: 5.

2 тур Вариант Пробный Задача №4

Задача 4

Цифровой фотоаппарат в режиме серийной съемки работает следующим образом:

1. Несжатое цифровое изображение, кодированное в 24-х битной цветовой модели RGB, помещается в буферную память.
2. Процессор производит сжатие этого изображения и записывает файл со сжатым изображением на карту памяти, после чего удаляет несжатое изображение из буфера. На всем протяжении работы алгоритма сжатия все несжатое изображение должно полностью находиться в памяти. Процессор может сжимать одновременно только одно изображение и не может прерывать этот процесс.
3. Если в буфере нет достаточного объема памяти для того, чтобы поместить целиком очередное изображение, съемка серии прекращается, причем не поместившийся кадр теряется. Это единственное ограничение максимального количества кадров в серии. Если совпадает момент времени, в который происходит удаление сжатого кадра и появление нового снятого кадра, то снятый кадр будет записан в буфер и обработан.

Размер кадра составляет 3648 x 2736 пикселей. Скорость сжатия одного кадра составляет 150 миллисекунд. Скорость серийной съемки составляет 8 кадров в секунду (первый кадр будет в буфере доступен для сжатия через 1/8 секунды после начала съемки). Размер буфера составляет 100 МБайт. Определите максимальное количество кадров в серии. В ответе укажите целое число.

При решении задачи необходимо учесть следующие допущения:

1. Время на размещение несжатого изображения в буфере, время на запись сжатого изображения на карту памяти и время на удаление несжатого изображения из буфера считаем несущественным по сравнению со временем работы алгоритма сжатия и не учитываем в расчетах.

Карта памяти имеет достаточный объем для записи серии из любого количества снимков, возможного для данного фотоаппарата.

Решение:

1) В 24-х битной цветовой модели один пиксель кодируется 24 / 8 = 3 (байтами).

2) Объем одного снимка (3648 x 2736 х 3)/1024 = 29 241 Кбайт » 29 Мбайт. Т.е в буферной памяти может находиться не более 3 снимков.

3) По условию, скорость серийной съемки составляет 8 кадров в секунду, скорость сжатия одного кадра составляет 150 миллисекунд. Т.е. скорость сжатия 6 ⅔ снимков в секунду.

4) Найдем время заполнения буферной памяти. Обозначим за t  время заполнения.

Составим уравнение: 8·t − 6 ⅔ · (t − ⅛) = 3.  Находим t = 13/8 секунд. 

5) За 13/8 секунд можно сделать 13 снимков, т.е. максимальное количество кадров в серии 13.

Ответ: 13

2 Тур Вариант Пробный Задача №1

Задача №1

Петя произвел ряд измерений и записал результаты в ячейки диапазона A1:A16 электронной таблицы. После чего построил по этим значениям график:

 

Потом Петя решил обработать эти данные и последовательно помещал в ячейку B1 формулы вида =СРЗНАЧ(А1:А#), где # принимало значение от 2 до 5, а затем копировал эту ячейку в ячейки диапазона B2:B16 и строил графики по значениям диапазона B1:B16. В результате Петя получил 4 графика, обозначенные ниже латинскими буквами A, B, C и D.

Решение:

1) Из Графика условия задания заполним данные столбца А.

2) Заполним первую строку таблицы результатами вычисления формул СРЗНАЧ(А1:А2), СРЗНАЧ(А1:А3), СРЗНАЧ(А1:А4) и СРЗНАЧ(А1:А5) .

Три значения совпадают, следовательно график С отображает значение “5” в формуле.

3) Продолжим заполнение таблицы данными. Заполним вторую строку таблицы результатами вычисления формул СРЗНАЧ(А2:А3), СРЗНАЧ(А2:А4) и СРЗНАЧ(А2:А5). Заполним третью строку таблицы результатами вычисления соответствующих формул.

4) Проанализируем полученные данные:

·         набор (2; 2,5; 2) дает «пик» на графике, т.е. график  В отображает значение “2” в формуле;

·         набор (2; 2,3; 2,6) дает «плавный рост» на графике, т.е. график  А отображает значение “3” в формуле;

·         график D отображает значение “4” в формуле. 

		=СРЗНАЧ(А1:А2)	=СРЗНАЧ(А1:А3)	=СРЗНАЧ(А1:А4)	=СРЗНАЧ(А1:А5)
	А	В
1	1	2	2	2	2,5
2	3	2,5	2,3	2,75
3	2	2	2,6	2,75
4	2
5	4
6	3
7	7
8	5
9	3
10	7
11	3
12	4
13	6
14	2
15	3
16	4

 

Ответ:  BADC