Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.55/29: Рейтинг темы: голосов - 29, средняя оценка - 4.55
343 / 228 / 177
Регистрация: 02.05.2017
Сообщений: 886
1

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

16.05.2018, 17:07. Просмотров 5980. Ответов 21


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

Исполнитель «Калькулятор» имеет три команды:
Прибавить 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;
}
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
16.05.2018, 17:07
Ответы с готовыми решениями:

Найти количество различных чисел, которые можно получить из числа ровно за C команд
#include &lt;iostream&gt; using namespace std; int c(int x, int y) { if (x == y || y == 0) return 1;...

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

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

Переставить цифры числа так, чтобы получилось минимальное возможное число
Дано натуральное число n. Необходимо переставить его цифры таким образом, чтобы получилось...

21
132 / 52 / 43
Регистрация: 09.05.2015
Сообщений: 562
16.05.2018, 19:50 2
Насколько я знаю, такие задачи рекурсией решают. Хотел бы я шарить в ней...
0
Модератор
Эксперт по электронике
8360 / 6206 / 834
Регистрация: 14.02.2011
Сообщений: 21,569
16.05.2018, 20:02 3
Лучший ответ Сообщение было отмечено LegionK как решение

Решение

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--;
 
}
2
343 / 228 / 177
Регистрация: 02.05.2017
Сообщений: 886
17.05.2018, 04:57  [ТС] 4
ValeryS, , я бы и не догадался,спасибо
0
353 / 134 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
17.05.2018, 12:23 5
Цитата Сообщение от ValeryS Посмотреть сообщение
например так
Вроде не.
28.
1 = (28/2/2 - 1)/3/2
Итого 5
1 = (28-1)/3/3/3
Итого 4
0
343 / 228 / 177
Регистрация: 02.05.2017
Сообщений: 886
17.05.2018, 12:36  [ТС] 6
Ромаха, там и 10 выдает 4, а можно в 3,но и так нормально)
0
Модератор
Эксперт по электронике
8360 / 6206 / 834
Регистрация: 14.02.2011
Сообщений: 21,569
17.05.2018, 13:27 7
Цитата Сообщение от Ромаха Посмотреть сообщение
Вроде не.
я же сказал
Цитата Сообщение от ValeryS Посмотреть сообщение
например
это самый простейший алгоритм, который мне пришел в голову
другой без использования деревьев придумать не могу -)

Добавлено через 5 минут
здесь нужно смотреть в сторону "жадного алгоритма" но мне лень -)
0
353 / 134 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
17.05.2018, 14:11 8
Жадинко? Не верю чет

Тут ж обычная динамика. А т.к. ее писать лень, то ленивая через рекурсию. O(n) красота
1
Модератор
1618 / 1075 / 483
Регистрация: 17.07.2012
Сообщений: 5,303
18.05.2018, 02:45 9
Классика динамического программирования.
Можно почитать тут https://tproger.ru/articles/dynprog-starters/.
1
4455 / 2074 / 263
Регистрация: 01.03.2013
Сообщений: 5,511
Записей в блоге: 22
18.05.2018, 15:15 10
Как Ромаха завещал -
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];        
}
1
343 / 228 / 177
Регистрация: 02.05.2017
Сообщений: 886
19.05.2018, 10:03  [ТС] 11
_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?
0
4455 / 2074 / 263
Регистрация: 01.03.2013
Сообщений: 5,511
Записей в блоге: 22
19.05.2018, 13:21 12
Цитата Сообщение от LegionK Посмотреть сообщение
До того как в 5 строчке не вернет 0?
Очевидно, да.
Цитата Сообщение от LegionK Посмотреть сообщение
Но в чем тогда смысл?
Дойти до финала по ветке исключительно декремента.
Цитата Сообщение от LegionK Посмотреть сообщение
здесь они оба дадут число N. Но что тогда вернет min?
Здесь надо понимать, что исходное число у нас сверху ограничено значением N, значит при наличии декремента мы можем получить желаемый результат не более чем за N-1 команд (все декременты), при добавлении команд деления на 2 и на 3 число команд для достижения результата у нас не увеличивается (потому что промежуточный результат преобразований всегда уменьшается на каждом шаге), а значит таким нехитрым образом мы доказали, что минимальное число шагов у нас ограничено сверху значением N-1, соответственно мы можем брать N в качестве того аргумента минимума, который никогда не вернется. Но с тем же успехом мы могли брать std::MaxInt или как оно в плюсах вызывается - мне лень было искать, а N у нас уже есть готовое
1
343 / 228 / 177
Регистрация: 02.05.2017
Сообщений: 886
19.05.2018, 14:53  [ТС] 13
_Ivana,
Цитата Сообщение от _Ivana Посмотреть сообщение
Дойти до финала по ветке исключительно декремента.
Тогда можно считать, что в конце концов, когда мы навычитаем до того, момента, когда n равен 1 - функция начнет возвращать нам нули(5 строка начнет работать)? И вот этот вызов
Цитата Сообщение от _Ivana Посмотреть сообщение
f(n-1)
в конце всех рекурсий тоже вернет 0? Извините, что туплю, просто хочу разобраться в алгоритме решения таких задач
0
4455 / 2074 / 263
Регистрация: 01.03.2013
Сообщений: 5,511
Записей в блоге: 22
19.05.2018, 15:02 14
Вы зачем-то беретесь за такие задачи, когда (судя по вашим постам в этой теме) у вас даже с более простыми проблемы, не говоря уже про жадные алгоритмы или мемоизацию. Это так же безрезультатно, как учиться играть в футболе не умея ходить. Начните с чего-нибудь попроще, например факториала, разберитесь как он работает. Что толку в объяснениях, которые дают лишь иллюзию понимания, а в следующий раз вы опять окажетесь бессильны.
0
LegionK
19.05.2018, 15:33  [ТС]
  #15

