python - 在 python 中计算嵌套总和

Question

我是编程和 python 的新手，所以我想问你们一个通过编程计算双西格玛的简单方法

(∑ⁿ_i=1)(∑^m_k=1)(i+k)

我正在尝试解决问题，但我卡在需要初始化 p 的部分，任何提示都将被应用。

这是我到目前为止尝试过的

p = 1
sum = 0

N,M=[int(i) for i in input().split()]
for i in range(1,N+1):
    for i in range(i+1,i+M+1):
        p=p*i
    sum += p

print(sum)

Answer 1

考虑以下几点:

这意味着您的原始二次 O(m*n) 算法可以替换为线性 O(m+n) 解决方案:

In [1]: from hypothesis import strategies as st
   ...: from hypothesis import given, settings
   ...: 
   ...: 
   ...: def linear(n, m):
   ...:     return n * sum(range(1, m+1)) + m * sum(range(1, n+1))
   ...: 
   ...: 
   ...: def quadratic(n, m):
   ...:     total = 0
   ...:     for i in range(1, n+1):
   ...:         for j in range(1, m+1):
   ...:             total += i + j
   ...:     return total
   ...: 
   ...: 
   ...: @given(st.integers(1, 50), st.integers(1, 50))
   ...: @settings(max_examples=1000)
   ...: def test(n, m):
   ...:     assert linear(n, m) == quadratic(n, m)
   ...: 
   ...:     

In [2]: test()

In [3]: %timeit linear(10, 10)
852 ns ± 15.8 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [4]: %timeit quadratic(10, 10)
7.93 µs ± 165 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

由于您是初学者，我添加了一个简单的自动属性测试来:1) 强调测试一个有效的原始解决方案与一个优化的替代方案的重要性，2) 证明等价性。还有一些针对小型 n 和 m 的基准测试。

并且由于存在算术级数和(即 M 和 N)的封闭式方程，您可以进一步将其归结为常数时间 O( 1) 解决方案(我在这里做了一些简化):

In [5]: def constant(n, m):
   ...:     return n * m * (2 + m + n) / 2
   ...: 
   ...: 

In [6]: %timeit constant(10, 10)
151 ns ± 1.4 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

附言

如果没有充分的理由，您永远不应该在全局 namespace 中隐藏内置名称(例如 sum = 0)。