Отправлено: 06.03.22 04:20. Заголовок: ege23 №151

Всех с наступающим праздником весны!

Вот задачка, на первый взгляд простая, а ответ не сходится:

ege 23 № 151 (Е. Джобс) Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавь 1
2. Умножь на 2
3. Сделай нечётное
Первая команда увеличивает число на 1, вторая – вдвое, третья прибавляет к четному числу 1, к нечетному – 2. Сколько существует таких программ, которые исходное число 3 преобразуют в число 25 и при этом траектория вычислений программы содержит число 9 и число 17?

Подскажите, пожалуйста, чего я теряю в своих умозаключениях пытаясь написать рекуррентную функцию:

если n/2 => f(n) = f(n-1)+f(n-1)+f(n/2)
иначе => f(n) = f(n-1)+f(n-2)

Спасибо!

 Отправлено: 06.03.22 12:58. Заголовок: В формуле для четног..

В формуле для четного у вас ошибка. В четное нельзя прийти третьей командой

 Отправлено: 07.03.22 02:07. Заголовок: EugeneJobs пишет: В..

EugeneJobs пишет:

цитата:

В формуле для четного у вас ошибка. В четное нельзя прийти третьей командой

В таком случае и в формуле для нечетных тоже есть ошибка, поскольку нечетное можно получить 3-мя командами, стало быть правильной будет такая функция:
если n/2 => f(n) = f(n-1)+f(n/2)
иначе => f(n) = f(n-1)+f(n-2)+f(n-1)
возможно, что и так тоже будет правильно:
если n/2 => f(n) = f(n-1)+f(n/2)
иначе => f(n) = 2*f(n-1)+f(n-2)

Спасибо

 Отправлено: 07.03.22 11:25. Заголовок: T = *(25+1) T = 1 f..

 T = [0]*(25+1) 
 T[3] = 1 
 for i in range(4,25+1): 
    k = T[i-1] 
    if i % 2 == 0: 
      k += T[i//2] 
    else: 
      k += T[i-1] + T[i-2] 
    T[ i] = k 
    if i in [9, 17]: 
      for j in range(i): T[j] = 0 
  
 print( T[25] )

 Отправлено: 08.03.22 01:06. Заголовок: Спасибо, Константин ..

Спасибо, Константин Юрьевич!
Когда смотришь на готовый код программы, вроде все понятно, что и для чего
Поляков пишет:

цитата:

... if i in [9, 17]: for j in range(i): T[j] = 0

Вот этого кирпичика и не хватало, "на автопилоте" обнулял все, что выше 17, как в Excel-e
Поэтому, самому выстроить эти кирпичики в крепкую стену - увы, не получалось, может потому, что руки сразу тянутся к Excel
фото img

Может быть кому-то и эта картинка тоже поможет

Еще раз, огромное спасибо