0

我的作业中有一个问题涉及数组和 for 循环。

该问题要求您找出 的值int(m[3,4])。

import numpy as np

m = np.zeros((20,20))

for i in range(1,20):
  for j in range(1,20):
    m[i,j] = m[i-1,j]+m[i,j-1]+ 1

print(int(m[3,4]))

我试过写出m[i, j]fori和j0 到 5 范围内的所有值来 find m[3,4]，但我想知道是否有更短的做事方式？

预期答案是 34。

4

4 回答 4

2

这只是项为负 1 的帕斯卡三角形。

因此，复杂性与找到 n 选择 k 相同。

python中有数学nCr函数吗？

import operator as op
from functools import reduce

def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer / denom

有了这个，

m[i, j] = ncr(i+j, i) - 1
于 2019-09-12T15:54:11.257 回答
0

对于 1 到 20 范围内的所有 i,j 是 400 项。你可以通过计算12个词找到答案

这是矩阵：

a-----b-----c-----d

e-----f-----g-----h

i-----j-----k-----l

m-----n-----o-----p

每一项是相邻的左边和上面的和加1。例如k = j + g + 1

现在遍历矩阵。对于 i,j = 1,1，前 2 项为零，所以 a = 1，

aa 右边或下面的所有项都加 1。现在我们有：

1-----2-----3-----4

2-----f-----g-----h

3-----j-----k-----l

4-----n-----o-----p

现在

f = 2 + 2 + 1 = 5
g = 5 + 3 + 1 = 9

继续获得：

1-----2-----3-----4

2-----5-----9-----14

3-----9-----19-----34<--

m-----n-----o-----p
于 2019-09-12T15:49:05.983 回答
0

我建议写一个例子，并找到模式。打印生成的 5x5 矩阵，你会看到

[[ 0.  0.  0.  0.  0.]
 [ 0.  1.  2.  3.  4.]
 [ 0.  2.  5.  9. 14.]
 [ 0.  3.  9. 19. 34.]
 [ 0.  4. 14. 34. 69.]]

请注意，矩阵是对称的，即m[i,j] == m[j,i]。由此，您将知道您只需要进行一半的计算。您可以先找到下三角矩阵或上三角矩阵，然后您将通过对称得到答案。

于 2019-09-12T15:50:55.603 回答
0

另一种解决方案：

Python 3.8.0b4 (default, Sep  5 2019, 14:10:43)
Type 'copyright', 'credits' or 'license' for more information
IPython 7.8.0 -- An enhanced Interactive Python. Type '?' for help.

In [1]: import numpy as np

In [2]: N = 20

In [3]: m = np.zeros((N, N), int)

In [4]: x = m[:]

In [5]: for i in range(1, N):
   ...:     for j in range(1, N):
   ...:         m[i, j] = m[i - 1, j] + m[i, j - 1] + 1
   ...:

In [6]: for i in range(1, N):
   ...:     x[i] = [sum(x[i - 1, :j]) + j for j in range(N)]
   ...:

In [7]: (m == x).all()
Out[7]: True
于 2019-09-12T15:43:28.337 回答