Алгоритм получает на вход натуральное число N и строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Если сумма цифр десятичной записи заданного числа нечётна, то в конец двоичной записи
3−4. Пункт 2 повторяется для вновь полученных чисел ещё два раза.
5. Результатом работы алгоритма становится десятичная запись полученного числа R.
Пример. Дано число N = 17. Алгоритм работает следующим образом:
1. Строим двоичную запись: 1710 = 100012.
2. Сумма цифр
3. Сумма цифр
4. Сумма цифр
5. Результат работы алгоритма R = 139.
Определите количество принадлежащих отрезку [123 456 789; 1 987 654 321] чисел, которые могут получиться в результате работы этого алгоритма.
Приведём решение на языке Python.
def summ(n):
sumi = 0
while n > 0:
sumi += n % 10
n = n // 10
return sumi
o1 = 0
o2 = 0
q1 = bin(123456789)[2:]
q2 = int(q1[:len(q1)-3], 2)
for n in range(q2 - 10, q2 + 10):
s = bin(n)[2:]
for i in range(3):
if summ(int(s, 2)) % 2 == 0:
s += '0'
else:
s += '1'
r = int(s, 2)
if 123456789 <= r and r <= 1987654321:
o1 = n
break
k1 = bin(1987654321)[2:]
k2 = int(k1[:len(k1) - 3], 2)
for n in range(k2 - 10, k2 + 10):
s = bin(n)[2:]
for i in range(3):
if summ(int(s, 2)) % 2 == 0:
s += '0'
else:
s += '1'
r = int(s, 2)
if 123456789 <= r and r <= 1987654321:
o2 = n
print(o2 - o1 + 1)
Ответ: 233 024 691.
Приведём решение Дмитрия Гнутова на языке Python.
def hi(n):
t = str(n)
nechet = t.count('1') + t.count('3') + t.count('5') + t.count('7') + t.count('9')
if nechet % 2 == 1:
n = n * 2 + 1
else:
n = n * 2
return n
a = 123456789//8
for minch in range (a-1, a+2):
if hi(hi(hi(minch))) >= 123456789:
break
b = 1987654321//8
for ch in range (b -1, b + 2):
if hi(hi(hi(ch))) <= 1987654321:
maxch = ch
print(maxch, minch, maxch - minch +1)
Приведём решение Юрия Красильникова на языке Python.
def f(n):
for i in range(3):
n = 2*n + sum(map(int,str(n)))%2
return n
a,b = 123456789,1987654321
n = a // 8-5
m = b// 8-5
while f(n) < a: n += 1
while f(m) <= b: m += 1
print(m-n)