Отправлено: 18.02.22 21:02. Заголовок: Задача 22.190

Ольга пишет:

цитата:

Никак не могу решить задание №190 из ege22(Е. Джобс) Ниже записана программа. Получив на вход число x, эта программа печатает два числа L и M. Сколько существует натуральных чисел x, при вводе которых алгоритм печатает 6 и 0? x = int(input()) L, M = 0, 0 while x > 0:   L = L + 1   if x % 16 % 2 == 0:     M = M + 1   else:     M = M - 1   x = x // 16 print(L) print(M)

Ответ: 4 915 200. 
Никак не могу решить. L=6 – количество работы цикла (сколько раз число 16 укладывается в число х +1 )
M=0 – нет чисел, которые делятся на 16 и на 2 (т.е. на 2^5).
4915200 = 2 ^16 · 3 · 5 · 5
Видимо нужно найти общее число, которое будет получаться при L=6 и отнять те, которые делятся на 16 и на 2.
Помогите, пожалуйста!

 Отправлено: 18.02.22 22:24. Заголовок: Вот переборное решен..

Вот переборное решение, отрабатывает за приемлемое время:

 count = 0 
 for xx in range(int('100000',16), int('FFFFFF',16)+1): 
   x = xx 
   L, M = 0, 0 
   while x > 0: 
     L = L + 1 
     if x % 16 % 2 == 0: 
       M = M + 1 
     else: 
       M = M - 1 
     x = x // 16 
   if L == 6 and M == 0: 
     count += 1 
 print(count)

 Отправлено: 18.02.22 22:31. Заголовок: Поляков пишет: M=0 –..

Поляков пишет:

цитата:

M=0 – нет чисел, которые делятся на 16 и на 2 (т.е. на 2^5).

Это неверно. Условие M = 0 означает, что в шестнадцатеричной записи числа равное количество чётных и нечётных цифр.

 Отправлено: 19.02.22 06:09. Заголовок: Если решать аналитич..

Если решать аналитически, то имеем следующее рассуждение.

Количество разрядов 16-го числа равно 6 (L == 6), количество четных и нечетных разрядов одинаковое (M = 0).

Рассмотрим два случая: когда старший разряд четный и когда старший разряд нечетный.

Ч*****
В этом случае нужно найти количество сочетаний из 5 по 2 для расположения четных чисел. 5!/(3!*2!) = 10
На первой (старшей) позиции может быть 7 цифр (четные кроме 0). На всех остальных - один из 8. 7*8⁵

Н*****
Рассуждение аналогичное, за тем исключением, что на первой позиции может быть 8 цифр.

Итого имеем:
7*8⁵ + 8*8⁵ = 15*8⁵ = 491520 для каждой конфигурации последовательности цифр
491520*10 = 4915200 всего комбинаций

 Отправлено: 19.02.22 07:26. Заголовок: Также 15 можно объяс..

Также 15 можно объяснить тем, что на первой позиции (в старшем разряде) не может быть 0. То есть только 15 из 16 допустимых цифр.

Дальнейшие разряды (2 четных + 3 нечетных и 2 нечетных + 3 четных) имеют симметричную схему решения.

5!/(3!*2!) - количество конфигураций,
8⁵ - количество вариантов для каждой конфигурации.

Итого сразу имеем выражение:
15*8⁵*10 = 4915200