Задание №5: Анализ алгоритмов для исполнителей
Основные типы и прототипы задания №5:
Двоичные автоматы
Троичные и n-ичные автоматы
Поиск минимального N или R
Условие задания
(Б. Михлин) Алгоритм получает на вход натуральное число N и строит по нему новое число R следующим образом:
1. Если число N четное, то оно делится на 2, иначе из него вычитается 1.
2. Если полученное на предыдущем шаге число кратно 6, то оно делится на 6, иначе из него вычитается 1.
3. Если полученное на предыдущем шаге число кратно 15, то оно делится на 15, иначе из него вычитается 1. Это число считается результатом работы алгоритма R.
Найдите минимальное число N, шестнадцатеричная запись которого содержит цифру С, а соответствующее число R равно 523.
2. Если полученное на предыдущем шаге число кратно 6, то оно делится на 6, иначе из него вычитается 1.
3. Если полученное на предыдущем шаге число кратно 15, то оно делится на 15, иначе из него вычитается 1. Это число считается результатом работы алгоритма R.
Ответ:
3145
Шаблон решения на Python
# === Задание 5: Автомат преобразования двоичных чисел ===
for n in range(1, 1000):
b = bin(n)[2:]
if b.count('1') % 2 == 0:
b = b + '0'
b = '10' + b[2:]
else:
b = b + '1'
b = '11' + b[2:]
r = int(b, 2)
if r > 40:
print(f"Ответ: N={n}, R={r}")
break