香檳塔問題

問題描述

我們將玻璃杯堆成金字塔狀，第一排有 1 個玻璃杯，第二排有 2 個玻璃杯，依此類推，直到第 100 排。每個玻璃杯裝一杯香檳。

然后，將一些香檳倒入最上面的第一個玻璃杯中。當最上面的玻璃杯裝滿時，任何多余的液體都會均勻地落到它左右兩側的玻璃杯上。當這些玻璃杯裝滿時，任何多余的香檳都會均勻地落到這些玻璃杯的左右兩側，依此類推。（最下面一排的玻璃杯中多余的香檳會落到地板上。）

例如，倒完一杯香檳后，最上面的玻璃杯是滿的。倒完兩杯香檳后，第二排的兩個玻璃杯是半滿的。倒完三杯香檳后，這兩個杯子就滿了——現在總共有 3 個滿的玻璃杯。倒完四杯香檳后，第三排中間的杯子半滿，外面的兩個杯子滿四分之一，如下圖所示。

本質上，這個問題是瀑布級聯的建模，是帕斯卡三角形的變體，其中三角形中的每個項目都是其“左父級”和“右父級”的總和。這里，我們需要計算總溢出和，而不是總和。

問題說明

通過閱讀問題描述，我們可以了解級聯效應，以及塔頂的行如何影響其下方的行。但是，考慮到描述的行/列性質，我們應該開始將“香檳塔”視為數組的數組，其中塔中的每個索引都由一個長度比前一個索引大一的數組組成：

例如：塔 = [ [0], [0,0], [0,0,0], … ]

考慮到這一點，我們不要將塔描繪成如圖所示的等邊三角形，而是重新設想塔，使每行的索引對齊（直角三角形），并查看它們的值如何相互關聯，以了解描述中描述的前 4 次倒酒。

One Pour:
[ 1 ], 
[ 0, 0 ], 
[ 0, 0, 0 ], 
[ 0, 0, 0, 0 ], Two Pours:
[ 1 ], 
[ 0.5, 0.5 ], 
[ 0  , 0  , 0 ], 
[ 0  , 0  , 0  , 0 ]Three Pours:
[ 1 ], 
[ 1  , 1 ], 
[ 0  , 0  , 0 ], 
[ 0  ,