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

@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): сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	Установка Emscripten SDK (emsdk) и CMake на Windows для сборки C и C++ приложений в WebAssembly (Wasm) 8Observer8 30.01.2026 Чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. Система контроля версиями Git. . .	Подключение Box2D v3 к SDL3 для Android: физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	Влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .

@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

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

Решение