Рекурсивная функция и мемоизация

@JimMor · Регистрация: 25.04.2020

Студворк — интернет-сервис помощи студентам

Функция задана рекурсивно:
f(n) = 1 если n <= 2
= f(floor(6*n/7)) + f(floor(2*n/3)) если нечётное
= f(n - 1) + f(n - 3) если чётное
(floor - это округление в меньшую сторону)

По данному n вычислите f(n), вернее, найдите остаток от деления f(n) на 2**32.

ВХОДНЫЕ ДАННЫЕ:
Программа получает на вход натуральное число n <= 10**18.

ВЫХОДНЫЕ ДАННЫЕ:
Программа должна вывести f(n) % 2**32.

Пример:
Вход: 7
Выход: 10

И ещё подсказки:
Простая рекурсия будет работать очень долго из-за того, что функция будет многократно вызываться для одного и того же значения параметра n. Чтобы этого избежать используют мемоизацию — однажды вычисленное значение функции сохраняют в массиве, и если функция была вызвана один раз для какого-то значения n, то при повторном вызове от этого n рекурсивные вызовы не будут осуществляться заново, а будет использовано сохраненное значение из массива.

Поскольку значение аргумента функции n может быть очень большим, для сохранения результатов вычисления функции необходимо использовать ассоциативный массив (map в C++ или dict в Python), у которого ключ будет иметь тип long long, а значения будут иметь тип unsigned int.

Вот мой код, прошёл 60 из 65 тестов:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
b = int(input())
from math import floor
a = {}
def f(n):
    if n in a:
        pass
    else:
        if n <= 2:
            a[n] = 1
        elif n%2 != 0:
            a[n] = f(floor(6*n/7)) + f(floor(2*n/3))
        else:
            a[n] = f(n-1) + f(n-3)
    return a[n]
print(f(b)%(2**32))

@eaa · 25.05.2020, 08:38

и где мемоизация ?

@JimMor · 25.05.2020, 08:40 **[ТС]**

Сообщение от JimMor

Чтобы этого избежать используют мемоизацию — однажды вычисленное значение функции сохраняют в массиве, и если функция была вызвана один раз для какого-то значения n, то при повторном вызове от этого n рекурсивные вызовы не будут осуществляться заново, а будет использовано сохраненное значение из массива.

Насколько я понял, это

@milssky · 25.05.2020, 09:03

