Минимальное количество команд, чтобы из числа 1 получить число N

@LegionK · Регистрация: 02.05.2017

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

Приветик. Есть вопрос по одной задаче, вот её условие :

Исполнитель «Калькулятор» имеет три команды:
Прибавить 1;
Умножить на 2;
Умножить на 3.

Определите, какое минимальное количество команд необходимо, чтобы из числа 1 получить число N.

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

Ввод содержит целое число N (1 ≤ N ≤ 106).

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

Выведите одно целое число — количество команд, выполнение которых приводит к получению числа N из числа 1.

Примеры :

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

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

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

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

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

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

И тут возникает вопрос как это можно сделать. Прошу объяснить сам алгоритм того, как можно по числу узнать сколько этих комманд нужно. Лучше всего на словах, а не на коде

вот че-то набацал, но оно просто ищет число при помощи этих команд, а не их мин. кол-во. Был вариант просто раз 30 запустить этот цикл, но по моему есть способ быстрее

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
#include <iostream>
#include <ctime>
 
using namespace std;
 
int main()
{
    srand(time(0));
    int counter(0),num(0),temp(1),random(0);
    cin >> num;
    while(temp != num){
        if(temp>num){
            temp = 1;
            counter = 0;
        }
        random = rand() % 3;
        if(random == 0)temp += 1;
        if(random == 1)temp *= 2;
        if(random == 2)temp *= 3;
 
        ++counter;
    }
    cout << counter << "\n";
 
    cout << endl;
    return 0;
}

@LegionK · 19.05.2018, 16:41 **[ТС]**

Все, можно считать тема закрыта. Спасибо _Ivana,ValeryS и Ромаха. Теперь понял, что есть и такие задачки

и нашел че изучать

@Ромаха · 19.05.2018, 20:33

Зачем понимать рекурсию?
Она прекрасна тем, что понимать ничего и не надо.
Например, задачу для решения ханойских башен я напишу за минуты три. с перерывом на покурить. А собирать ручками буду часа 2 (привет, гиперболы)

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

а вот тему "динамическое программирование" даже отдаленно понять не могу.

Динамика входит в олимпиадное. Вот и гуглите. Есть книжечки. Есть курсы на интуите. Есть разборы задач на кф. И еще тьма прочего.

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

очень

Из всей математики, что я когда-либо использовал в программировании мне понадобились знания о том, что такое логарифм и экспонента, теория чисел и определения интеграла.

Новые блоги и статьи Все статьи Все блоги /
Установка ChatGPT (Codex) на Windows без использования Microsoft Store Fabien159 28.10.2026 Здравствуйте всем читающим! Опишу процесс установки ChatGPT (Codex) на Windows, если по каким-то причинам у вас не получается устанавить его через Microsoft Store. И так: 1. Скачиваем с. . .	Программное добавление префикса в нумерацию документов Maks 27.10.2026 Реализация из решения ниже выполнена в самописной конфигурации на БСП (помощь начинающему коллеге). Задача: Программно добавить префикс в нумерацию документов. Решение: В модуле объекта. . .	После закрытия оутлука продолжает висеть процесс в диспетчере задач Maks 27.10.2026 С недавнего времени в продакшене возникла проблема: при закрытии оутлука в диспетчере задач продолжал висеть процесс outlook. exe. Проблема возникла после установки MS Office 2021 LTSC на машинах, под. . .	Baragoz - DPS/HPS бот для WoW 3.3.5a, многоязычный AmbA 26.10.2026 Хотите ещё ботов? У меня есть один! А я пока отдохну от него. https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=12062&stc=1&d=1793007952 Инструкция внутри. https:/ / youtu. be/ VpfFZSUDGnQ. . .
Особенности gif сгенерированных в Си russiannick 21.10.2026 Рассмотрим генерацию gif файлов, которые в Си имеют свои особенности. Gif представляет собой графический формат популярный в интернете. Посмотрим на палитру. Gif файл сгенерированный в си отличается. . .	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 Вставляем диск, а старый подключаем через переходник, грузимся с лайва. . .

@LegionK 393 / 263 / 193 Регистрация: 02.05.2017 Сообщений: 1,003
	19.05.2018, 16:41 [ТС]
	Все, можно считать тема закрыта. Спасибо _Ivana,ValeryS и Ромаха. Теперь понял, что есть и такие задачки и нашел че изучать 1