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

@vitek2000 · Регистрация: 12.04.2021

Студворк — интернет-сервис помощи студентам

Задача с курсов сириуса, прошу смотреть на примеры ввода и вывода, спасибо заранее за помощьв решении задачи (никак не могу код написать)

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

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

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

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

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

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

Примеры
Ввод:
32718
Вывод:
17

Ввод:
1
Вывод:
0

Ввод:
5
Вывод:
3

@alexu_007 · 27.06.2021, 10:23

Сообщение от vitek2000

И в правду мемоизацию надо использовать, динамическое программирование как никак.

А что это такое?

Добавлено через 53 минуты
У меня чёто не хватает интеллекта. Если нету математического решения, остаётся перебор вариантов - а это фантастические цифры.

Можно решать тупо в лоб: пробовать поделить на три, если не делится - пробовать поделить на 2, если не делится - отнимать единицу - но это не гарантирует оптимального варианта.

Кто-то решил? Код не нужен, сам алгоритм?

@vitek2000 · 27.06.2021, 10:29 **[ТС]**

alexu_007, я уже пометил ответ, мемоизация - в программировании сохранение результатов выполнения функций для предотвращения повторных вычислений. Мне не хватало времени с рекурсией, и надо было использовать это, тема цже закрыта.

@TheCalligrapher · 27.06.2021, 19:31

Сообщение от alexu_007

Если нету математического решения, остаётся перебор вариантов - а это фантастические цифры.

В данной задаче каждый перебор вариантов естественным образом опирается на уже выполненные ранее переборы вариантов. Если принять это во внимание, а не заниматься выполнением одних и тех же переборов снова и снова, то "фантастические цифры" сразу же становятся совсем не фантастическими.

@alexu_007 · 27.06.2021, 22:34

Сообщение от woldemas

А что динамика с простой мемоизацией не прокатывает? 10^6 - не так уж много.

Объясните пожалуйста, как работает ваш код. Я вывел на экран значения mem[i] для х = 32718, что означают эти цифры? И как с их помощью получить последовательность, приводящую к правильному результату, например

32718 3 ( /3 )
10906 2 ( /2 )
5453 1 ( -1 )
5452 2
2726 2
1363 1
1362 3
454 2

и так далее. Или в обратном порядке от единицы.

@TheCalligrapher · 27.06.2021, 22:58

Сообщение от alexu_007

Я вывел на экран значения mem[i] для х = 32718

Значение mem[i] - это длина решения для i. Неужели так трудно догадаться?

Сообщение от alexu_007

что означают эти цифры?

Зачем вы выводите mem[i] напротив i+1? Чтобы "интереснее" было разбираться?

Сообщение от alexu_007

5452 2
2726 2
1363 1
1362 3
454 2

Что это за загадочные значения и где вы их взяли??? Ничего даже отдаленно похожего в массиве нет.

@woldemas · 27.06.2021, 23:00

alexu_007 вы немножко не о вывели, в каждом элементе вектора mem хранятся значения минимального количества операций, необходимых для получения числа равного индексу этого элемента. Что касается операций, можно, например, ещё один такой массив завести, в котором сохранять идентификаторы операций. Тогда можно будет проследить весь путь.

@alexu_007 · 28.06.2021, 00:26

Сообщение от TheCalligrapher

Что это за загадочные значения и где вы их взяли??? Ничего даже отдаленно похожего в массиве нет.

Я и сам вижу, что нет. Условия задачи вспомните. Мы можем либо прибавить единицу, либо умножить на два, либо на три. Таким образом, если "разматывать" цепочку от конца, т.е. от тестового значения 32718 - мы можем поделить его на 3, 2 или вычесть 1. И получить три варианта возможного продолжения вычислений. Так не всегда, ессно, а только если число делится без остатка на 3 или/и на 2 - что сужает область поиска. Вариант с -1 возможен в любом случае.

(i+1) - это порядковый номер, начиная с единицы.

Сообщение от woldemas

Что касается операций, можно, например, ещё один такой массив завести, в котором сохранять идентификаторы операций. Тогда можно будет проследить весь путь.

Массив то завести не трудно, только что за идентификаторы операций, где их взять? Насколько я понимаю, это должны быть просто цифры 1, 2 или 3?

@woldemas · 28.06.2021, 00:38

Сообщение от alexu_007

это должны быть просто цифры 1, 2 или 3?

Ну по сути да.
Можно усложнить дело, обернуть их в объекты, и добавить функционал, например, при скармливании им их индекса в массиве они возвращают индекс предыдущего объекта и т.д., но эту уж так на любителя.

@alexu_007 · 28.06.2021, 00:55

Сообщение от woldemas

