Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.2k views
in Technique[技术] by (71.8m points)

algorithm - Find the amount of water in ith cup in a pyramid structure?

This question was asked in a forum. Any suggestions?

There is a pyramid with 1 cup at level , 2 at level 2 , 3 at level 3 and so on.. It looks something like this

  1
 2 3
4 5 6

every cup has capacity C. you pour L liters of water from top . when cup 1 gets filled , it overflows to cup 2,3 equally, and when they get filled , Cup 4 and 6 get water only from 2 and 3 resp but 5 gets water from both the cups and so on. Now given C and L .Find the amount of water in ith cup ?

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

Each glass has an incoming flow, an amount of water in the glass, and maybe some outgoing flow (overflow).

If each glass can contain 1 unit of water, and you pour 15 units of water, you get the following (overflow amount in parenthesis):

Incoming flow = 15, capacity = 1

Level 1:               1(14)
Level 2:           1(6)     1(6)
Level 3:       1(2)     1(5)     1(2)
Level 4:    1(1)   1(2.5)  1(2.5)    1(1)
Level 5:   1  1(0.75)  1(1.5)  1(0.75)   1
Level 6:  0 0.375 1(0.125) 1(0.125) 0.375 0
Level 7: 0 0  0.0625   0.125    0.0625   0 0

The incoming flow to the first level is L. The incoming flow from glass c on level r is Fin(c, r), and could be written as:

Fin(0, r) = 0
Fin(r+1, r) = 0
Fin(1, 1) = L
Fin(c, r) = Fout(c - 1, r - 1)/2 + Fout(c, r - 1)/2

The amount of water in that glass is:

A(c, r) = Min(C, Fin(c, r))

And the outgoing flow is:

Fout(c, r) = Max(0, Fin(c, r) - C)

I don't see any obvious formula for evaluating A(c, r) without doing it recursively.


To get from an index to a row and glass position, you can do:

index = r*(r-1)/2 + c

r = floor((1 + sqrt(8*index - 7))/2)
c = index - r*(r-1)/2

(indexes start with 1)

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...