Статья Автор: Лебедев Дмитрий

Разбор варианта Статграда (2024.10.24). Часть 2 (2.8.12.16.19-20-21.23)

Вторая часть разбора заданий из варианта Статграда от 24 октября 2024 года
Предлагаются конкретные решения конкретных заданий "средний" сложности.
Разбираются задания базового и повышенного уровня сложности 
Задание 2 Задание 8 Задание 12 
Задание 16 Задание 19-20-21 Задание 23
Разбор не является пособием по решению заданий. Общие подходы можно найти в других разделах  Учебника.

Задание 2 (ссылка на задание)
Логическая функция F задаётся выражением:
(x → (y → z)) ∧ (y → (z ≡ ¬w))
Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F.
???
???
???
???
F
0
0
 
0
0
0
0
 
 
0
 
0
 
 
0
 
Определите, какому столбцу таблицы истинности соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Код программы стандартный и определение последовательности следования аргументов не вызывает проблем.
Чисто "ручное" решение не так очевидно, хотя используя то, что:
  • столбцы должны быть "различны" (иначе решений будет как минимум два, а по формулировке условия оно одно)
  • строка из одних нулей (единиц) не "несет информации"
таблицу можно дополнить, что может упростить "ручное" решение
 
???
???
???
???
F
0
0
1
0
0
0
0
 
1
0
1
0
 
 
0


Задание 8 (ссылка на задание) 
( Компьютерное решение с когнитивным сопроцессором devil)
Определите количество восьмизначных 15-ричных чисел, в записи которых
  • ровно два нуля
  • и не более четырёх цифр, для записи которых используются буквы.
  1. В числе ровно два нуля. Ноль не может быть на 1-м месте. Значит нули занимают два места из 7 возможных. Это 21 вариант. 
  2. Оставшиеся мест занимают цифры и буквы. Возможно два способа решения
  • Для каждого числа можем составить "маску" из 0 и 1, где 0 соответствует цифре, а 1 - букве
    переберем все маски длины 6  ( 26 вариантов) и оставим только те, в которых не более 4-х единиц
    для каждой маски найдем k - число единиц. Количество чисел, соответствующей маске будет равно
    \(5^k \cdot 9^{6-k} \) (букв пять, а цифр (без нуля) - 9)
  • Пусть k - количество цифр числа выраженных буквами. Тогда для них можно выбрать \(C_6^k\) вариантов позиций в числе, 
    а количество таких чисел будет равно \(5^k \cdot 9^{6-k} \)   (букв пять, а цифр (без нуля) - 9). 
    Таким образом надо в цикле по k найти сумму \(C_6^k\cdot 5^k \cdot 9^{6-k} \)
В коде приведены оба решения (в  виде подпрограмм), в которых количество разрядов фиксировано (поэтому сочетания используются как константы), а мощность алфавита является "вводимым" параметром


Задание 12 (ссылка на задание)
Исполнитель Редактор получает на вход строку цифр и преобразует её.
Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
А) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150.
Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.
Б) нашлось (v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Дана программа для Редактора:
НАЧАЛО
ПОКА нашлось (111)
  заменить (111, 2)
  заменить (222, 11)
  заменить (1, 2)
КОНЕЦ ПОКА
КОНЕЦ
Определите количество таких натуральных N из интервала [123 456 794; 678 901 234],
для которых в результате применения данной программы к строке, состоящей из N единиц, получится строка, состоящая только из двоек.

Очевидно, что запускать программу на "требуемом" интервале значений бесполезно, но попробуем позапускать программу на небольших интервалах, чтобы понять как будет "вести себе результат"
Реализуем программу и будем выводить "нужные" строки для интервала значений 


Нетрудно заметить, что программа выводит только строки
  • 22
  • 222
  • 2222
причем, с повтором через каждые 16 значений, то есть период в 16 и в каждом периоде таких значений 3
(проанализировав алгоритм несложно понять, что только такие последовательности и могут получаться frown)
Добавим в вывод остаток от 16


Нужные последовательности получаются при остатках 9, 10, 0. 
Попробуем подсчитать для отрезка [A; B]
Задача
Пусть [A, B]. Сколько чисел на этом отрезке имеют остаток x  по модулю P.
Решение:
  • "сдвинем" отрезок на x - [A-x, B-x]. Тогда достаточно определить сколько чисел на этом отрезке.
  • это значение можно найти как разницу \(N_B^P - N_{A-1}^P\ где,\ N_K^P - \) количество чисел отрезка [1; K] кратных P
  • достаточно легко понять, что \(N_K^P = K//P\)
  • таким образом, ответ равен значению \((B-x)//P - (A-1-x)//P\)
Далее, чтобы не ошибиться и не "тратить  силы", найтем ответ как сумму трех значений
(границы отрезка забьем как константы) 


Задания 19-21 (ссылка на задание)
Правила игры:
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может выполнить любое из следующих трёх действий: 1) убрать из кучи один камень; 2) если количество камней в куче кратно трём, уменьшить его в три раза, в противном случае убрать из кучи два камня; 3) если количество камней в куче кратно пяти, уменьшить его в пять раз, в противном случае убрать из кучи три камня.
Например, если в куче 12 камней, то за один ход можно получить 11, 4 или 9 камней.
Игра завершается, когда количество камней в куче становится не более 19.
Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 19 или меньше камней.
В начале игры в куче было S камней, S > 19.
Задание 19: Укажите минимальное значение S, при котором Петя не может выиграть первым ходом, но при любом первом ходе Пети Ваня может выиграть своим первым ходом
Задание 20: найдите два наименьших значения S, при которых Петя не может выиграть первым ходом, но у Пети есть выигрышная стратегия, позволяющая ему выиграть вторым ходом при любой игре Вани.
Задание 21: найдите минимальное значение S, при котором у Вани есть стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, но у Вани нет стратегии, которая позволила бы ему гарантированно выиграть первым ходом.
Приведен "стандартный" код решения. Поясним порядок его получения и поиск ответов

