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

Новые блоги и статьи Все статьи Все блоги /
http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит переходные токи и напряжения на элементах схемы. . . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .

@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,989 Записей в блоге: 32
	19.05.2018, 15:02
	Вы зачем-то беретесь за такие задачи, когда (судя по вашим постам в этой теме) у вас даже с более простыми проблемы, не говоря уже про жадные алгоритмы или мемоизацию. Это так же безрезультатно, как учиться играть в футболе не умея ходить. Начните с чего-нибудь попроще, например факториала, разберитесь как он работает. Что толку в объяснениях, которые дают лишь иллюзию понимания, а в следующий раз вы опять окажетесь бессильны. 0

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

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

Решение