JimMor, где она в вашем коде? У вас, если ключ n нашелся в словаре, вы ничего не делаете, функция вернет None. А нужно вернуть значение по ключу.
Можно было не городить эти словари, а использовать lru_cache() из functools (читать тут: https://docs.python.org/3/library/functools.html)

@JimMor · 25.05.2020, 09:06 **[ТС]**

Дак я и прошу помочь, потому что не понимаю

Добавлено через 1 минуту
А, наверное, надо вместо pass поставить

Python
1
return a[n]

?

@milssky · 25.05.2020, 09:06

Если брать ваш код, то как-нибудь так

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
b = int(input())
from math import floor
a = {}
def f(n):
    if n in a:
        return a[n]
    else:
        if n <= 2:
            a[n] = 1
        elif n%2 != 0:
            a[n] = f(floor(6*n/7)) + f(floor(2*n/3))
        else:
            a[n] = f(n-1) + f(n-3)
    return a[n]
print(f(b)%(2**32))

@JimMor · 25.05.2020, 09:09 **[ТС]**

Не, то же самое. 60 из 65 тестов

@milssky · 25.05.2020, 09:29

А что-нибудь такое?

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
from math import floor
from datetime import datetime
from functools import lru_cache
 
 
@lru_cache(maxsize=None)
def f(n):
    if n <= 2:
        return 1
    elif n%2 != 0:
        return f(floor(6*n/7)) + f(floor(2*n/3))
    else:
        return f(n-1) + f(n-3)

@JimMor · 25.05.2020, 09:32 **[ТС]**

60 из 65... Не знаю, как это работает, но оно почти работает

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from math import floor
from datetime import datetime
from functools import lru_cache
 
 
@lru_cache(maxsize=None)
def f(n):
    if n <= 2:
        return 1
    elif n%2 != 0:
        return f(floor(6*n/7)) + f(floor(2*n/3))
    else:
        return f(n-1) + f(n-3)
b = int(input())
print(f(b)%(2**32))

Я же правильно добавил?

@milssky · 25.05.2020, 09:34

И никаких подсказок? Я бы тогда внутрь функции пихнул бы вычисление остатка от деления на 2**32

@JimMor · 25.05.2020, 09:35 **[ТС]**

Подсказки, какие были, я впихнул в начало

@eaa · 25.05.2020, 09:39

ну вычисляйте результат по модулю 2^32 в функции

@JimMor · 25.05.2020, 09:51 **[ТС]**

60 из 65...

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from math import floor
from datetime import datetime
from functools import lru_cache
 
 
@lru_cache(maxsize=None)
def f(n):
    if n <= 2:
        return 1%2**32
    elif n%2 != 0:
        return (f(floor(6*n/7)) + f(floor(2*n/3)))%2**32
    else:
        return (f(n-1) + f(n-3))%2**32
b = int(input())
print(f(b))

@eaa · 25.05.2020, 10:07

Python
1
2
3
4
5
6
7
8
9
10
def f(n):
    if n not in a:
        if n <= 2:
            a[n] = 1
        elif n%2 != 0:
            a[n] = f(6*n//7) + f(2*n//3) % (2**32)
        else:
            a[n] = (f(n-1) + f(n-3)) % (2 **32)
    return a[n]
a = {}

@JimMor · 25.05.2020, 10:09 **[ТС]**

Надо, наверное, добавить только floor?

Добавлено через 43 секунды
И потом

Python
1
2
b = int(input())
print(f(b))

@eaa · 25.05.2020, 10:09

а это не одно и тоже? и быстрее вычисляется.

@JimMor · 25.05.2020, 10:14 **[ТС]**

floor округляет

Добавлено через 23 секунды
Или ты про отличия своей версии?

Добавлено через 3 минуты
УРА!!!!

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
from math import floor
a = {}
def f(n):
    if n not in a:
        if n <= 2:
            a[n] = 1 % (2**32)
        elif n%2 != 0:
            a[n] = f(6*n//7) + f(2*n//3) % (2**32)
        else:
            a[n] = (f(n-1) + f(n-3)) % (2 **32)
    return a[n]
 
b = int(input())
print(f(b))

@eaa · 25.05.2020, 10:15

floor убери

@JimMor · 25.05.2020, 10:16 **[ТС]**

зачем?

@eaa · 25.05.2020, 10:17

floor(x/y) == x//y

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	25.05.2020, 08:38
	и где мемоизация ? 1

@milssky 28 / 21 / 8 Регистрация: 05.08.2012 Сообщений: 108
	25.05.2020, 09:03
	JimMor, где она в вашем коде? У вас, если ключ n нашелся в словаре, вы ничего не делаете, функция вернет None. А нужно вернуть значение по ключу. Можно было не городить эти словари, а использовать lru_cache() из functools (читать тут: https://docs.python.org/3/library/functools.html) 1

@JimMor 3 / 2 / 1 Регистрация: 25.04.2020 Сообщений: 17
	25.05.2020, 09:09 [ТС]
	Не, то же самое. 60 из 65 тестов 0

@milssky 28 / 21 / 8 Регистрация: 05.08.2012 Сообщений: 108
	25.05.2020, 09:34
	И никаких подсказок? Я бы тогда внутрь функции пихнул бы вычисление остатка от деления на 2**32 1

@JimMor 3 / 2 / 1 Регистрация: 25.04.2020 Сообщений: 17
	25.05.2020, 09:35 [ТС]
	Подсказки, какие были, я впихнул в начало 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	25.05.2020, 09:39
	ну вычисляйте результат по модулю 2^32 в функции 1

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	25.05.2020, 10:09
	а это не одно и тоже? и быстрее вычисляется. 1

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	25.05.2020, 10:15
	floor убери 1

@JimMor 3 / 2 / 1 Регистрация: 25.04.2020 Сообщений: 17
	25.05.2020, 10:16 [ТС]
	зачем? 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	25.05.2020, 10:17
	floor(x/y) == x//y 1

Рекурсивная функция и мемоизация

Решение