Тема 9. Обработка, хранение, передача информации.

Тип 1. Какой минимальный объём памяти (в Кбайт) нужно зарезервировать, чтобы можно было сохранить любое растровое изображение размером 128 на 256 пикселов при условии, что в изображении могут использоваться 64 различных цвета? В ответе запишите только целое число, единицу измерения писать не нужно.

Тип 2. Рисунок размером 64 на 128 пикселей занимает в памяти 7 Кбайт (без учёта сжатия). Найдите максимально возможное количество цветов в палитре изображения.

Тип 3. Музыкальный фрагмент был оцифрован и записан в виде файла без использования сжатия данных. Получившийся файл был передан в город А по каналу связи за 12 секунд. Затем тот же музыкальный фрагмент был оцифрован повторно с разрешением в 2 раза выше и частотой дискретизации в 3 раз выше, чем в первый раз. Сжатие данных не производилось. Полученный файл был передан в город Б; пропускная способность канала связи с городом Б в 2 раза выше, чем канала связи с городом А. Сколько секунд длилась передача файла в город Б?

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

Тип 5. У Васи есть доступ к Интернет по высокоскоростному одностороннему радиоканалу, обеспечивающему скорость получения им информации 2¹⁷ бит в секунду. У Пети нет скоростного доступа в Интернет, но есть возможность получать информацию от Васи по низкоскоростному телефонному каналу со средней скоростью 2¹⁶ бит в секунду. Петя договорился с Васей, что тот будет скачивать для него данные объемом 8 Мбайт по высокоскоростному каналу и ретранслировать их Пете по низкоскоростному каналу. Компьютер Васи может начать ретрансляцию данных не раньше, чем им будут получены первые 1024 Кбайт этих данных. Каков минимально возможный промежуток времени (в секундах), с момента начала скачивания Васей данных, до полного их получения Петей? В ответе укажите только число, слово «секунд» или букву «с» добавлять не нужно.

Тип 6. Документ объёмом 20 Мбайт можно передать с одного компьютера на другой двумя способами:

А. Сжать архиватором, передать архив по каналу связи, распаковать.

Б. Передать по каналу связи без использования архиватора.

Какой способ быстрее и насколько, если:

• средняя скорость передачи данных по каналу связи составляет 2²⁰ бит в секунду;
• объём сжатого архиватором документа равен 60% исходного;
• время, требуемое на сжатие документа, – 10 секунд, на распаковку – 2 секунды?

В ответе напишите букву А, если быстрее способ А, или Б, если быстрее способ Б. Сразу после буквы напишите число, обозначающее, на сколько секунд один способ быстрее другого.

Так, например, если способ Б быстрее способа А на 50 секунд, в ответе нужно написать Б50.

Единицы измерения «секунд», «сек.», «с.» к ответу добавлять не нужно.

Тип 7. После преобразования растрового 256-цветного графического файла в 4-цветный формат его размер уменьшился на 18 Кбайт. Каков был размер исходного файла в Кбайтах?

Тема 10. Комбинаторика.

Тип 1. Вася составляет 6-буквенные слова, в которых есть только буквы К, А, Н, Т, причём буква К используется в каждом слове ровно 2 раза. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?

Тип 2. Сколько слов длины 5, начинающихся с согласной буквы и заканчивающихся гласной буквой, можно составить из букв К, У, М, А? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.

Тип 3. Все 5-буквенные слова, составленные из букв П, О, Р, Т, записаны в алфавитном порядке и пронумерованы. Вот начало списка:

ООООО

ООООП

ООООР

ООООТ

ОООПО

……

Какое количество слов находятся между словами ТОПОР и РОПОТ (включая эти слова)?

Тип 4. Все 4-буквенные слова, составленные из букв М, А, Р, Т, записаны в алфавитном порядке. Вот начало списка:

АААА

АААМ

АААР

АААТ

……

Запишите слово, которое стоит на 250 -м месте от начала списка.

Тип 5. Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка:

ААААА

ААААК

ААААР

ААААУ

АААКА

……

Укажите номер слова УКАРА.

Тип 6. Вася составляет 6-буквенные слова, в которых есть только буквы С, Л, О, Н, причём буква С используется в каждом слове ровно не менее 2х раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?

Тип 7. Необходимо составить таблицу кодовых слов для передачи секретного сообщения. В качестве кодовых слов используются 5-буквенные слова, в которых присутствуют только буквы из слова РАКУШКА, причем первая буква должна быть либо Р, либо К; последняя буква должна быть гласной. В каждом слове должно быть не менее трех гласных букв. Сколько различных кодовых слов можно использовать?

Тип 8. Сколько существует различных символьных последовательностей длины 3 в четырёхбуквенном алфавите {A,B,C,D}, если известно, что одним из соседей A обязательно является D, а буквы B и C никогда не соседствуют друг с другом?

Тема 11. Рекурсия.

Тип 1. Ниже записаны две рекурсивные процедуры: F и G:

procedure F(n: integer); forward; procedure G(n: integer); forward; procedure F(n: integer); begin if n > 0 then G(n - 1); end; procedure G(n: integer); begin writeln('*'); if n > 1 then F(n - 2); end;

def F(n): if n > 0: G(n - 1) def G(n): print('*') if n > 1: F(n - 2)

Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F(11)?

Тип 2. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(0) = 1, F(1) = 1

F(n) = 2*F(n–1) + F(n-2), при n > 1

Чему равно значение функции F(6)? В ответе запишите только целое число

Тип 3. Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1; G(1) = 1;

F(n) = 2*F(n–1) – G(n–1),

G(n) = 2*F(n–1) + G(n–1), при n >=2

Чему равно значение величины F(5)-G(5)? В ответе запишите только целое число.

Тип 4. Дан рекурсивный алгоритм

procedure F(n: integer); begin writeln('*'); if n > 0 then begin F(n-2); F(n-2); F(n div 2); end end;

def F(n): print('*') if (n > 0): F(n - 2) F(n - 2) F(n // 2)

Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(6)?

Тип 5. Дан рекурсивный алгоритм:

procedure F(n: integer); begin if n > 0 then begin writeln('*'); F(n-2); F(n-1); F(n-1); end; writeln('*'); end;

def F(n): if (n > 0): print("*") F(n - 2) F(n - 1) F(n - 1) print("*")

Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(5)?

Тип 6. Дан рекурсивный алгоритм

procedure F(n: integer); begin writeln(n); if n < 6 then begin writeln(n); F(n+1); F(n+2); F(n*2) end end;

def F(n): print(n) if (n < 6): print(n) F(n + 1) F(n + 2) F(n * 2)

Найдите сумму чисел, которые будут выведены при вызове F(1)

Тип 7. Ниже записаны две рекурсивные функции, F и G:

function F(n: integer): integer; begin if n > 2 then F:= F(n - 1) + G(n - 2) else F:= n; end; function G(n: integer): integer; begin if n > 2 then G:= G(n - 1) + F(n - 2) else G:= n+1; end;

def F(n): if n > 2: return F(n - 1) + G(n - 2) else: return n def G(n): if n > 2: return G(n - 1) + F(n - 2) else: return n+1

Чему будет равно значение, вычисленное при выполнении вызова F(6)?

Тип 8. Дан рекурсивный алгоритм:

function F(n: integer): integer; begin if n < 6 then F:= n+F(n+3) * F(2*n) else F:= n*2; end;

def F(n): if (n < 6): return n + F(n + 3) * F(2 * n) else: return n * 2

Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(3)?