Определить наименьшее число операций для того, чтобы используя заданные операции получить из числа 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;
}

Вывод:

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

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

	Определить наименьшее число операций для того, чтобы используя заданные операции получить из числа 1 заданное число N 25.06.2021, 14:21. Показов 23674. Ответов 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