Не по теме:

_Ivana,

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

0
4455 / 2074 / 263
Регистрация: 01.03.2013
Сообщений: 5,511
Записей в блоге: 22
19.05.2018, 15:42 16
Я посоветую не пытаться брать наскоком сразу сложные вам задачи, а методично и много решать более простых, постепенно усложняя их уровень. Если какая-то задача вызывает трудности - оставьте ее, но обязательно пробуйте вернуться потом - если вы будете заниматься, то рано или поздно вы ее решите. Это как в качалке - найдите свой вес. А задачек дофига и больше в инете, на любой уровень, даже с возможностью проверки решения.
1
Модератор
Эксперт по электронике
8360 / 6206 / 834
Регистрация: 14.02.2011
Сообщений: 21,569
19.05.2018, 15:59 17
Цитата Сообщение от 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);
}
0
343 / 228 / 177
Регистрация: 02.05.2017
Сообщений: 886
19.05.2018, 16:23  [ТС] 18
_Ivana, а скажите примерный порядок тем, которые надо читать,пожалуйста, или курс какой-нибудь посоветуете? Типа школьную математику я нашел книжек. Прочитаю. А дальше в какую сторону смотреть? Или вы о программировании? Если так - я как раз в предложенном порядке смотрел задачи на одном сайте.На массивы, матрицы, функции,строки, сортировки и т.д я решаю и пара мини-проектов есть на Qt, а вот тему "динамическое программирование" даже отдаленно понять не могу.

Добавлено через 5 минут
ValeryS, да уж, эта рекурсия, интуитивно, что ли понятна(ибо условие прочитал,наверное ),но сразу запутываюсь когда представляю как оно там работает на каждой итерации. Подкиньте тоже, пожалуйста, книг по этой теме и темам "ниже,которые нужны чтобы понять эту". Разобраться оч. хочу, времени море, так что можно побольше)
0
Модератор
Эксперт по электронике
8360 / 6206 / 834
Регистрация: 14.02.2011
Сообщений: 21,569
19.05.2018, 16:32 19
Цитата Сообщение от LegionK Посмотреть сообщение
Подкиньте тоже, пожалуйста, книг по этой теме
лучше всяких книг, по моему мнению, "опыт-сын ошибок трудных"(с)
запускай прогу в отладчике и по шагам смотри что где происходит
посмотри как_Ivana, насобачился в рекурсиях, я иногда даже его не понимаю
правда рекурсии он не С++ изучал
1
4455 / 2074 / 263
Регистрация: 01.03.2013
Сообщений: 5,511
Записей в блоге: 22
19.05.2018, 16:34 20
Рекомендую изучить на базовом уровне какой-нибудь бескомпромиссный функциональный язык программирования, в котором вообще нет мутабельности и циклов. Например, неземной и волшебный Haskell. У вас просто не будет другой возможности что-либо сделать, кроме как использовать рекурсию И порешать задачки на нем. Если освоите, то потом с рекурсией будете на ты.

ЗЫ а почитать - весьма настоятельно рекомендую SICP - в сети можно свободно скачать русский перевод. Если у вас действительно есть интерес, вы рискуете стать на путь просветления по прочтении
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.05.2018, 16:34

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь или здесь.

Расставить знаки арифметических операций между цифрами числа A, чтобы получить число B
Заданы два целых положительных числа A и B. Расставьте знаки арифметических операций (+, -, *, /)...

Какое минимальное количество цифр числа надо исправить, чтобы исправленное число совпадало с обращенным?
1.Составьте программу определяющую какое минимальное количество цифр числа H надо исправить,чтобы...

Количество построений команд, который позволяют получить из A число B
У некоторого исполнителя есть две команды: первая увеличивает число на 2, вторая увеличивает число...

Какое минимальное количество итераций понадобится чтобы определить случайное число от 0 - до 256?
задание такое: какое минимальное количество итераций понадобится чтобы определить случайное...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.