向一叠玻璃杯中加水

Question

我一直想知道帕斯卡三角形是否有任何实际应用，而不仅仅是二项式展开式的系数。

\n

我试图解决这个问题：

\n

\n

\n

但是，如果我添加 K 个单位的水，并且想要找到一个水含量最少的玻璃杯，该怎么办：

\n

其中，Glass 将被发现为： 第 -th 行c中的 -th glassr

\n

我相信。如果我们能找到这个，那么我们就不难找到任意玻璃杯中的水量了。{i<r and j<c}

\n

\n

• 问题：

  \n

  输入\n添加的水 - K 单位，每个玻璃杯的容量为 1- 单位

  \n

  预期输出：第排c中的第一个玻璃杯r中的水最少。

  \n
\n

\n

我试图通过记录每行开始溢出时的容量来解决问题：\n并想知道如何继续使用此方法。

\n

      1       max = 1, cap = 1\n     1 1      max = 1, sum(coefficients)=2**1 = 2, cap = 2/1 \n    1 2 1     max = 2, sum = 2**2, cap = 4/2 = 2 units \n   1 3 3 1    max = 3, sum = 2**3, cap = 8/3 units\n  1 4 6 4 1   max = 6, sum = 2**4, cap = 16/6 units \n

\n

#不确定，但在我看来，这就是添加水的速率。

\n

                 1\n              1/2   1/2\n           1/4   2/4  1/4\n        1/8   3/8    3/8   1/8\n     1/16  4/16  6/16   4/16  1/16  \n

\n

我应该使用二维列表并定义为：

\n

\xce\x941, \xce\x942 = 0, 0\nif g(n-1, k)>1 and k <= n-1:\n    \xce\x941 = g(n-1, k) -1 \nif g(n-1, k-1)>1 and k-1 <= n-1:\n    \xce\x942 = g(n-1, k-1) - 1\ng(n, k) = \xce\x941/2 + \xce\x942/2\n

\n

g(n,k) = g(n-1, k-1) + g(n-1, k)

\n

g = [[0]*(i+1) for i in range(11)]\ndef f(g, K):\n    g[1][1] += 1\n    K = K-1\n    d1, d2 = 0, 0\n    for n in range(2, 10):\n        for k in range(1, n+1):\n            if k ==1:\n                g[n][k] = g[n-1][k]/2\n            if k == n:\n                g[n][k] = g[n-1][k-1]/2\n            else:\n                if g[n-1][k-1]>1:\n                    d1 = g[n-1][k-1] -1\n                if g[n-1][k] > 1:\n                    d2 = g[n-1][k] -1\n                g[n][k] = d1/2 + d2/2        \n    return g, K\nk = int(input())\nwhile k:\n    g, k = f(g, k)\nfor x in g:\n    print(x)\n

\n

不知道还缺什么？

\n

Answer 1

对于这样小的K约束，简单的逐行填充就足够了（我们只能存储两行，为了简单起见，这里使用 2D 列表）

def fillGlasses(k, row, col):
    gl = [[k]]
    level = 1
    overflow_occured = True
    while overflow_occured:   # also can stop when at needed row
        print(gl[level-1])  #before overflow
        level += 1
        overflow_occured = False
        gl.append([0]*level)
        for i in range(level - 1):
            t = gl[level-2][i] - 1
            if t > 0:
                gl[level-1][i] += t/2
                gl[level-1][i+1] += t/2
                gl[level-2][i] = 1
                overflow_occured = True
    #print(gl)  #after all
    return gl[row-1][col-1]

print(fillGlasses(21,8,4))

[21]
[10.0, 10.0]
[4.5, 9.0, 4.5]
[1.75, 5.75, 5.75, 1.75]
[0.375, 2.75, 4.75, 2.75, 0.375]
[0, 0.875, 2.75, 2.75, 0.875, 0]
[0, 0, 0.875, 1.75, 0.875, 0, 0]
[0, 0, 0, 0.375, 0.375, 0, 0, 0]
0.375