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

(The Last Inch) КЕГЭ- 5. Модель решения

Разбор задания КЕГЭ-5 из Тренировочного вариант №1

Для решения напишем программу перевода числа в троичную систему (она может быть востребована и в других заданиях).
Сложнее понять до какого значения надо перебирать N?
Ответ можно определить исходя из того, что количество значащих цифр в числе после преобразования увеличивается на две.
Это дает понимание, что число точно увеличивается.
Код будет большим, так как требования к преобразованию разные и "большие". Подпрограмму надо проверить по выводу (промежуточная печать результатов - ОБЯЗАТЕЛЬНА) и двум веткам.

def f(n): # возможно, можно написать короче, но все согласно условию
  s = [] # список для цифр перевода
  while n > 0 : # перевод в троичную систему (пока в обратном порядке)
    s.append(n % 3) 
    n = n // 3
  s = s[::-1] # возврат порядка следования
  R = '' # инициализация ответа
  if sum(s) % 4 == 0 : # проверка условия на сумму цифр троичной записи
    for a in s : # замена 1 на 2 - можно упростить через %3 - но будет сложнее понимать
      if a == 1 : R = R + '2' # замена 1 на 2
      elif a == 2 : R = R + '1' # замена 2 на 1
      else : R = R + str(a)  # остальное (0) оставляем
    R = '10' + R # слева добавили 10
  else : # иначе (не кратно 4) - другой алгоритм
    s = s + [2, 0] # дописали справа 20
    s[1], s[2] = 0, 2 # заменили 2 и 3 разряд (помним, что нумерация в списке с нуля)
    for a in s : # преобразовали в строку (считаем, что про join забыли)
      R = R + str(a) # порядок цифр нужный
  return R # обязательно НАДО проверить правильность работы
n, A, B = 0, 302, 2**100  # инициализация параметров задания
ans = 0 # инициализация ответра
while n < A : # восходящая модель
  n += 1 # увеличение n
  R = int(f(n), 3) # получение результата и перевод в 10-ю СС (для отладки - удобнее переводить здесь)
  if R > A and R <= B : # проверка на минимальность
    ans, B = n, R # фиксация новых значений
    print(n, R, f(n)) # промежуточная печать результатов !!!
print('Ответ в последней строке. Он равен', ans)   #  вывод результата

Разбор задания КЕГЭ-5 из Тренировочного вариант №2

Задача 5.
На вход алгоритма подаётся натуральное число N (N>8). Алгоритм строит по нему новое число R следующим образом.
1. Строится троичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число N делится на 3, то к этой записи в конец дописываются три первые троичные цифры;
б) если число N на 3 не делится, то сумма цифр полученной троичной записи умножается на 5,
переводится в троичную систему счисления и дописывается в конец числа.
Полученная таким образом запись является троичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Укажите минимальное нечётное число R, большее 2500, которое может быть получено с помощью описанного алгоритма.
В ответе запишите это число в десятичной системе счисления.

Это задание упрощенный клон задания из первого варианта. Легко понять, что число R>3*N (дописываем ненулевое число цифр),
значит поиск по n можно ограничить значением 2500
Ответ в задании получается сразу и от небольшого n. Это "усложняет проверку, поэтому можно организовать нисходящий метод для проверки

def f0(n) : # перевод числа в троичную - возврат списка
  s = [] # список для цифр перевода
  while n > 0 : # перевод в троичную систему (пока в обратном порядке)
    s.append(n % 3) 
    n = n // 3
  s = s[::-1] # возврат порядка следования
  return s
  
def f(n): # возможно, можно написать короче, но все согласно условию
  s= f0(n) # начальный перевод в троичную 
  R = '' # инициализация ответа
  if n % 3 == 0 : # проверка кратности 3 числа n
    s = s + s[:3] # дублируем три "левых" в "конец"
  else : # иначе (не кратно 3) - другой алгоритм
    k =sum(s) # вычисление суммы цифр троичной записи
    t = f0(5*k) # новый перевод в троичную
    s = s + t # дописали справа
  for a in s : # преобразовали в строку (считаем, что про join забыли)
      R = R + str(a) # порядок цифр нужный
  return R # обязательно НАДО проверить правильность работы
n, A, B = 8, 2500, 2**1024  # инициализация параметров задания
ans = 0 # инициализация ответра
while n < A : # восходящая модель
  n += 1 # увеличение n
  R = int(f(n), 3) # получение результата и перевод в 10-ю СС (для отладки - удобнее переводить здесь)
  if R > A and R <= B  and R % 2 == 1: # проверка на минимальность
    ans, B = n, R # фиксация новых значений
    print(R, n, f(n)) # промежуточная печать результатов !!!
print('Ответ в последней строке. Он равен', B)   #  вывод результата (он равен R, а не n)

Разбор задания КЕГЭ-5 из Тренировочного вариант №3

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится троичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если сумма цифр троичной записи кратна 3, то все нули в записи меняются на 1, а все 1 меняются на 0,
после к числу приписывается 10 слева;
б) если сумма цифр троичной записи не кратна 3, то к записи справа приписывается 101,
после первые 2 разряда меняются на 22, разряды нумеруются слева направо, начиная с 1.
Полученная таким образом запись является троичной записью искомого числа R.
Укажите минимальное число N, для которого результатом работы алгоритма является наименьшее число R, превышающее 314.
В ответе это число запишите в десятичной системе счисления.

Это задание упрощенный клон задания из первого варианта. Легко понять, что число R>3*N (дописываем ненулевое число цифр),
значит поиск по n можно ограничить значением 314 - далее будет намного больше
Изменим вариант решения, выделив еще подпрограмму перевода числа из десятичной системы.

def f0(n, p =3) : # перевод числа в троичную - возврат списка
  s = [] # список для цифр перевода
  while n > 0 : # перевод в троичную систему (пока в обратном порядке)
    s.append(n % p) 
    n = n // p
  s = s[::-1] # возврат порядка следования
  return s

def f(n): # возможно, можно написать короче, но все согласно условию
  s = f0(n) # переводим в троичную и даже "не портим n"
  R = '' # инициализация ответа
  if sum(s) % 3 == 0 : # проверка условия на сумму цифр троичной записи
    for a in s : # замена 1 на 2 - можно упростить через %3 - но будет сложнее понимать
      if a == 0 : R = R + '1' # замена 0 на 1, можно записать R += '1'
      elif a == 1 : R = R + '0' # замена 1 на 0, можно записать R += '0'
      else : R = R + str(a) # остальное (2) оставляем, можно записать R += str(a)
    R = '10' + R # слева добавили 10
  else : # иначе (не кратно 4) - другой алгоритм
    s = s + [1, 0, 1] # дописали справа 20
    s[0], s[1] = 2, 2 # заменили 2 и 3 разряд (помним, что нумерация в списке с нуля)
    for a in s : # преобразовали в строку (считаем, что про join забыли)
      R = R + str(a) # порядок цифр нужный
  return R # обязательно НАДО проверить правильность работы
n, A, B = 0, 314, 2**100  # инициализация параметров задания
ans = 0 # инициализация ответра
while n < A : # восходящая модель
  n += 1 # увеличение n
  R = int(f(n), 3) # получение результата и перевод в 10-ю СС (для отладки - удобнее переводить здесь)
  if R > A and R < B : # проверка на минимальность (второе строгое, так как нужно минимальное) 
    ans, B = n, R # фиксация новых значений
    print(n, R, f(n)) # промежуточная печать результатов !!!
print('Ответ в последней строке. Он равен', ans)   #  вывод результата

Печать