Калькулятор ограничение по времени на тест2 секунды ограничение по памяти на тест64…
- User
Калькулятор ограничение по времени на тест2 секунды ограничение по памяти на тест64 мегабайта вводстандартный ввод выводстандартный вывод Имеется калькулятор, который выполняет три операции:
-
Прибавить к числу X единицу.
-
Умножить число X на 2.
-
Умножить число X на 3.
Определите, какое наименьшее число операций необходимо для того, чтобы получить из числа 1 заданное число N.
Входные данные
Реши через ДП, на с++
-
- Assistant
В данной задаче можно использовать динамическое программирование для решения. Для каждого числа от 1 до N мы будем находить минимальное число операций, необходимых для получения этого числа из 1. Для этого можно использовать массив dp[], где dp[i] будет хранить минимальное количество операций для числа i.
Изначально, dp[1] = 0, так как для получения числа 1 нам не требуется ни одной операции.
Затем, мы будем перебирать числа от 2 до N и каждый раз находить минимальное количество операций для текущего числа. Для этого мы будем рассматривать три возможных предыдущих числа, из которых можно получить текущее число i: i-1, i/2 и i/3. Тогда, минимальное количество операций для числа i можно найти как минимум из трех вариантов:
- dp[i-1] + 1,
- если i делится на 2, то dp[i/2] + 1,
- если i делится на 3, то dp[i/3] + 1.
Таким образом, можно выразить формулу для нахождения dp[i]: dp[i] = min(dp[i-1] + 1, dp[i/2] + 1 (если i делится на 2), dp[i/3] + 1 (если i делится на 3))
После нахождения всех значений dp[], ответом на задачу будет dp[N].
Ниже приведена реализация алгоритма на C++:
#include <iostream> #include <vector> #include <algorithm> using namespace std; int minimumOperations(int N) { vector<int> dp(N + 1, INT_MAX); // массив для хранения минимальных количеств операций dp[1] = 0; // базовый случай for (int i = 2; i <= N; i++) { dp[i] = min(dp[i], dp[i - 1] + 1); // прибавление 1 к предыдущему числу if (i % 2 == 0) { dp[i] = min(dp[i], dp[i / 2] + 1); // умножение на 2 } if (i % 3 == 0) { dp[i] = min(dp[i], dp[i / 3] + 1); // умножение на 3 } } return dp[N]; } int main() { int N; cin >> N; int result = minimumOperations(N); cout << result << endl; return 0; }Пример работы программы: Входные данные: 10 Выходные данные: 5
Объяснение: Для получения числа 10 из 1 требуется выполнить следующие операции: 1+1=2, 22=4, 43=12, 12/3=4, 4*2=8, 8+1=9, 9+1=10. Итого, нам понадобилось 5 операций.