Имеется калькулятор который выполняет три операции
Перейти к содержимому

Имеется калькулятор который выполняет три операции

  • автор:

Как решить задачу калькулятор на питон

Надо придумать функцию которая решает задачу и запрограммировать её.

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.
Выходные данные

SheWhoRunsOnTheWaves

Это задача на динамическое программирование (будем считать каждое следующее значение с помощью предыдущих).

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 значения:

  1. point1 — кол-во операций в предыдущей ячейке
  2. point2 — кол-во операций в ячейке, из которой можно прийти в эту умножением на 2 (только если возможно из нее прийти, т.е. если ее номер делится на 2)
  3. 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-сообщество

[RSS Feed]

  • Начало
  • » Центр помощи
  • » Задача «Калькулятор с восстановлением ответа»

#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] — сколько нужно операций чтобы получить это число.

  1. Прибавить к числу X единицу.
  2. Умножить число X на 2.
  3. Умножить число X на 3.

Определите, какое наименьшее число операций необходимо для того, чтобы получить из числа 1 заданное число N.

Входные данные

Программа получает на вход одно число, не превосходящее 10 6 .

Выходные данные

Требуется вывести одно число: наименьшее количество искомых операций.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *