Алгоритм получает на вход натуральное число N и строит по нему новое число R следующим образом:
1. Строится двоичная запись числа N.
2. Подсчитывается количество чётных и нечётных цифр в десятичной записи заданного числа. Если в десятичной записи больше чётных цифр, то в конец двоичной записи
3−4. Пункт 2 повторяется для вновь полученных чисел ещё два раза.
5. Результатом работы алгоритма становится десятичная запись полученного числа R.
Пример. Дано число N = 14. Алгоритм работает следующим образом:
1. Строим двоичную запись: 1410 = 11102.
2. В записи числа 14 чётных и нечётных цифр поровну. Число 14 чётное, дописываем к двоичной
3. В записи числа 28 чётных цифр больше, дописываем к двоичной
4. В записи числа 57 нечётных цифр больше, дописываем к двоичной
5. Результат работы алгоритма R = 114.
Определите количество принадлежащих отрезку [123 455; 987 654 321] чисел, которые могут получиться в результате работы этого алгоритма.
Заметим, что указанный алгоритм не меняет порядок чисел. Разделив число 123455 нацело
Приведём решение на языке Python.
o1 = 0
o2 = 0
q1 = bin(123455)[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):
count1 = 0
count2 = 0
l = int(s, 2)
l1 = l
while l > 0:
if (l % 10) % 2 == 0:
count2 += 1
l //= 10
elif (l % 10) % 2 != 0:
count1 += 1
l //= 10
if count2 > count1:
s += '1'
elif count2 < count1:
s += '0'
elif count1 == count2:
if l1 % 2 == 0:
s += '0'
else:
s += '1'
r = int(s, 2)
if 123455 <= r and r <= 987654321:
o1 = n
break
k1 = bin(987654321)[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):
count1 = 0
count2 = 0
l = int(s, 2)
l1 = l
while l > 0:
if (l % 10) % 2 == 0:
count2 += 1
l //= 10
elif (l % 10) % 2 != 0:
count1 += 1
l //= 10
if count2 > count1:
s += '1'
elif count2 < count1:
s += '0'
elif count1 == count2:
if l1 % 2 == 0:
s += '0'
else:
s += '1'
r = int(s, 2)
if 123455 <= r and r <= 987654321:
o2 = n
print(o2 - o1 + 1)
Ответ: 123441358.
Приведём решение Дмитрия Гнутова на языке Python.
def novoech(pr):
for i in range (0, 3):
n = str(pr)
nechet = n.count('1') + n.count('3') + n.count('5') + n.count('7') + n.count('9')
chet = n.count('0') + n.count('2') + n.count('4') + n.count('6') + n.count('8')
if nechet > chet:
pr = pr*2
elif nechet < chet:
pr = pr*2 + 1
elif nechet ==chet:
if nechet%2 == 0:
pr = pr*2
else:
pr = pr*2 + 1
return pr
minch = 123455//8
for pr in range (minch - 1, minch + 2):
r = novoech(pr)
if r >= 123455:
minch = pr
break
maxch = 987654321//8
for pr in range (maxch - 1, maxch + 2):
r = novoech(pr)
if r <= 987654321:
maxch = pr
print ( maxch - minch + 1 )