主页 / 问题 / 1506766
Accepted
Ян Альбертович Дененберг
Asked:2023-03-21 07:38:01 +0000 UTC2023-03-21 07:38:01 +0000 UTC

白雪皑皑的序列，代码优化

  • 772

设 s(n) 是最接近自然数 n 的平方。snow 序列构造如下：它的前两个成员是 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 个，而是 snowy 序列中的相当多的成员。你如何加速代码？

python

2 个回答

  1. @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
    • 2
  2. Best Answer

    事实上，对于计算你只需要函数的最后两个值，你可以记住并移动它们。这里只是代码的修改部分：

    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
    • 2

相关问题