python - 向一叠玻璃杯中加水

Question

我一直想知道帕斯卡三角形是否有任何实际应用，而不仅仅是二项式展开的系数。
我试图解决这个问题:


但是，如果我添加 K 个单位的水并想找到一个水量最少的玻璃杯怎么办:
哪里可以找到 Glass 为:c - 第玻璃 r -扔
我相信。如果我们能找到这个，那么我们就不难找到任何玻璃杯中的水量 {i<r and j<c}

问题:
输入
加水-K单位，每杯容量为1-单位
预期输出 :c第玻璃 r水最少的那一排。

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

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

#不确定，但在我看来，@which 水的添加率是这样的。

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

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

Δ1, Δ2 = 0, 0
if g(n-1, k)>1 and k <= n-1:
    Δ1 = g(n-1, k) -1 
if g(n-1, k-1)>1 and k-1 <= n-1:
    Δ2 = g(n-1, k-1) - 1
g(n, k) = Δ1/2 + Δ2/2

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

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

不知道少了什么？

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