Задание №5: Анализ алгоритмов для исполнителей
Основные типы и прототипы задания №5:
Двоичные автоматы
Троичные и n-ичные автоматы
Поиск минимального N или R
Условие задания
(В. Шубинкин) Автомат производит первичную проверку правильности номера банковской карты. Он получает на вход число N из 16 цифр и обрабатывает его по следующему правилу (вариант алгоритма Лу́на):
Определите наименьшее число N, большее 1234 5678 9101 1121, которое может быть корректным номером согласно указанному алгоритму. Укажите в ответе последние 8 цифр числа.
1) Цифры числа нумеруются справа налево, начиная с нуля.
2) Цифры, стоящие на нечётных позициях, увеличиваются в два раза. Если при этом получается двузначное число, его цифры складываются.
3) Складываются все цифры на чётных позициях и преобразованные цифры на нечётных позициях.
4) Если полученная сумма кратна 10, считается, что номер корректный.
Например, для числа 4096 8308 0309 8323 сумма цифр на чётных позициях (с конца) 3+3+9+3+8+3+6+0=35, сумма преобразованных цифр на нечётных позициях 4+7+0+0+0+7+9+8=35. Общая сумма 70 кратна 10, значит номер корректен.2) Цифры, стоящие на нечётных позициях, увеличиваются в два раза. Если при этом получается двузначное число, его цифры складываются.
3) Складываются все цифры на чётных позициях и преобразованные цифры на нечётных позициях.
4) Если полученная сумма кратна 10, считается, что номер корректный.
Определите наименьшее число N, большее 1234 5678 9101 1121, которое может быть корректным номером согласно указанному алгоритму. Укажите в ответе последние 8 цифр числа.
Ответ:
91011128
Шаблон решения на 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