Все ссылки на статьи и ролики моего канала Old Programmer расположенные по темам тут. А здесь все мои ресурсы по рекурсивному и олимпиадному программированию
- Мои материалы по рекурсивному программированию
- Олимпиадное программирование. Список ресурсов канала Old Programmer
Еще одна задача из моего архива олимпиадного программирования. Олимпиада прошла совсем не давно и некоторые задачи, которые в ней предлагались, я опубликую.
Задача "Ассемблер"
Фабула
Вы хотели бы научиться программировать на ассемблере? У вас есть шанс. Ассемблер не похож на обычные языки программирования. Он оперирует не переменными, а ячейками памяти и регистрами. Регистры, это тоже ячейки памяти, но эта память находится в самом процессоре. Она не большая, но очень быстрая. Конечно в одной задаче мы не сможем изучить весь ассемблер, но с двумя командами я вас познакомлю.
И так есть два регистра RAX и RBX. И есть две команды MOV и ADD. Первая команда копирует число из одного регистра в другой: MOV RBX, RAX (из RAX в RBX), вторая осуществляет операцию сложения: ADD RAX, RBX - складываются два числа, а результат помещается в RAX.
Задание
И так у вас есть две команды MOV RBX, RAX и ADD RAX, RBX. Команды MOV RAX, RBX и ADD RBX, RAX использовать нельзя. Пусть в регистре RAX лежит число N, в регистре RBX лежит ноль. Необходимо с помощью только указанных команд получить в RAX число M. Ваша задача найти минимальное количество таких команд.
Входные данные
На входе даны два числа N и M. (N>=0, N<=10^9; M>=0, M<=10^9).
Выходные данные
Одно число — минимальное количество указанных операций, которые нужно произвести, чтобы получить в RAX нужное число. Если это не возможно, то выводится -1.
Примеры
Решение
Может показаться что возможно рекурсивное решение. Т.е. на самом деле рекурсивное решение, конечно, возможно, но время выполнения резко возрастает с увеличением разницы между числами.
Решение задачи основывается на двух положениях, которые легко просматриваются при рассмотрении простых примеров:
- Второе число должно делится на первое
- Минимальное количество команд равно сумме простых множителей частного от деления второго числа на первое. В случае пары 1 8, 8 = 2 * 2 * 2. Сумма двоек и дает 6. Для пары 2 18 имеем, 18/2 = 9, 9 = 3 * 3, количество команд равно 3 + 3 = 6.
Результат решения представлен в olmp4000.c.
До следующих встреч. Подписываемся на мой канал Old Programmer, здесь много материалов по разным вопросам программирования.
