Как решить задачу калькулятор на питон
Надо придумать функцию которая решает задачу и запрограммировать её.
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())))
C++ Калькулятор
Имеется калькулятор, который выполняет три операции:
прибавить к числу X единицу;
умножить число X на 2
умножить число X на 3
Определите, какое наименьшее число операций необходимо для того, чтобы получить из числа 1 заданное число N
Входные данные
Программа получает на вход одно число, не превосходящее 10^6.
Выходные данные
Это задача на динамическое программирование (будем считать каждое следующее значение с помощью предыдущих).
1) Подключаем дополнительно две библиотеки: vector и algorithm:
2) Заводим переменную n и ее считываем:
3) Заводим вектор result для подсчета минимального числа операций для каждого значения n. Т.к. в С++ нумерация начинается с 0, а делать сдвиг на 1 неудобно, сразу сделаем вектор большего размера на 1 (тогда минимальное число операций будет храниться в n-ой ячейке, а не (n-1)-ой). Значение первой ячейки сразу приравниваем к 0 (есть во входных данных):
- vector result(n+1);
- result[1] = 0;
4) Потом объявляем переменную maxx. В нее кладем очень большое значение, которое точно никогда не будет достигнуто (знаем, что во вход. данных число ≤ , т.е. надо просто взять значение больше хотя бы на 1):
- int maxx = 10000001;
5) Теперь сама динамика. Идем в цикле по массиву result, начиная со второй ячейки (первая уже заполнена, нулевая нас не интересует).
Там мы считаем 3 значения:
- point1 — кол-во операций в предыдущей ячейке
- point2 — кол-во операций в ячейке, из которой можно прийти в эту умножением на 2 (только если возможно из нее прийти, т.е. если ее номер делится на 2)
- point3 — кол-во операций в ячейке, из которой можно прийти в эту умножением на 3 (только если возможно из нее прийти, т.е. если ее номер делится на 3)
Для подсчета значений point2 и point3 используем тернарный оператор (можно использовать if). Если в ячейку таким образом прийти нельзя, кладем туда недостижимое значение maxx, которое точно больше всех остальных, чтобы не учитывать его при посчете минимального кол-ва способов.
Наконец, используя эти данные, вычисляем значение в текущей ячейке. Берем минимум из всех этих значений (понятно, что если point2 или point3 равны maxx (т.е. таким образом прийти нельзя), то значение в них просто не учитывается) и прибавляем 1, для обозначения, что еще один шаг сделан. Минимум вычисляем с помощью функции min, которая хранится в библиотеке algorithm.
- for (int i = 2; i < n+1; i++)
- int point1 = result[i-1];
- int point2 = (i % 2 == 0) ? result[i/2] : maxx;
- int point3 = (i % 3 == 0) ? result[i/3] : maxx;
- result[i] = min(min(point1, point2), point3) + 1;
- >
6) Теперь в каждой ячейке вектора result хранится минимальное кол-во шагов, которое необходимо, чтобы туда прийти. Выводим значение result[n]. Это и есть ответ.
Python-сообщество
- Начало
- » Центр помощи
- » Задача «Калькулятор с восстановлением ответа»
#1 Окт. 8, 2021 22:32:23
Fiares_Curie Зарегистрирован: 2021-10-06 Сообщения: 6 Репутация: 0 Профиль Отправить e-mail
Задача «Калькулятор с восстановлением ответа»
Имеется калькулятор, который выполняет три операции:
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.
Определите кратчайшую последовательность операций, необходимую для получения из числа 1 заданное число N.
Входные данные:
Программа получает на вход одно число N, не превосходящее 106.
Выходные данные:
Выведите строку, состоящую из цифр “1”, “2” или “3”, обозначающих одну из трех указанных операций, которая получает из числа 1 число N за минимальное число операций. Если возможных минимальных решений несколько, выведите любое из них.
Мой код:
n = int(input()) x = 1 s = "" while x n: if x*3 n: x *= 3 s = s + "3" elif x*3 == n: s = s + "3" print(s) break elif x*2 n: x *= 2 s = s + "2" elif x*2 == n: s = s + "2" print(s) break elif x+1 n: x += 1 s = s + "1" elif x+1 == n: s = s + "1" print(s) break
Но заходит эта программа только на четырех тестах (из 19). Где ошибки?
#2 Окт. 9, 2021 00:43:28
py.user.next От: Зарегистрирован: 2010-04-29 Сообщения: 9596 Репутация: 836 Профиль Отправить e-mail
Задача «Калькулятор с восстановлением ответа»
Fiares_Curie
Где ошибки?
Подход неправильный. Пиши рекурсивную функцию. Если сделаешь хвостовую рекурсию, то сможешь преобразовать её в цикл. Но я думаю, что тебе и рекурсии будет достаточно для прохождения.
Тут писал ссылку на пример.
Ты делай сам. Или мы сейчас за тебя сделаем эту задачу и ты так ничему и не научишься. Потому что, чтобы научиться чему-то, надо делать это самому, прогонять через свои мозги, искать самому вариант, думать самому. Только так мозги обучаются.
Отредактировано py.user.next (Окт. 9, 2021 00:45:49)
#3 Окт. 9, 2021 21:09:11
xam1816 Зарегистрирован: 2020-05-11 Сообщения: 1259 Репутация: 108 Профиль Отправить e-mail
Задача «Калькулятор с восстановлением ответа»
Это задача из динамического программирования,т.е или по другому нахождение оптимального решения.Мне понимание динамического программирования плохо дается,прямо стена какая-то.
Понравилась цитата“ Динамическое программирование — это когда задачу,которую не понятно как решать,разбиваешь на более мелкие задачи,которые тоже не понятно как решать”
Вот и берем значит задачу типа
Fiares_Curie
Имеется калькулятор, который выполняет три операции:
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.
Определите кратчайшую последовательность операций, необходимую для получения из числа 1 заданное число N.
— чтобы получить 1 из 1 то нужно сделать 0 операций.Это понятно
— чтобы получить 2 из 1 то нужно сделать + 1 операцию,т.е. чтобы получить 1 ничего не надо делать,а 2 уже надо одну операцию
— чтобы получить 3 нужно посмотреть сколько мы делали операций чтобы дойти до 2 и прибавить еще одну операцию(+1) = 2 операции “х+1” нужно сделать. НО у нас есть способ x3,т.е нужно проверить можем ли мы из 3 без остатка попасть к 1 (3%3 == 0),тогда чтобы добраться до 3 нам нужна 1 операция (х3),т.е выбираем минимальное количество операций
— чтобы получить 4 из 1 то смотрим сколько операций получили для 3 и прибавим +1 или как случай выше если (4%2 == 0) то понимаем что из количества операций для 2 мы тоже можем сделать +1 одну операцию “х2”
— чтобы получить 5 из 1,то смотрим сколько операций нужно чтобы получить 4 и прибавляем +1,при этом не забываем проверять есть ли (5%2==0 или 5%3==0)
— чтобы получить n из 1,то смотрим сколько операций нужно для n-1 + 1,проверяем если n%2 ==0,то смотрим сколько нужно операций для n//2 и +1, проверяем если n%3 == 0, то смотрим сколько нужно операций для n//3 + 1,из них выбираем минимальное количество операций
для хранения кол-ва операций для каждого числа используем список
num = int(input('>>>')) a = [0] * (num + 1) # для каждого числа пока заполняем по 0 операций a[1] = 0 # продублирую для наглядности чтобы получить 1 нужно 0 операций for n in range(2, num + 1): # для каждого числа из диапазона minimal = a[n - 1] + 1 # смотрим сколько потребовалось операций для предыдущего и прибавляем if n % 2 == 0: minimal = min(minimal, a[n // 2] + 1) # сравниваем сколько операций потребовалось для n//2+1 if n % 3 == 0: minimal = min(minimal, a[n // 3] + 1) # аналогично a[n] = minimal # заполняем вместо 0 количество операций
затем восстанавливаем события
расписывать не буду,кому надо разберется
operations = [] i = num while i > 1: if a[i] == (a[i-1]+1): operations.insert(0, 1) i -= 1 continue if i%2 == 0 and a[i] == a[i//2]+1: operations.insert(0, 2) i //= 2 continue operations.insert(0, 3) i //= 3 print(a[num])# минимальное количество операций для num print(operations)# примененные операции
Имеется калькулятор который выполняет три операции
Разбор добавил Влад Макеев
Простая динамика, где A[i] — сколько нужно операций чтобы получить это число.
- Прибавить к числу X единицу.
- Умножить число X на 2.
- Умножить число X на 3.
Определите, какое наименьшее число операций необходимо для того, чтобы получить из числа 1 заданное число N.
Входные данные
Программа получает на вход одно число, не превосходящее 10 6 .
Выходные данные
Требуется вывести одно число: наименьшее количество искомых операций.