Форум » Циклы и ветвления » Задача 22.190 » Ответить
Задача 22.190
Поляков: Ольга пишет: [quote]Никак не могу решить задание №190 из ege22(Е. Джобс) Ниже записана программа. Получив на вход число x, эта программа печатает два числа L и M. Сколько существует натуральных чисел x, при вводе которых алгоритм печатает 6 и 0?[pre2] 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)[/pre2] Ответ: 4 915 200. Никак не могу решить. L=6 – количество работы цикла (сколько раз число 16 укладывается в число х +1 ) M=0 – нет чисел, которые делятся на 16 и на 2 (т.е. на 2^5). 4915200 = 2 ^16 · 3 · 5 · 5 Видимо нужно найти общее число, которое будет получаться при L=6 и отнять те, которые делятся на 16 и на 2. Помогите, пожалуйста![/quote]
Ответов - 4
Поляков: Вот переборное решение, отрабатывает за приемлемое время: [pre2] 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)[/pre2]
Поляков: Поляков пишет: M=0 – нет чисел, которые делятся на 16 и на 2 (т.е. на 2^5). Это неверно. Условие M = 0 означает, что в шестнадцатеричной записи числа равное количество чётных и нечётных цифр.
EugeneJobs: Если решать аналитически, то имеем следующее рассуждение. Количество разрядов 16-го числа равно 6 (L == 6), количество четных и нечетных разрядов одинаковое (M = 0). Рассмотрим два случая: когда старший разряд четный и когда старший разряд нечетный. Ч***** В этом случае нужно найти количество сочетаний из 5 по 2 для расположения четных чисел. 5!/(3!*2!) = 10 На первой (старшей) позиции может быть 7 цифр (четные кроме 0). На всех остальных - один из 8. 7*85 Н***** Рассуждение аналогичное, за тем исключением, что на первой позиции может быть 8 цифр. Итого имеем: 7*85 + 8*85 = 15*85 = 491520 для каждой конфигурации последовательности цифр 491520*10 = 4915200 всего комбинаций
EugeneJobs: Также 15 можно объяснить тем, что на первой позиции (в старшем разряде) не может быть 0. То есть только 15 из 16 допустимых цифр. Дальнейшие разряды (2 четных + 3 нечетных и 2 нечетных + 3 четных) имеют симметричную схему решения. 5!/(3!*2!) - количество конфигураций, 85 - количество вариантов для каждой конфигурации. Итого сразу имеем выражение: 15*85*10 = 4915200
полная версия страницы