Задание №5: Анализ алгоритмов для исполнителей
Основные типы и прототипы задания №5:
Двоичные автоматы
Троичные и n-ичные автоматы
Поиск минимального N или R
Условие задания
Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом:
1) Если исходное число кратно 2, оно делится на 2, иначе из него вычитается 1.
2) Если полученное на предыдущем шаге число кратно 3, оно делится на 3, иначе из него вычитается 1.
3) Если полученное на предыдущем шаге число кратно 7, оно делится на 7, иначе из него вычитается 1.
4) Число, полученное на шаге 3, считается результатом работы алгоритма.
Сколько существует различных натуральных чисел N, при обработке которых получится R = 2?
2) Если полученное на предыдущем шаге число кратно 3, оно делится на 3, иначе из него вычитается 1.
3) Если полученное на предыдущем шаге число кратно 7, оно делится на 7, иначе из него вычитается 1.
4) Число, полученное на шаге 3, считается результатом работы алгоритма.
Ответ:
5
Шаблон решения на 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