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

Типа 23 КЕГЭ

Есть система команд

надо из числа a получить число b
(a>1, b<100)

Для решения создаем матрицу переходов A и находим (E-A)^-1
Это даст ответ для всех значений
Используем numpy

import numpy as np
N =101
A = np.zeros((N,N), dtype = float)
for i in range(1, N): 
  if i+2 < N: A[i,i+2] = 1.0
  if i+3 < N: A[i,i+3] = 1.0
  if i * 5 < N: A[i,i*5] = 1.0
#E = np.eye(N)
ans_m = np.round(np.linalg.power(A)).astype('int64')
x, y = 1, 100
print(f'{x=} -> {y=} равно {ans_m[x,y]}')

import numpy as np
N =201
k = 50
A = np.zeros((N,N), dtype = 'int64')
for i in range(1, N): 
  if i+2 < N: A[i,i+2] = 1.0
  if 0 < i -3 < N: A[i,i-3] = 1.0
  if i * 7 < N: A[i,i*7] = 1.0
ans_m = np.linalg.matrix_power(A,k)
zmax = np.max(ans_m)
xy = [(x,y) for x in range(N) for y in range(N) if ans_m[x,y] == zmax]

print(f'max - {k} - = {zmax} для  {xy}')

Формулировка задачи
Исполнитель Калькулятор умеет выполнять несколько команд:

Прибавить 7
Отнять 3
Умножить на 2
Поделить нацело на 5

Все операции совершаются на отрезке от A до B (включительно) - то есть, начальное число и все результаты операций
должны принадлежать отрезку [A;B]
Например, если A= 1, B=100, а на экране число x, то для:

x = 2 можно выполнить 1 и 3 команды (получить 9= x + 7 и 4 = x * 2)
x = 99 можно выполнить 2 и 4 команды (получить 96 = 99 - 3 и 19=99//5

Возможные задания:

Известно, что Исполнитель выполнил ровно N команд. Определите количество траекторий,
переводящих заданное число x в заданное число y
Известно, что Исполнитель выполнил не более N команд. Определите количество траекторий,
переводящих заданное число x в заданное число y.
Известно, что Исполнитель выполнил ровно N команд. Определите x, y, такие что количество траекторий,
переводящих число x в число y максимально
Для "направленного" (ацикличного) набора команд :
Опеределите общее количество траекеторий, переводящих x в y (определить для всех пар)
Для "направленного" (ацикличного) набора команд :
Для заданных x,y найти длину траектории, при которой количество вариантов траекторий максимально

import numpy as np
a, b, c = 1,3,2
P, Q, N = 100, 200, 1000
M = Q - P +1
Z = np.zeros((M, M), dtype = float)
for x in range(P, Q+1):
  i = x - P
  if (x + a) <= Q: Z[i, i + a] += 1.0
  if (x + b) <= Q: Z[i, i + b] += 1.0
  if (x * c) <= Q: Z[i, x * c - P ] += 1.0 
E = np.eye(M)
ans_m = np.round(np.linalg.inv(E-Z)).astype('int64')
      
      
x, y = P, Q
print(f'{x=} -> {y=} равно {ans_m[x-P,y-P]}')

Печать