Можно усложнить дело

Да не нужно усложнять, вы объясните, как их получить. Проверка то элементарная, берём единицу и последовательно выполняем арифметические действия.

Дело в том, что вы получили правильный ответ, но который хотелось бы проверить. Я пробовал решить на бумажке с калькулятором тупо в лоб: если делится на три - делил на три, если на два - на два, если не делится - вычитал единицу. У меня получилось за 18 ходов. За 17 не получилось.

@woldemas · 28.06.2021, 01:38

Сообщение от alexu_007

Дело в том, что вы получили правильный ответ, но который хотелось бы проверить.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<vector>
#include<iostream>
 
enum Op { INC = 1, X2, X3};
 
int main()
{
    int x;
    std::cin >> x;
    std::vector<int> mem(x + 1, 0);
    std::vector<Op> path(x + 1);
    for(int i = 2; i <= x; i++) {
        auto min_ops = mem[i - 1] + 1;
        Op op = INC;
        if(i % 2 == 0) {
            if(auto tmp = mem[i / 2] + 1; min_ops > tmp) {
                min_ops = tmp;
                op = X2;
            }
        }
        if(i % 3 == 0) {
            if(auto tmp = mem[i / 3] + 1; min_ops > tmp) {
                min_ops = tmp;
                op = X3;
            }
        }
        mem[i] = min_ops;
        path[i] = op;
    }
    std::cout << mem.back() << std::endl;
    for(size_t i = path.size() - 1; i > 1; ) {
        switch (path[i]) {
        case INC:
            std::cout << "INC " << --i << std::endl;
            break;
        case X2:
            std::cout << "X2 " << (i /= 2) << std::endl;
            break;
        case X3:
            std::cout << "X3 " << (i /= 3) << std::endl;
            break;
        }
    }
    return 0;
}

Вывод:

Новые блоги и статьи Все статьи Все блоги /
FPS контроллер с анимированными Y-Bot и 3D-звуком miniaudio (Box3D, Recast, BehaviorTree.CPP, ozz-animation, ImGui, OpenGL и SDL3) 8Observer8 18.10.2026 Содержание блога \| English Version Полное мультиплатформенное руководство по стартовому проекту с FPS-контроллером игрока, анимированными роботами Y-Bot с 4-слойным блендингом, 3D-физикой Box3D,. . .	Локальный http сервер Argus19 17.10.2026 Локальный http сервер На работе, на двух локальных компьютерах круглосуточно работают программы опроса приборов с записью в книги Excel,которые раз в сутки записываются на сервер компании. Т. к. . . .	Копировать Windows на новый диск на UEFI damix 17.10.2026 https:/ / uriesk. wordpress. com/ 2016/ 11/ 01/ move-window-10-to-ssd-on-a-uefi-dualboot-system-with-basic-linux-tools/ TL DR Вставляем диск, а старый подключаем через переходник, грузимся с лайва. . .	ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .
Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .

@vitek2000 3 / 3 / 0 Регистрация: 12.04.2021 Сообщений: 55

	Определить наименьшее число операций для того, чтобы используя заданные операции получить из числа 1 заданное число N 25.06.2021, 14:21. Показов 24330. Ответов 29 Метки с++ (Все метки) Задача с курсов сириуса, прошу смотреть на примеры ввода и вывода, спасибо заранее за помощьв решении задачи (никак не могу код написать) Имеется калькулятор, который выполняет три операции: прибавить к числу X единицу; умножить число X на 2; умножить число X на 3. Определите, какое наименьшее число операций необходимо для того, чтобы получить из числа 1 заданное число N. Входные данные Программа получает на вход одно число, не превосходящее 106. Выходные данные Требуется вывести одно число: наименьшее количество искомых операций. Примеры Ввод: 32718 Вывод: 17 Ввод: 1 Вывод: 0 Ввод: 5 Вывод: 3 0

@vitek2000 3 / 3 / 0 Регистрация: 12.04.2021 Сообщений: 55
	27.06.2021, 10:29 [ТС]
	alexu_007, я уже пометил ответ, мемоизация - в программировании сохранение результатов выполнения функций для предотвращения повторных вычислений. Мне не хватало времени с рекурсией, и надо было использовать это, тема цже закрыта. 0

@woldemas 677 / 479 / 216 Регистрация: 06.09.2013 Сообщений: 1,312
	27.06.2021, 23:00
	alexu_007 вы немножко не о вывели, в каждом элементе вектора mem хранятся значения минимального количества операций, необходимых для получения числа равного индексу этого элемента. Что касается операций, можно, например, ещё один такой массив завести, в котором сохранять идентификаторы операций. Тогда можно будет проследить весь путь. 0