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

@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

Новые блоги и статьи Все статьи Все блоги /
Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .	Функция заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .
Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем	10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .

@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

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

Решение