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

Разбор Статграда от 2024-12-17. Часть 3( 16, 19-20-21, 23)

Задание 16
Функция F(n), где n – натуральное число, задана следующими соотношениями:
F(n) = F(n/2) + 3, если чётно;
F(n) = F(n/3) + 2, если n нечётно и при этом кратно 3;
F(n) = 0, если n нечётно и не кратно 3.
Определите минимальное значение n, для которого F(n) = 70.
Задание очень похоже на стандартное, поэтому попробуем применить решение динамическим программированием (будем сохранять промежуточные результаты) ... и потерпим частичное фиаско 
В этой "песочнице" программу выполнить не получиться,  поскольку для решения потребовалось около двух минут процессорного времени.
(Ответ 37748736)


 А попробуем ускорить решение и вложиться в 10 секунд.
Представим n в виде n = 2tn.( n1 - нечётное) Тогда: 
F(n)= F(2tn1) =F(2t-1n1)+3 =...= F(n1)+3*t  
n1 - нечётное, значит можно представить как n1 = 3p*n2, (n2  - нечётное и не кратно 3 => F(n2)=0). Тогда:
F(n1)= F(3pn2) =F(3p-1n2)+2 = ...=F(n2)+2*p  
Таким образом, если n=2t3pm (m  - нечётное и не кратно 3), то F(n)=F(2t3p) = 3t+2p
Осталось найте решение диофантового уравнения 3t+2p = 70 
t n
22 2 22232
20 5 22035
Запустим для n =22232


Задание 23
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которые обозначены буквами:
A. Вычти 3
B. Если число чётное, Раздели на 2, Иначе Вычти 5

Программа для исполнителя – это последовательность команд.
Сколько существует программ, которые преобразуют исходное число 36 в число 3
и при этом траектория вычислений не содержит числа 12?
Условие стандартное. Решать можно динамикой. Возможны два вариант решения
  1. Функцию пишем как в условии. В 'end' (3) записываем 1 и запускаем от 'start' (36)
  2. Функцию пишем в обратном порядке. В 'start' (36) записываем 1 и запускаем от 'end'(3)
Используем:
  • словарь sf, где записаны позиции старта и окончания траекторий
  • множество zap со значениями запрещенных вершин
  • словарь dp с вычисленными значениями количества траекторий
  • проверку принадлежности числа x отрезку [A;B] осуществляем через (x-A)(x-B) <= 0, что позволяет не различать случаи A<B и A>B 


Программа очень похожа на программу для задания 16.
Ниже второй вариант. В  нём команды обращены в "будущее". 
Несложно понять, что n всегда получается из 2n и, если n чётное, то и из n+5 (будет нечётным)


Задания 19-20-21
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя.
За один ход игрок может выполнить любое из следующих действий:
1) убрать из кучи пять камней;
2) если количество камней в куче чётно, уменьшить его в два раза;
3) если количество камней в куче кратно трём, уменьшить его в три раза;
4) если количество камней в куче нечётно и не кратно трём, добавить один камень.
Условие и вопросы (будут ниже) стандартные, хотя ходы могут уменьшать размер кучи, но и увеличивать
(при этом после двух ходов размер кучи гарантированно уменьшается)
 Метод решения состоит в следующем (основные шаги стандартного подхода):
  • Пишется функции pi, получающая следующие позиции
  • Пишем step0 и получаем множество W1 - победные поля для Пети в 1 ход 
  • Пишем step1 и получаем множество L1 - победные поля для Вани  в 1 ход
    (это ответ на задание 19)
  • Пишем step2 и получаем множество W2 - победные поля для Пети  в 2 хода
    (это ответ на задание 20)
  • Ещё раз применяем step1 и получаем множество L2 - победные поля для Вани  в 2 хода
    (это ответ на задание 21)


В функции Step0 изменена проверка позиции на "выигрышность" - проверяется, что в "образе" минимальный элемент "выигрышный" (это логичный, но частный подход, вызван "двунаправленностью" правил ходов в игре)
Задание 19
Укажите минимальное значение S, при котором Петя не может выиграть первым ходом,
но при любом первом ходе Пети Ваня может выиграть своим первым ходом.

ответ: 25

Задание 20
найдите два наименьших значения S, при которых Петя не может выиграть первым ходом, но у Пети есть выигрышная стратегия, позволяющая ему выиграть вторым ходом при любой игре Вани.
В ответе запишите найденные значения в порядке возрастания.

ответ: 40, 43
Задание 21
найдите минимальное значение S, при котором у Вани есть стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, но у Вани нет стратегии, которая позволила бы ему гарантированно выиграть первым ходом

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