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

Answer 2

Для решения данной задачи можно использовать алгоритм динамического программирования.

Создадим массив dp размером N+1, где dp[i] будет хранить минимальное количество операций, необходимых для получения числа i.

Инициализируем dp[1] = 0, так как нам не нужно выполнять никаких операций, чтобы получить число 1.

Далее, для каждого числа i от 2 до N, будем рассматривать три возможных операции и выбирать минимальное количество операций из них:

1. Если число i делится на 3 без остатка, то можно получить число i путем выполнения операции умножения на 3. То есть, dp[i] = dp[i/3] + 1.

2. Если число i делится на 2 без остатка, то можно получить число i путем выполнения операции умножения на 2. То есть, dp[i] = dp[i/2] + 1.

3. В остальных случаях, можно получить число i путем выполнения операции прибавления 1. То есть, dp[i] = dp[i-1] + 1.

Выбираем минимальное значение из трех возможных операций и записываем его в dp[i].

В конце алгоритма, значение dp[N] будет содержать минимальное количество операций, необходимых для получения числа N.

Пример решения для числа 32718:

1. Инициализация: dp[1] = 0.

2. Для числа 2: - dp[2] = min(dp[2/3] + 1, dp[2/2] + 1, dp[2-1] + 1) = min(dp[0] + 1, dp[1] + 1, dp[1] + 1) = min(1, 1, 1) = 1.

3. Для числа 3: - dp[3] = min(dp[3/3] + 1, dp[3/2] + 1, dp[3-1] + 1) = min(dp[1] + 1, dp[1] + 1, dp[2] + 1) = min(1, 1, 2) = 1.

4. Для числа 4: - dp[4] = min(dp[4/3] + 1, dp[4/2] + 1, dp[4-1] + 1) = min(dp[1] + 1, dp[2] + 1, dp[3] + 1) = min(1, 2, 2) = 1.

5. Продолжаем вычисления для всех чисел до N.

6. В конце, dp[32718] будет содержать минимальное количество операций, равное 17.

Таким образом, для числа 32718 необходимо выполнить 17 операций, чтобы получить число N.

Аналогично можно решить задачу для числа 5, получив минимальное количество операций, равное 3.