Question

C++
Калькулятор
Имеется калькулятор, который выполняет три операции:
прибавить к числу X единицу;
умножить число X на 2
умножить число X на 3
Определите, какое наименьшее число операций необходимо для того, чтобы получить из числа 1 заданное число N
Входные данные
Программа получает на вход одно число, не превосходящее 10^6.
Выходные данные

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

Ввод
5
Вывод
3

Answer 1

Ответ:

#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:

• #include <vector>
• #include <algorithm>

2) Заводим переменную n и ее считываем:

• int n = 0;
• cin >> n;

3) Заводим вектор result для подсчета минимального числа операций для каждого значения n. Т.к. в С++ нумерация начинается с 0, а делать сдвиг на 1 неудобно, сразу сделаем вектор большего размера на 1 (тогда минимальное число операций будет храниться в n-ой ячейке, а не (n-1)-ой). Значение первой ячейки сразу приравниваем к 0 (есть во входных данных):

• vector<int> result(n+1);
• result[1] = 0;

4) Потом объявляем переменную maxx. В нее кладем очень большое значение, которое точно никогда не будет достигнуто (знаем, что во вход. данных число ≤ $10^{6}$, т.е. надо просто взять значение больше хотя бы на 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]. Это и есть ответ.

• cout << result[n];

#SPJ1