Подснежная последовательность, оптимизация кода

Question

Подснежная последовательность, оптимизация кода

Рейтинг: 1Ответов: 2Опубликовано: 21.03.2023

Пусть s(n) - ближайший квадрат к натуральному числу n. Подснежная последовательность строится следующим образом: первые два её члена это 1 и 3, а каждый следующий член a_k=s(a_{k-1})+s(a_{k-2}). Написать программу, которая печатает первые 20 членов подснежной последовательности.

# Пусть s(n) - ближайший квадрат к натуральному числу n. 
# Подснежная последовательность строится следующим образом: 
# первые два её члена это 1 и 3, а каждый следующий член 
# a_k=s(a_{k-1})+s(a_{k-2}). Написать программу, 
# которая печатает первые 20 членов подснежной последовательности. 

def nearest_square(n):
    root = int(n**0.5)
    lower_diff = abs(n - root**2)
    upper_diff = abs(n - (root + 1)**2)
    return root**2 if lower_diff <= upper_diff else (root + 1)**2

def snowdrop_sequence(n):
    sequence = [1, 3]
    for i in range(2, n):
        next_term = nearest_square(sequence[-1]) + nearest_square(sequence[-2])
        sequence.append(next_term)
    return sequence

first_20_terms = snowdrop_sequence(20)
print(first_20_terms)

Вывод программы: 1, 3, 5, 8, 13, 25, 41, 61, 100, 164, 269, 425, 697, 1117, 1765, 2853, 4573, 7433, 12020, 19496

Теперь представим, что нам нужно не 20, а достаточно много членов подснежной последовательности. Как можно ускорить код?

python оптимизация арифметика числовые-последовательности

Источник: Stack Overflow на русском

Answer 1

▲ 2Принят

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

def snowdrop_sequence(n):
    sequence = [1, 3]
    nearest_2, nearest_1 = list(map(nearest_square, sequence))
    for i in range(2, n):
        next_term = nearest_1 + nearest_2
        sequence.append(next_term)
        nearest_1, nearest_2 = nearest_square(next_term), nearest_1
    return sequence

Answer 2

▲ 2

@tym32167 , вот так?

from functools import lru_cache

@lru_cache(maxsize=None)  # Кешируем результаты функции nearest_square
def nearest_square(n):
    root = int(n**0.5)
    lower_diff = abs(n - root**2)
    upper_diff = abs(n - (root + 1)**2)
    return root**2 if lower_diff <= upper_diff else (root + 1)**2

def snowdrop_sequence(n):
    sequence = [1, 3]
    for i in range(2, n):
        next_term = nearest_square(sequence[-1]) + nearest_square(sequence[-2])
        sequence.append(next_term)
    return sequence

# Теперь при больших значениях n, код будет работать быстрее
first_100_terms = snowdrop_sequence(100)
print(first_100_terms)

Вывод программы:

1, 3, 5, 8, 13, 25, 41, 61, 100, 164, 269, 425, 697, 1117, 1765, 2853, 4573, 7433, 12020, 19496, 31700, 51284, 82760, 134020, 216900, 351112, 568805, 920165, 1488197, 2408081, 3897104, 6305380, 10201797, 16506757, 26709605, 43216193, 69925700, 113140520, 183068813, 296206669, 479279421, 775478185, 1254715073, 2030173493, 3284851333, 5315027845, 8599887812, 13914958912, 22514999140, 36430035944, 58945214189, 95375253485, 154320393037, 249695474137, 404015215921, 653710419909, 1057726385460, 1711436916340, 2769162809725, 4480599198361, 7249763174449, 11730361809493, 18980125582888, 30710493812605, 49690623418186, 80401122815989, 130091745597853, 210492866062618, 340584607064113, 551077447034740, 891662044995877, 1442739517477042, 2334401572620442, 3777141062960946, 6111542628168525, 9888683713841236, 16000226356582057, 25888910036127322, 41889136396880722, 67778046436976170, 109667182878757033, 177445229232365748, 287112412194693453, 464557641302556514, 751670053750020250, 1216227696366846501, 1967897750744648520, 3184125448249755144, 5152023198937958949, 8336148646858989345, 13488171844543537257, 21824320486505393170, 35312492328873094585, 57136812821284645465, 92449305150700940314, 149586117968721087925, 242035423114604532541, 391621541062391098237, 633656964170622875752, 1025278505252824589892

Подснежная последовательность, оптимизация кода

Ответы