Форум: «ЕГЭ по информатике»

На этом форуме отвечают на конкретные вопросы. Фраза «я не понимаю, как решать» — это не вопрос. На вопрос «как решить задачу №X» вас отошлют к материалам сайта kpolyakov.spb.ru. За бессвязный поток слов и неспособность формулировать свои мысли — бан.

Если у вас не сходится ответ на какую-то задачу, пожалуйста сразу представляйте свое «правильное» решение.

Программы "заворачивайте" в тэг [pre2]...[/pre2], при этом сохраняются все отступы и применяется моноширинный шрифт. Если у вас используется сочетание "[i]" для обозначения элемента массива или строки, ставьте пробел после открывающей скобки. Иначе система выделит все дальнейшее курсивом.

Для регистрации на форуме щелкните по ссылке «Вход-регистрация» вверху страницы. В открывшееся окошко «ник» введите свою фамилию на русском языке (например, Иванов). В окошко «пароль» введите придуманный вами пароль, состоящий из латинских букв и цифр. Поставьте галочку в окошке «зарегистрироваться, я новый участник» и нажмите кнопку «ОК».

Форум » Системы счисления » (№ 5268) (Е. Джобс)
	перенос

Автор

Сообщение

Ar3turrr

Сообщение: 28

Отправлено: 12.03.23 12:23. Заголовок: (№ 5268) (Е. Джобс)

Не понимаю, что делаю не так. Ответ получается 61982.

def F(n): 
     S = 1 
  
     if n < 3: return 1 
  
     if S % 2 == 0: return F(n - 1) - F(n - 2) 
  
     else: return F(n - 1) + F(n // 2) 
  
 print(F(100))

Профиль

Цитата

Ответить

Ответов - 3 [только новые]

ЕленаФом

Сообщение: 9

Отправлено: 13.03.23 18:23. Заголовок: Правильное решение

 
 from functools import lru_cache 
  
 @lru_cache 
 def F(n):   
 	if n < 3: return 1 
 	S = sum([int(c) for c in str(n)]) 
 	#print(n,S) 
 	if S % 2 == 0:  
 		return F(n - 1) - F(n - 2)  
 	else:  
 		return F(n - 1) + F(n // 2)  
 	 
 print(F(100)) # 23

Кеширование важно, иначе очень долго. И нельзя писать как у вас S = 1, поскольку при вложенных вызовах рекурсии будут другие суммы цифр числа n, ваша программа просто "не туда" улетает после первого вызова.

Профиль

Цитата

Ответить

Ar3turrr

Сообщение: 31

Отправлено: 14.03.23 14:56. Заголовок: ЕленаФом пишет: Кеш..

ЕленаФом пишет:

цитата:

Кеширование важно, иначе очень долго.

Что такое кеширование? Что именно делает кеширование? И нужно ли его использовать всегда, когда дело касается рекурсии?

Профиль

Цитата

Ответить

Поляков
Администратор
Сообщение: 3943

Отправлено: 17.03.23 14:12. Заголовок: Ar3turrr пишет: Что ..

Ar3turrr пишет:

цитата:

Что такое кеширование? Что именно делает кеширование? И нужно ли его использовать всегда, когда дело касается рекурсии?

Кэширование (мемоизация) - это сохранение в памяти всех вычисленных ранее значений функции. Если мы уже вычислили F(100), то в следующий раз уже не нужно выполнять вычисления, а можно просто взять готовое значение.
Кэширование необходимо, когда рекурсивная функция вызывает сама себя несколько раз (здесь - два) и очень долго работает. Кэширование служит для ускорения вычислений. Вместо него можно использовать динамическое программирование, когда результаты предыдущих вычислений сохраняются в массиве.

Профиль

Цитата

Ответить

Ответ:

1 2 3 4 5 6 7 8 9

показывать это сообщение только модераторам
не делать ссылки активными

Имя, пароль:

зарегистрироваться

Форум » Системы счисления » (№ 5268) (Е. Джобс)

Тему читают:

- участник сейчас на форуме

- участник вне форума

Все даты в формате GMT 3 час. Хитов сегодня: 1396
Права: смайлы да, картинки да, шрифты нет, голосования нет
аватары да, автозамена ссылок вкл, премодерация откл, правка нет

Создай свой форум на сервисе Borda.ru
Форум находится на 2 месте в рейтинге
Текстовая версия