Myślenie o tym jak o problemie z drzewem to śledź czerwony, to tak naprawdę wykres kierunkowy. Ale zapomnij o tym wszystkim.
Pomyśl o szklance gdziekolwiek poniżej górnej. Będzie miał jedną lub dwie szklanki nad nim, które mogą się do niego przelać. Przy odpowiednim wyborze układu współrzędnych (nie martw się, patrz koniec) możemy napisać funkcję, aby uzyskać okulary „macierzyste” dla dowolnego szkła.
Teraz możemy pomyśleć o algorytmie, aby uzyskać ilość płynu wlewaną do szklanki, niezależnie od przelewu z tego szkła. Odpowiedź jest jednak taka, że do każdego rodzica wlewa się dużo płynu minus ilość przechowywana w każdym szkle rodzicielskim, podzielona przez 2. Wystarczy zsumować to dla wszystkich rodziców. Zapisanie tego jako fragmentu Pythona w treści funkcji quant_poured_into ():
# p is coords of the current glass
amount_in = 0
for pp in parents(p):
amount_in += max((amount_poured_into(total, pp) - 1.0)/2, 0)
Funkcja max () ma zapewnić, że nie wystąpi ujemna przepełnienie.
Jesteśmy prawie skończeni! Wybieramy układ współrzędnych z „y” w dół strony, szklanki pierwszego rzędu to 0, drugi rząd to 1 itd. Współrzędne „x” mają zero pod szkłem górnego rzędu, a drugi rząd ma współrzędne x -1 i +1, trzeci rząd -2, 0, +2 i tak dalej. Ważną kwestią jest to, że lewe lub prawe szkło na poziomie y będzie miało abs (x) = y.
Podsumowując wszystko w Pythonie (2.x), mamy:
def parents(p):
"""Get parents of glass at p"""
(x, y) = p
py = y - 1 # parent y
ppx = x + 1 # right parent x
pmx = x - 1 # left parent x
if abs(ppx) > py:
return ((pmx,py),)
if abs(pmx) > py:
return ((ppx,py),)
return ((pmx,py), (ppx,py))
def amount_poured_into(total, p):
"""Amount of fluid poured into glass 'p'"""
(x, y) = p
if y == 0: # ie, is this the top glass?
return total
amount_in = 0
for pp in parents(p):
amount_in += max((amount_poured_into(total, pp) - 1.0)/2, 0)
return amount_in
def amount_in(total, p):
"""Amount of fluid left in glass p"""
return min(amount_poured_into(total, p), 1)
Tak więc, aby uzyskać ilość faktycznie w szklance przy p, użyj kwoty_w (ogółem, p).
Z PO nie jest to jasne, ale fragment dotyczący „nie można dodać parametrów” może oznaczać, że na oryginalne pytanie należy odpowiedzieć pod względem wyświetlanych liczb szklanych . Rozwiązuje się to poprzez zapisanie funkcji mapowania z numerów szkieł pokazowych na wewnętrznym układzie współrzędnych stosowanym powyżej. To kłopotliwe, ale można zastosować iteracyjne lub matematyczne rozwiązanie. Łatwa do zrozumienia funkcja iteracyjna:
def p_from_n(n):
"""Get internal coords from glass 'number'"""
for (y, width) in enumerate(xrange(1, n+1)):
if n > width:
n -= width
else:
x = -y + 2*(n-1)
return (x, y)
Teraz po prostu przepisz powyżej funkcję quant_in (), aby zaakceptować liczbę szklaną:
def amount_in(total, n):
"""Amount of fluid left in glass number n"""
p = p_from_n(n)
return min(amount_poured_into(total, p), 1)
