[White Mike]

Скажите, позж, как написать прогу, которая выведет наименьшее число команд, которые нужны для получения из числа a число b. например из числа 3 число 57 причем команды только две: +3 и /4

@темы: Точка зрения, Программрование

Comments

[Kotyarka]

"как написать прогу?"

читаете книгу, включаете комп, и все это желательно до того как началась сессия :-)

[White Mike]

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

[hauff]

White Mike, вы хоть условия задачи расскажите, что делать в случае если такое число получить нельзя? или такого быть не может?

[White Mike]

оу, ссори, забыл. Вот условие:
Вася, решая задачи демо-версии ЕГЭ, дошел до задачи B5, которая звучит так. "У исполнителя Калькулятор две команды:
1) прибавь 3
2) умножь на 4
Выполняя первую из них, Калькулятор прибавляет к числу на экране 3, а выполняя вторую, умножает его на 4."
Далее в задаче требовалось получить из числа 3 число 57 не более, чем за 6 команд. Однако Вася заинтересовался, как можно для произвольных чисел a и b построить программу наименьшей длины получения числа b из числа a.
Напишите программу, которая по заданным числам a и b вычислит наименьшее количество команд Калькулятора, которое нужно, чтобы получить из a число b.

Формат входных данных

Вводятся два натуральных числа, не превышающих 1000 - a и b.

Формат выходных данных

Выведите наименьшее число команд, которое нужно, чтобы получить из a число b. Если число b получить нельзя, выведите -1 (минус 1).

[hauff]

White Mike, тут всё попроще, умножить на 4 это всегда больше чем прибавить 3. Т.е. скорее всего действуем рекурсивно, умножаем на 4, смотрим перепрыгнули ли мы нужное число, если нет, то снова на 4, если да, то делаем откат назад и прибавляем тройку.

[hauff]

White Mike, не совсем так, конечно )) если перепрыгнули, то уже можно только троек наприбавлять попробовать, и если не получилось, то откатиться назад, прибавить 3 и снова попробовать помножить на 4

[[revolver]]

hauff, совершенно неправильно. Переборный алгоритм конечно найдёт ответ, но через сколько операций? Т.к. оба числа находятнся в диапазоне от 0 до 1000, нужно воспользоваться алгоритмом BFS - поиска в ширину (волновой). Числа от 0 до 1000 -- это вершины графа, операции +3 и *4 -- ориентированные рёбра на наших вершинах. Очевидно, что граф невзвешанный (т.к. про вес каждой операции ничего не сказано), а значит нам как раз подходит алгоритм BFS (который и ищет минимальный путь между двумя заданными вершинами в невзвешанном графе).

[White Mike]

окей. спасибо)

[hauff]

[revolver], в каком смысле неправильный, я по сути это и имел виду

[[revolver]]

hauff, нууууу описан то полный перебор с возвратом, работающий за время 2^количество_чисел. Ну отсечения есть, где то 2^(количество_чисел/2). А bfs за линейное время работает)

[hauff]

[revolver], хорошо, хорошо

[[revolver]]

hauff, да всё ок) просто это первый нормальный вопрос в этом сообществе за длииительное время) Вот я и оторвался) Извиняюсь....

[White Mike]

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

[[revolver]]

White Mike, после какого такого всероса?

[White Mike]

После IX Всероссийской командной олимпиады по программированию среди школьников