Задание 37. Стратегии и прочая радость.
5-117. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г использовали соответственно кодовые слова 0, 100, 101, 111. Укажите кратчайшее возможное кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
9-2-78. Музыкальный фрагмент был оцифрован и записан в виде файла без использования сжатия данных. Получившийся файл был передан в город А по каналу связи за 75 секунд. Затем тот же музыкальный фрагмент был оцифрован повторно с разрешением в 2 раза выше и частотой дискретизации в 3 раза выше, чем в первый раз. Сжатие данных не производилось. Полученный файл был передан в город Б за 90 секунд. Во сколько раз скорость пропускная способность канала в город Б больше пропускной способности канала в город А?
11-87. Даны две рекурсивные функции:
function F(n: integer): integer;
begin
if n 1 then
F := F(n - 1) + G(n - 1)
else
F := n;
end;
function G(n: integer): integer;
begin
if n 1 then
G := G(n - 1) + F(n)
else
G := n;
end;
Чему будет равно значение, вычисленное при выполнении вызова F(5)?
12-34. Если маска подсети 255.255.252.0 и IP-адрес компьютера в сети 156.132.15.138, то номер компьютера в сети равен_____
12-39. В терминологии сетей TCP/IP маской подсети называется 32-разрядное двоичное число, определяющее, какие именно разряды IP-адреса компьютера являются общими для всей подсети – в этих разрядах маски стоит 1. Обычно маски записываются в виде четверки десятичных чисел - по тем же правилам, что и IP-адреса. Для некоторой подсети используется маска 255.255.254.0. Сколько различных адресов компьютеров теоретически допускает эта маска, если два адреса (адрес сети и широковещательный) не используют?
18-201. На числовой прямой даны два отрезка: P = [0, 10] и Q = [25, 50]. Отрезок A таков, что формула
(x A) → ((x P) (x Q))
истинна при любом значении переменной x. Определите наименьшую возможную длину отрезка A.
18-202. На числовой прямой даны два отрезка: P = [7, 15] и Q = [12, 25]. Отрезок A таков, что формула
((x P) (x A)) ((x Q) (x A))
истинна при любом значении переменной x. Какое наименьшее количество точек, соответствующих чётным целым числам, может содержать отрезок A?
22-84. Исполнитель Июнь17 преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Прибавить 4
Сколько существует программ, для которых при исходном числе 2 результатом является число 13 и при этом траектория вычислений не содержит число 6?
26-16. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или добавить в кучу десять камней. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 25 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 41. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 41 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 40.
1. При каких S: 1а) Петя выигрывает первым ходом; 1б) Ваня выигрывает первым ходом?
2. Назовите два значения S, при которых Петя может выиграть своим вторым ходом.
3. Назовите два значения S, при которых Ваня выигрывает своим первым или вторым ходом.
26-35. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
добавить в кучу один камень или
увеличить количество камней в куче в три раза и убрать из кучи 2 камня.
Например, имея кучу из 10 камней, за один ход можно получить кучу из 11 или 28 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 31. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 31 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 30.
1. При каких S: 1а) Петя выигрывает первым ходом; 1б) Ваня выигрывает первым ходом?
2. Назовите два значения S, при которых Петя может выиграть своим вторым ходом?
3. Назовите значение S, при котором Ваня выигрывает своим первым или вторым ходом.
26-56. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
а) добавить в кучу один камень;
б) увеличить количество камней в куче в три раза.
Игра завершается в тот момент, когда количество камней в куче становится не менее 33. Если при этом в куче оказалось не более 89 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. В начальный момент в куче было S камней, 1 ≤ S ≤ 32.
Задание 1. а) При каких значениях числа S Петя может выиграть в один ход? Укажите все такие значения и соответствующие ходы Пети.
б) У кого из игроков есть выигрышная стратегия при S = 29, 30, 31? Опишите выигрышные стратегии для этих случаев.
Задание 2. У кого из игроков есть выигрышная стратегия при S = 9, 10? Опишите соответствующие выигрышные стратегии.
Задание 3. У кого из игроков есть выигрышная стратегия при S = 8? Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах – количество камней в позиции.
0
