Форум » Динамическое программирование » ЕГЭ 23№138 » Ответить
ЕГЭ 23№138
Оксана2021: Исполнитель Нолик преобразует двоичное число, записанное на экране. У исполнителя есть две команды, которым присвоены номера: 1. Вычесть 1 2. Обнулить Первая команда уменьшает число на 1. Вторая команда обнуляет все ненулевые разряды, кроме старшего (например, для исходного числа 11101 результатом работы команды будет число 10000), если таких разрядов нет, то данная команда не выполняется. Сколько существует программ, которые исходное двоичное число 10001 преобразуют в двоичное число 1? Помогите разобраться. Обнулить-останется число степень двойки. Как определить наибольшую степень двойки в числе?
Ответов - 6
Поляков: Оксана2021 пишет: Как определить наибольшую степень двойки в числе? Можно подбором. Можно через целую часть логарифма по основанию 2.
polyakovss: [pre2] a=[0]*20 a[17]=1 for x in range(17,0,-1): a[x-1] += a[x] x1 = 2**(len(f'{x:b}')-1) if x != x1: a[x1] += a[x] print(a[1]) [/pre2]
Оксана2021: Огромное спасибо!!
AnnaPershina: [pre2] def f(x,y): if x==y: return 1 if x>y: return f(x-1,y)+f(2**(len(bin(x)[2:])-1),y) if x<y: return 0 print(f(17,1)) [/pre2] Подскажите, пожалуйста, в чем ошибка ? Программа ничего не выдает
Поляков: Оксана2021 пишет: если таких разрядов нет, то данная команда не выполняется У вас в программе вторая команда выполняется всегда, и получаете бесконечную рекурсию.
nikitadvu: AnnaPershina пишет: [pre2] def f(x,y): if x==y: return 1 if x>y: return f(x-1,y)+f(2**(len(bin(x)[2:])-1),y) if x<y: return 0 print(f(17,1)) [/pre2] Взяв за основу вашу идею, получилось вот так: [pre2] def f(s,fin): if s==fin: return 1 if s<fin: return 0 if s == (2**(len(bin(s)[2:])-1)): return f(s-1,fin) else: return f(s-1,fin)+ f(2**(len(bin(s)[2:])-1),fin) print(f(17,1)) [/pre2]
полная версия страницы