Минимальное количество команд, чтобы из числа 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;
}

@Bring · 16.05.2018, 19:50

Насколько я знаю, такие задачи рекурсией решают. Хотел бы я шарить в ней...

ValeryS · 16.05.2018, 20:02

1 берем число
2 если равно 1 выходим
3 если делится на 3 то делим на 3 идем к пункту 1
4 если делится на два то делим на 2, идем к пункту 1
5 вычитаем 1 идем к пункту 1
по моему так

например так

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int count=0;
while(N!=1 && N>0)
{
 count++;
 if(N%3==0)
   {
    N/=3;
    continue;
   }
 if(N%2==0)
   {
    N/=2;
    continue;
   }
 N--;
 
}

@LegionK · 17.05.2018, 04:57 **[ТС]**

ValeryS,

, я бы и не догадался,спасибо

@Ромаха · 17.05.2018, 12:23

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

например так

Вроде не.
28.
1 = (28/2/2 - 1)/3/2
Итого 5
1 = (28-1)/3/3/3
Итого 4

@LegionK · 17.05.2018, 12:36 **[ТС]**

Ромаха, там и 10 выдает 4, а можно в 3,но и так нормально)

ValeryS · 17.05.2018, 13:27

Сообщение от Ромаха

Вроде не.

я же сказал

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

например

это самый простейший алгоритм, который мне пришел в голову
другой без использования деревьев придумать не могу -)

Добавлено через 5 минут
здесь нужно смотреть в сторону "жадного алгоритма" но мне лень -)

@Ромаха · 17.05.2018, 14:11

Жадинко? Не верю чет

Тут ж обычная динамика. А т.к. ее писать лень, то ленивая через рекурсию. O(n) красота

Новичок · 18.05.2018, 02:45

Классика динамического программирования.
Можно почитать тут https://tproger.ru/articles/dynprog-starters/.

@_Ivana · 18.05.2018, 15:15

Как Ромаха завещал -

C++
1
2
3
4
5
6
7
8
const int N = 1000000;
int a[N];
 
int f(int n) {
    if (n<=1) return 0;
    if (!a[n]) a[n] = 1 + std::min(f(n-1), std::min(n%3 ? N : f(n/3), n%2 ? N : f(n/2)));
    return a[n];        
}

@LegionK · 19.05.2018, 10:03 **[ТС]**

_Ivana, извините, не могли бы вы немного пояснить : до какого момента будет вызываться

C++
1
f(n-1)

?
До того как в 5 строчке не вернет 0? Но в чем тогда смысл? С делением тот же самый момент не понятен. Объясните, пожалуйста, если не трудно. И ещё вопрос по тернарному оператору - если, у нас, например, число 5 -

C++
1
std::min(n%3 ? N : f(n/3), n%2 ? N : f(n/2)))

здесь они оба дадут число N. Но что тогда вернет min?

@_Ivana · 19.05.2018, 13:21

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

До того как в 5 строчке не вернет 0?

Очевидно, да.

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

Но в чем тогда смысл?

Дойти до финала по ветке исключительно декремента.

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

здесь они оба дадут число N. Но что тогда вернет min?

Здесь надо понимать, что исходное число у нас сверху ограничено значением N, значит при наличии декремента мы можем получить желаемый результат не более чем за N-1 команд (все декременты), при добавлении команд деления на 2 и на 3 число команд для достижения результата у нас не увеличивается (потому что промежуточный результат преобразований всегда уменьшается на каждом шаге), а значит таким нехитрым образом мы доказали, что минимальное число шагов у нас ограничено сверху значением N-1, соответственно мы можем брать N в качестве того аргумента минимума, который никогда не вернется. Но с тем же успехом мы могли брать std::MaxInt или как оно в плюсах вызывается - мне лень было искать, а N у нас уже есть готовое

@LegionK · 19.05.2018, 14:53 **[ТС]**

_Ivana,

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

Дойти до финала по ветке исключительно декремента.

Тогда можно считать, что в конце концов, когда мы навычитаем до того, момента, когда n равен 1 - функция начнет возвращать нам нули(5 строка начнет работать)? И вот этот вызов

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

