Задание базового уровня, проверяющее умение восстанавливать исходные данные алгоритма по его результатам. На его выполнение отводится 4 минуты.
Условие задачи
Алгоритм получает на вход натуральное число n. Алгоритм строит по нему новое число следующим образом:
- Строится двоичная запись числа n.
- Эта запись обрабатывается по следующему правилу:
- Если число n делится на 3, то к двоичной записи дописываются три последние двоичные цифры.
- Если число n на 3 не делится, то остаток от деления умножается на 3, переводится в двоичную запись и дописывается в конец числа.
Полученная запись является двоичной записью искомого числа. Необходимо указать минимальное число, больше 151, которое может быть получено с помощью описанного алгоритма.
Решение задачи на языке программирования
Решение задачи проще всего осуществить с использованием языка программирования. Будем перебирать исходные числа в цикле и применять описанный алгоритм.
def solve():
results = []
for n in range(1, 1000): # Диапазон можно изменять
s = bin(n)[2:] # Строим двоичную запись, отрезаем "0b"
if n % 3 == 0:
s += s[-3:]
else:
s += bin(n % 3 * 3)[2:]
decimal_result = int(s, 2)
if decimal_result > 151:
results.append(decimal_result)
return min(results)
print(solve())Пояснения к коду:
- Цикл for n in range(1, 1000): перебирает натуральные числа от 1 до 999. Диапазон может быть изменен, если в результате работы программы нужный результат не будет найден.
- s = bin(n)[2:] преобразует число в двоичную строку и удаляет префикс «0b».
- Условие if n % 3 == 0: проверяет делимость на 3.
- s += s[-3:] дописывает три последние цифры, если число делится на 3.
- s += bin(n % 3 * 3)[2:] дописывает двоичное представление остатка, умноженного на 3, если число не делится на 3.
- int(s, 2) преобразует двоичную строку в десятичное число.
- results.append(decimal_result) добавляет полученное число в список результатов.
- return min(results) возвращает минимальное число из списка.
Использование списка results позволяет избежать вывода всех результатов и последующего поиска минимального значения, что упрощает и ускоряет решение.
Задачу эффективно решает программа, перебирающая числа и применяющая описанный алгоритм. Использование списка для хранения результатов и последующего нахождения минимума обеспечивает быстрое и корректное получение ответа — 163. Важно учитывать, что длина дописываемой части зависит от условия; простой вывод чисел больше 151 может привести к неправильному результату.