Как решить задачу калькулятор на питон
Надо придумать функцию которая решает задачу и запрограммировать её.
fn — минимальное чиcло шагов для получения n из единицы. Что про неё можно сказать?
- f1 = 0 — это, я думаю, объяснять не нужно.
- fk+1 ≤ 1 + fk — потому что fk+1 не может быть больше, иначе нарушится требование минимальности (обоснование опущено, но вы должны это хорошо понимать);
- f2k ≤ 1 + fk — следущее правило, обоснование аналогично;
- f3k ≤ 1 + fk — аналогично.
Все условия переведены на язык формул. Вычисление f:
def f(n): if n == 1: return 0 v = f(n - 1) if n % 2 == 0: v = min(v, f(n // 2)) if n % 3 == 0: v = min(v, f(n // 3)) return v + 1 print(f(int(input()))) Для маленьких n работает хорошо, после сотни тормозит, для больших чисел падает с переполнением стека. Теория хороша, практика не очень.
Проблема в том что мы очень много раз вычисляем одни и те же значения fn. Можно сделать оценку, что количество вызовов растет как e n . Чтобы избавится от повторных вызовов, значения функции надо запоминать в кэше:
import functools @functools.lru_cache(None) def f(n): if n == 1: return 0 v = f(n - 1) if n % 2 == 0: v = min(v, f(n // 2)) if n % 3 == 0: v = min(v, f(n // 3)) return v + 1 print(f(int(input()))) Кэш всё ускоряет, но проблема с глубиной рекурсии остаётся. Чиним её: вычисляем значения f последовательно от единицы до n, вычисленные значения храним в списке cache и используем по необходимости. Рекурсии нет и нет проблем с её глубиной:
def f(n): cache = [0] * (n + 1) for i in range(2, n + 1): v = cache[i - 1] if i % 2 == 0: v = min(v, cache[i // 2]) if i % 3 == 0: v = min(v, cache[i // 3]) cache[i] = v + 1 return cache[-1] print(f(int(input()))) Имеется калькулятор который выполняет три операции
Разбор добавил Влад Макеев
Задача Аналогичеа предыдущей, только выводя ответ, мы просматриваем числа X из которых могло быть получено обрабатываемое число K и если A[X] + 1 = A[K] то K было получено из X.
- Прибавить к числу X единицу.
- Умножить число X на 2.
- Умножить число X на 3.
Определите кратчайшую последовательность операций, необходимую для получения из числа 1 заданное число N.
Входные данные
Программа получает на вход одно число N, не превосходящее 10 6 .
Выходные данные
Выведите строку, состоящую из цифр «1», «2» или «3», обозначающих одну из трех указанных операций, которая получает из числа 1 число N за минимальное число операций. Если возможных минимальных решений несколько, выведите любое из них. ��
Пример
Решение задачи Калькулятор с Яндекс Контест
Имеется калькулятор, который выполняет следующие операции:
умножить число X на 2;
умножить число X на 3;
прибавить к числу X единицу.
Определите, какое наименьшее количество операций требуется, чтобы получить из числа 1 число N.
Код
Скопировать код
n = int(input()) a = [0, 0, 1, 1] b = [0, 0, 1, 1] if n == 1: print(0, '\n', 1, sep="") raise SystemExit elif n == 2: print(1) print(1, 2) raise SystemExit elif n == 3: print(1) print(1, 3) raise SystemExit for i in range(4, n + 1): mn = 10000000000000000000000000000000000000000000000 if i % 3 == 0: mn = a[i // 3] if i % 2 == 0: mn = min(mn, a[i // 2]) mn = min(a[i - 1], mn) a += [mn + 1] if i % 3 == 0 and a[i // 3] == mn: b += [i // 3] elif i % 2 == 0 and a[i // 2] == mn: b += [i // 2] else: b += [i - 1] lt = [n] t = b[n] c = a[n] while c != 0: lt += [t] t = b[t] c = a[t] lt += [1] print(len(lt) - 1) print(*lt[::-1])
         
Автор: Администратор
Имеется калькулятор который выполняет три операции
Разбор добавил Влад Макеев
Простая динамика, где A[i] — сколько нужно операций чтобы получить это число.
- Прибавить к числу X единицу.
- Умножить число X на 2.
- Умножить число X на 3.
Определите, какое наименьшее число операций необходимо для того, чтобы получить из числа 1 заданное число N.
Входные данные
Программа получает на вход одно число, не превосходящее 10 6 .
Выходные данные
Требуется вывести одно число: наименьшее количество искомых операций.