f(n-1)

в конце всех рекурсий тоже вернет 0? Извините, что туплю, просто хочу разобраться в алгоритме решения таких задач

@_Ivana · 19.05.2018, 15:02

Вы зачем-то беретесь за такие задачи, когда (судя по вашим постам в этой теме) у вас даже с более простыми проблемы, не говоря уже про жадные алгоритмы или мемоизацию. Это так же безрезультатно, как учиться играть в футболе не умея ходить. Начните с чего-нибудь попроще, например факториала, разберитесь как он работает. Что толку в объяснениях, которые дают лишь иллюзию понимания, а в следующий раз вы опять окажетесь бессильны.

@LegionK · 19.05.2018, 15:33 **[ТС]**

Не по теме:

_Ivana,

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

например факториала

А в решении таких задач так сильно нужна математика? Если да - что посоветуете почитать,чтобы быстрее втянутся (~3 месяца - полгода)? И как вообще называется раздел математики, нужный для динамического программирования? Уровень знаний - 8 классов. Можно даже посложнее, ибо раз в неделю у учителя можно спросить

@_Ivana · 19.05.2018, 15:42

Я посоветую не пытаться брать наскоком сразу сложные вам задачи, а методично и много решать более простых, постепенно усложняя их уровень. Если какая-то задача вызывает трудности - оставьте ее, но обязательно пробуйте вернуться потом - если вы будете заниматься, то рано или поздно вы ее решите. Это как в качалке - найдите свой вес. А задачек дофига и больше в инете, на любой уровень, даже с возможностью проверки решения.

ValeryS · 19.05.2018, 15:59

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

А в решении таких задач так сильно нужна математика?

очень

например тот же факториал
одно из определение
Факториал N это произведение чисел от 1 до N
решается циклом

C++
1
2
3
int fact=1;
for(int i=1;i<=N;i++)
  fact*=i;

другое определение
Факториал N это произведение N на факториал (N-1), факториал 0 равен 1
решается рекурсией

C++
1
2
3
4
5
int fact(N)
{
 if(N==0) return 1;
 return N*fact(N-1);
}

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

_Ivana, а скажите примерный порядок тем, которые надо читать,пожалуйста, или курс какой-нибудь посоветуете? Типа школьную математику я нашел книжек. Прочитаю. А дальше в какую сторону смотреть? Или вы о программировании? Если так - я как раз в предложенном порядке смотрел задачи на одном сайте.На массивы, матрицы, функции,строки, сортировки и т.д я решаю и пара мини-проектов есть на Qt, а вот тему "динамическое программирование" даже отдаленно понять не могу.

Добавлено через 5 минут
ValeryS, да уж, эта рекурсия, интуитивно, что ли понятна(ибо условие прочитал,наверное

),но сразу запутываюсь когда представляю как оно там работает на каждой итерации. Подкиньте тоже, пожалуйста, книг по этой теме и темам "ниже,которые нужны чтобы понять эту". Разобраться оч. хочу, времени море, так что можно побольше)

ValeryS · 19.05.2018, 16:32

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

Подкиньте тоже, пожалуйста, книг по этой теме

лучше всяких книг, по моему мнению, "опыт-сын ошибок трудных"(с)
запускай прогу в отладчике и по шагам смотри что где происходит
посмотри как_Ivana, насобачился в рекурсиях, я иногда даже его не понимаю

правда рекурсии он не С++ изучал

@_Ivana · 19.05.2018, 16:34

Рекомендую изучить на базовом уровне какой-нибудь бескомпромиссный функциональный язык программирования, в котором вообще нет мутабельности и циклов. Например, неземной и волшебный Haskell. У вас просто не будет другой возможности что-либо сделать, кроме как использовать рекурсию

И порешать задачки на нем. Если освоите, то потом с рекурсией будете на ты.

ЗЫ а почитать - весьма настоятельно рекомендую SICP - в сети можно свободно скачать русский перевод. Если у вас действительно есть интерес, вы рискуете стать на путь просветления по прочтении