Поясним ход решения и процесс написания программы
  1. Создаем и отлаживаем подпрограмму def pi(pos). Это подпрограмма возвращаетмножество значений ("Образ"),
    в которые можно попасть из позиции pos.
    Проверяем работу для значений pos кратных/не кратных 3 и 5
  2. Определяем переменную swin, которая определяет условие окончания игры (для этого варианта swin=19
    (делаем её вводимой, для возможности посмотреть процесс)
    Определяем множество "стартовых позиций" St - по условию оно неограничено, но вопросы касаются только 4 "тактов", 
    значить "максимальное движение/уменьшение" равно 5*5*5*5 =625 (на практике можно брать значительно меньше)
  3. Пишем процедуру def step0(S), возвращающую множество значений (W1), для которых у Пети есть "выигрышная стратегия"(ВС) в один ход. 
    Для этого "пробегаем" значении  множества S и проверяем, что не все точки "образа" лежат внутри множества S
    Запускаем W1=step0(St), определяем "оставшиеся" позиции (St=St-W1) и можем, для вывести размеры множеств W1, St (для понимания, что происходит)
  4. Используя "copy-paste" создаем программу step1(S,X), которая "отбирает" в множестве S все точки, "образ" которых лежит в множестве X.
    Запуск L1=step1(St,W1) позволит получить ответ на задание 19, так как множество L1 будет множеством позиций, для которых выигрышная стратегия в один ход есть у Вани. Выводим L1 в "удобном" порядке.  Определяем "оставшиеся" позиции (St=St-L1)
  5. Используя "copy-paste" создаем программу step2(S,X), которая "отбирает" в множестве S все точки, "образ" которых имеет не пустое пресечение с множеством X.
    Запуск W2=step2(St,L1) позволит получить ответ на задание 20, так как множество W2 будет множеством позиций, для которых выигрышная стратегия в два хода есть у Пети. Выводим W2 в "удобном" порядке. Определяем "оставшиеся" позиции (St=St-W2)
  6.  Для дальнейшего решения не надо создавать новых программ.
    Запуск L2 = step1(St,W1.union(W2)) позволит получить ответ на задание 21, так как множество L2 будет множеством позиций, для которых выигрышная стратегия в неболее чем два хода есть у Вани. Выводим L2 в "удобном" порядке.
Полученный код (более 30 строк) может показаться "большим", но "простота" его написания ("copy-paste") и "универсальность" позволяют использовать данный код на экзамене 
Код программы приведен  в "упрощенном" виде (без лишних переносов, комментариев - как на экзамене)


Задание 16 (ссылка на задание)
Функция F(n), где n – натуральное число, задана следующими соотношениями:
  • F(n) = n, если n < 3;
  • F(n) = (n – 1) × F(n – 2), если n ≥ 3.
Чему равно значение выражения (F(2025) – F(2023)) / F(2021)?
Задание должно решаться без написания кода. Для решения нужно
  • выразить F(2025) через F(2023) \(F(2025)=2024\cdot F(2023)\)
  • упростить числитель \(F(2025)-F(2023)=2024\cdot F(2023)-F(2023)=2023\cdot F(2023)\)
  • выразить F(2023) через F(2021) \(F(2023)=2022\cdot F(2021)\)
  • ответом будет 2023*2022 = 4090506
Приведем "программное" решение, опирающееся на принцип динамического программирования
Поясним алгоритм программы
  • необходимые начальные значения записываются в словарь dp={1:1, 2:2}
  • рекурсия оформлена ввиде подпрограммы f16
  • рекурсия имеет "две линейки" - одна для нечётных значений аргументов, другая для чётных.
    Нас интересует "нечётная", поэтому начальное значение n=1 (строка 7)
  • запускаем вычисление рекурсии с "небольшим" шагом (взяли 100, строка 9).
    Размер шага не должен превышать допустимую глубину рекурсии (обычно это 1000)
  • ответ вычисляем от значений словаря dp, а не от результата "вызова" функций
Запуск позволяет убедиться, что программа  получает нужный результат


Задание 23 (ссылка на задание)
Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены буквами:
  1. Вычти 2
  2. Найди целую часть от деления на 2
  3. Найди целую часть от деления на 3
Программа для исполнителя – это последовательность команд.
Сколько существует программ, которые преобразуют исходное число 40 в число 4
и при этом траектория вычислений содержит число 20?

 

Ответом на задание будет значение \(N_{40}^{20}\cdot N_{20}^4,\ где \ N_x^y - \) количество программ, преобразующих x в y
Достаточно написать программу для нахождения \(N_x^y\), а умножение выполним "вручную"
Поясним текст программы для нахождения \(N_x^y\)
  • значения x (старт) и y (финиш) будем считывать с клавиатуры и запишем в список SF (старт, финиш)
    Запись в список "делает глобальными" значения  x,y ("избавляет" от необходимости передавать их в подпрограмму
  • для решения применим метод "снизу - вверх", поэтому значение в точке "финиш" определим в 1 (DP={SF[1]:1})
  • создадим подпрограмму f23(p), в которой
    • будем проверять, что p "между стартом и финишем" (строка 2)
    • вычислялось ли значение от p (строка 3)
    • вычислять значение от p используя "прямые" команды 
      Использование метода "снизу-вверх" как раз и обусловлено тем, что "обратные" команды написать сложнее
  • запустим подпрограмму f23 от "старта" и выведем результат (строка 8) 

Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация
Печать