Generalisiertes Zweieipuzzle

(1) Betrachte den Fall, dass der erste Tropfen das Ei bricht. Dann kannst du den Breakfloor genau dann bestimmen, wenn er höchstens f [d-1, e-1] ist. Daher können Sie nicht höher als f [d-1, e-1] + 1 beginnen (und natürlich nicht tiefer beginnen).

(2) Wenn dein erster Tropfen das Ei nicht bricht, bist du im Fall von f [d-1, e], beginnend am Boden deines ersten Tropfens + 1 , anstelle von Boden 1.

Also, das Beste, was du tun kannst ist, Eier auf dem Boden f [d-1, e-1] + 1 (wegen (1)) fallen zu lassen, und du kannst aufstehen f [d-1, e] Stockwerke höher als das (wegen (2)). Das ist

Aus Wiki Egg Dropping wissen wir, dass die Zustandsübertragungsgleichung lautet:

  

W(n,k) = 1 + min{ max(W(n − 1, x − 1), W(n,k − x)) } , x = 1, 2, ..., k

     

W(n,1)=1, W(1,k)=k

     

n = Anzahl der verfügbaren Testeier

     

k = Anzahl der (noch nicht getesteten) aufeinanderfolgenden Stockwerke

Unten ist mein Verständnis.

Wir haben k floors, n eggs, nehmen an, dass wir ein Ei zum Testen in x floor verwenden. Es gibt nur zwei mögliche Ergebnisse:

1. es bricht, so kommt das Problem rekursiv zu: x-1 floors, n-1 eggs, was zu W(n-1,x-1) widerspiegelt
2. es bricht nicht, also kommt das Problem rekursiv zu: k-x floors, n eggs, was zu W(n,k-x) widerspiegelt

Da das Problem den schlimmsten Fall erfordert, müssen wir den größeren auswählen, um sicherzustellen, dass der Worst Case funktioniert. Deshalb fügen wir ein Maximum zwischen W(n-1,x-1) und W(n,k-x) hinzu.

Abgesehen davon, da wir nur Tests in x floor angenommen haben, kann x von 1 bis k sein. In dieser Situation müssen wir definitiv das Minimum wählen, um sicherzustellen, dass die minimalen experimentellen Tropfen dies herausfinden N , deshalb fügen wir eine Min zwischen {max(W(n − 1, x − 1), W(n,k − x)): x = 1, 2, ..., k}

Schließlich, da wir 1 drop in x floor verwendet haben, muss die Gleichung 1 hinzufügen, was sich auf den ersten Teil der Gleichung bezieht.

Hoffe, dass dein Puzzle löst: -)

dynamische Programmierung basierte Lösung hier - Ссылка

Ich glaube, dass es selbsterklärend ist .. bitte zögern Sie nicht zu fragen, ob ein Teil nicht klar ist .. wird Ihnen gerne erklären

Dieses Problem kann mit den folgenden drei Ansätzen (die ich kenne) gelöst werden:

1. Dynamische Programmierung
2. Lösung mit binärer Suchstruktur
3. Lösung durch die direkte mathematische Formel für die maximale Anzahl von Stockwerken, die getestet oder mit einer bestimmten Anzahl von Eiern und einer gegebenen Anzahl von Tropfen bedeckt werden können

Lassen Sie mich zuerst einige Symbole definieren, die später in der Analyse verwendet werden:

Der Kernpunkt für den dynamischen Programmieransatz liegt in der folgenden rekursiven Formel für Fmax:

Und der Schlüssel zum Erhalten der direkten mathematischen Formel für Fmax liegt in der folgenden rekursiven Formel für Fmax:

Alternativlösung für den Binärsuchbaum (BST) ist auch für dieses Problem möglich. Um unsere Analyse zu erleichtern, lassen Sie uns BST mit leichten Modifikationen wie folgt zeichnen:

Wenn wir BST mit der obigen Darstellungsart zeichnen, dann entspricht die Breite der BST der Anzahl der Eier.

Jede BST mit einer f-Anzahl von Knoten, die mit der obigen Darstellungsart gezeichnet sind und der Beschränkungsbreite von BST & lt; = e (Anzahl von Eiern) unterworfen sind, ist eine Lösung, aber möglicherweise nicht die optimale Lösung.

Somit ist das Erhalten der optimalen Lösung äquivalent zum Erhalten der Anordnung von Knoten in BST mit minimaler Höhe, die der Beschränkung unterworfen ist: Breite von BST & lt; = e

Weitere Einzelheiten zu allen oben genannten 3 Ansätzen finden Sie in meinem Blog unter: 3 Ansätze zur Lösung des generalisierten Eitropfenproblems