Новые блоги и статьи Все статьи Все блоги /
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Ниже машинный перевод статьи The Thinkpad X220 Tablet is the best budget school laptop period . Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы,. . .	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 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .

@Bring 133 / 53 / 43 Регистрация: 09.05.2015 Сообщений: 565
	16.05.2018, 19:50
	Насколько я знаю, такие задачи рекурсией решают. Хотел бы я шарить в ней... 0

@LegionK 393 / 263 / 193 Регистрация: 02.05.2017 Сообщений: 1,003
	17.05.2018, 04:57 [ТС]
	ValeryS, , я бы и не догадался,спасибо 0

@LegionK 393 / 263 / 193 Регистрация: 02.05.2017 Сообщений: 1,003
	17.05.2018, 12:36 [ТС]
	Ромаха, там и 10 выдает 4, а можно в 3,но и так нормально) 0

@Ромаха 354 / 135 / 28 Регистрация: 16.12.2012 Сообщений: 607 Записей в блоге: 1
	17.05.2018, 14:11
	Жадинко? Не верю чет Тут ж обычная динамика. А т.к. ее писать лень, то ленивая через рекурсию. O(n) красота 1

Новичок 1682 / 1098 / 489 Регистрация: 17.07.2012 Сообщений: 5,360
	18.05.2018, 02:45
	Классика динамического программирования. Можно почитать тут https://tproger.ru/articles/dynprog-starters/. 1

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,984 Записей в блоге: 32
	19.05.2018, 15:02
	Вы зачем-то беретесь за такие задачи, когда (судя по вашим постам в этой теме) у вас даже с более простыми проблемы, не говоря уже про жадные алгоритмы или мемоизацию. Это так же безрезультатно, как учиться играть в футболе не умея ходить. Начните с чего-нибудь попроще, например факториала, разберитесь как он работает. Что толку в объяснениях, которые дают лишь иллюзию понимания, а в следующий раз вы опять окажетесь бессильны. 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,984 Записей в блоге: 32
	19.05.2018, 15:42
	Я посоветую не пытаться брать наскоком сразу сложные вам задачи, а методично и много решать более простых, постепенно усложняя их уровень. Если какая-то задача вызывает трудности - оставьте ее, но обязательно пробуйте вернуться потом - если вы будете заниматься, то рано или поздно вы ее решите. Это как в качалке - найдите свой вес. А задачек дофига и больше в инете, на любой уровень, даже с возможностью проверки решения. 1

@LegionK 393 / 263 / 193 Регистрация: 02.05.2017 Сообщений: 1,003
	19.05.2018, 16:23 [ТС]
	_Ivana, а скажите примерный порядок тем, которые надо читать,пожалуйста, или курс какой-нибудь посоветуете? Типа школьную математику я нашел книжек. Прочитаю. А дальше в какую сторону смотреть? Или вы о программировании? Если так - я как раз в предложенном порядке смотрел задачи на одном сайте.На массивы, матрицы, функции,строки, сортировки и т.д я решаю и пара мини-проектов есть на Qt, а вот тему "динамическое программирование" даже отдаленно понять не могу. Добавлено через 5 минут ValeryS, да уж, эта рекурсия, интуитивно, что ли понятна(ибо условие прочитал,наверное ),но сразу запутываюсь когда представляю как оно там работает на каждой итерации. Подкиньте тоже, пожалуйста, книг по этой теме и темам "ниже,которые нужны чтобы понять эту". Разобраться оч. хочу, времени море, так что можно побольше) 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,984 Записей в блоге: 32
	19.05.2018, 16:34
	Рекомендую изучить на базовом уровне какой-нибудь бескомпромиссный функциональный язык программирования, в котором вообще нет мутабельности и циклов. Например, неземной и волшебный Haskell. У вас просто не будет другой возможности что-либо сделать, кроме как использовать рекурсию И порешать задачки на нем. Если освоите, то потом с рекурсией будете на ты. ЗЫ а почитать - весьма настоятельно рекомендую SICP - в сети можно свободно скачать русский перевод. Если у вас действительно есть интерес, вы рискуете стать на путь просветления по прочтении 1

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

Решение