7

この質問はフォーラムで行われました。助言がありますか？

レベルに1カップ、レベル2に2カップ、レベル3に3カップなどのピラミッドがあります。次のようになります。

  1
 2 3
4 5 6

すべてのカップの容量はCです。上からLリットルの水を注ぎます。カップ1がいっぱいになると、カップ2、3に均等にオーバーフローし、カップ4と6は、それぞれ2と3からのみ水を受け取りますが、5は両方のカップから水を受け取ります。ここでCとLが与えられます。i番目のカップの水の量を見つけますか？

4

6 に答える 6

9

各グラスには、入ってくるフロー、グラス内の水の量、および場合によってはいくらかの出て行くフロー(オーバーフロー) があります。

各グラスに 1 単位の水を入れることができ、15 単位の水を注ぐと、次のようになります (括弧内はオーバーフロー量)。

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

最初のレベルへの流入フローは L です。レベルのガラスからの流入フローはであり、次のように記述できます。crFin(c, r)

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

そのグラスの水の量は次のとおりです。

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

そして、発信フローは次のとおりです。

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

A(c, r)再帰的に行わずに評価するための明白な式は見当たりません。

インデックスから行とグラスの位置に移動するには、次のようにします。

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

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

(indexes start with 1)
于 2012-08-01T19:07:24.653 に答える
0

いくつかのアイデア: (1) 重要なのは、どの 2 つのカップが i 番目のカップへの入力であるかを知ることです。(2) 重要なのは、左側から水をもたらす最小 Lleft と、右側から水をもたらす Lright のレベルを知ることです (3) したがって、カップ i に水を提供するカップを知る必要があります。0 から番号を付け始めると、これは簡単に考えられます。カップ i は (i-1)*2+1 と i*2 を満たします。これは、カップ k が (k%2=1 の場合) から水を受け取ることを意味します ( k-1)/2 および (k+1)/2 (k%2=0 の場合) k/2 および k/2+1 (4) これで、任意の L について差 L- を計算することを確認する必要があります。 Lleft と L-Lright です。正の場合、提供される水は、計算された差を 2^n で割った結果になります。ここで、n はカップのレベルです。

于 2012-08-01T18:42:04.587 に答える
0

ピラミッドをグラフにモデル化すると、問題は幅優先探索に変換されます。各ノードをトラバースするときに、その隣接ノードを取得し、オーバーフロー量を保存します。ネイバーが以前のノードによって既に取得されている場合 (これは、ノード 2 とノード 3 にエッジがあるため、5 ノードの場合に発生します)、その容量と既に満たされているものに基づいてオーバーフローを更新する必要があります (ノード 2 によって、ノード 2 がノード 3 の前にトラバースされたと仮定します)。

于 2012-08-02T06:37:17.053 に答える