Отправлено: 13.06.21 21:30. Заголовок: ЕГЭ 23№138

Исполнитель Нолик преобразует двоичное число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:
1. Вычесть 1
2. Обнулить
Первая команда уменьшает число на 1. Вторая команда обнуляет все ненулевые разряды, кроме старшего (например, для исходного числа 11101 результатом работы команды будет число 10000), если таких разрядов нет, то данная команда не выполняется. Сколько существует программ, которые исходное двоичное число 10001 преобразуют в двоичное число 1?
Помогите разобраться. Обнулить-останется число степень двойки. Как определить наибольшую степень двойки в числе?

 Отправлено: 13.06.21 22:35. Заголовок: Оксана2021 пишет: Ка..

Оксана2021 пишет:

цитата:

Как определить наибольшую степень двойки в числе?

Можно подбором. Можно через целую часть логарифма по основанию 2.

 Отправлено: 14.06.21 00:42. Заголовок: Вариант решения

 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]) 
  
 

 Отправлено: 16.06.21 16:26. Заголовок: Огромное спасибо!!..

Огромное спасибо!!

 Отправлено: 08.12.21 10:25. Заголовок: def f(x,y): if ..

 
 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)) 
  
 

Подскажите, пожалуйста, в чем ошибка ? Программа ничего не выдает

 Отправлено: 08.12.21 18:23. Заголовок: Оксана2021 пишет: ес..

Оксана2021 пишет:

цитата:

если таких разрядов нет, то данная команда не выполняется

У вас в программе вторая команда выполняется всегда, и получаете бесконечную рекурсию.

 Отправлено: 12.04.23 10:40. Заголовок: Решение рекурсией

AnnaPershina пишет:

цитата:

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))

Взяв за основу вашу идею, получилось вот так:

цитата:

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))