C++
Калькулятор
Имеется калькулятор, который выполняет три операции:
прибавить к числу X единицу;
умножить число X на 2
умножить число X на 3
Определите, какое наименьшее число операций необходимо для того, чтобы получить из числа 1 заданное число N
Входные данные
Программа получает на вход одно число, не превосходящее 10^6.
Выходные данные
Требуется вывести одно число: наименьшее количество искомых операций.
Примеры:
Ввод
32718
Вывод
17
Ввод
5
Вывод
3
Answers & Comments
Ответ:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n = 0;
cin >> n;
vector<int> result(n+1);
result[1] = 0;
int maxx = 10000001;
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;
}
cout << result[n];
}
Объяснение:
Это задача на динамическое программирование (будем считать каждое следующее значение с помощью предыдущих).
1) Подключаем дополнительно две библиотеки: vector и algorithm:
2) Заводим переменную n и ее считываем:
3) Заводим вектор result для подсчета минимального числа операций для каждого значения n. Т.к. в С++ нумерация начинается с 0, а делать сдвиг на 1 неудобно, сразу сделаем вектор большего размера на 1 (тогда минимальное число операций будет храниться в n-ой ячейке, а не (n-1)-ой). Значение первой ячейки сразу приравниваем к 0 (есть во входных данных):
4) Потом объявляем переменную maxx. В нее кладем очень большое значение, которое точно никогда не будет достигнуто (знаем, что во вход. данных число ≤ [tex]10^{6}[/tex], т.е. надо просто взять значение больше хотя бы на 1):
5) Теперь сама динамика. Идем в цикле по массиву result, начиная со второй ячейки (первая уже заполнена, нулевая нас не интересует).
Там мы считаем 3 значения:
Для подсчета значений point2 и point3 используем тернарный оператор (можно использовать if). Если в ячейку таким образом прийти нельзя, кладем туда недостижимое значение maxx, которое точно больше всех остальных, чтобы не учитывать его при посчете минимального кол-ва способов.
Наконец, используя эти данные, вычисляем значение в текущей ячейке. Берем минимум из всех этих значений (понятно, что если point2 или point3 равны maxx (т.е. таким образом прийти нельзя), то значение в них просто не учитывается) и прибавляем 1, для обозначения, что еще один шаг сделан. Минимум вычисляем с помощью функции min, которая хранится в библиотеке algorithm.
6) Теперь в каждой ячейке вектора result хранится минимальное кол-во шагов, которое необходимо, чтобы туда прийти. Выводим значение result[n]. Это и есть ответ.
#SPJ1