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