Минимальное количество команд, чтобы из числа 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 - в сети можно свободно скачать русский перевод. Если у вас действительно есть интерес, вы рискуете стать на путь просветления по прочтении

Новые блоги и статьи Все статьи Все блоги /
Функция установки текстового статуса в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .	Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем
10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .	Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .	Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .

@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,361
	18.05.2018, 02:45
	Классика динамического программирования. Можно почитать тут https://tproger.ru/articles/dynprog-starters/. 1

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

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

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

Решение