Dies ist für zusätzliches Guthaben in einer Klasse von Algorithmen. Das Problem lautet
Ein König hat einen Weinkeller mit N Flaschen und eine einzige Flasche wurde vergiftet.
Das Gift braucht ungefähr einen Monat, um zu arbeiten. Der König will die genaue Flasche identifiziert mit den wenigsten Testern innerhalb von Monaten möglich.
Meine Lösung ist
Teilen Sie die N -Flaschen in M lots auf und verwenden Sie '' M Tester
Der erste Tester schmeckt sowohl die erste als auch die letzte Partie
Der zweite Tester schmeckt sowohl die erste als auch die zweite Charge.
Der dritte Tester schmeckt sowohl die zweite als auch die dritte Charge.
Fahren Sie fort für M Lose, wobei die Tester Lose überlappen.
Als die zwei Tester, die den verdorbenen Wein probierten, krank wurden, wurde das Los identifiziert. Die M-2 -Tester ließen jedem Geschmack eine Flasche aus dem verdorbenen Los, und der dritte Tester, der krank wird, identifiziert die verdorbene Flasche.
Dieser Algorithmus benötigt jedoch die doppelte Zeit, die für die Arbeit zur Verfügung steht: einen Monat, um das verdorbene Los zu identifizieren, und einen zweiten Monat, um die verdorbene Flasche zu identifizieren. Gibt es einen effizienteren Algorithmus?
Wir können es mit log2(N) Testern mit einem ziemlich ordentlichen Algorithmus machen.
Lassen Sie mich das anhand eines einfachen Beispiels demonstrieren. Nehmen Sie N = 1000 an.
Wenn wir die Flaschen 0 bis 999 kennzeichnen, dann kann jede Flasche durch eine eindeutige Binärzahl dargestellt werden, die von 0000000000 ( 0 dezimal) bis 111100111 ( 999 dezimal) reicht.
Behauptung: Wir brauchen nur 10 Tester, um die vergiftete Flasche zu finden. Hinweis: log2(N) = log2(1000) = 10 .
Algorithmus: Für die M th-Flasche erhalten wir zuerst die 10-Bit-Binärdarstellung von M . Wenn das i th Bit der Binärzahl 1 ist, lassen wir den i th Tester den Wein aus der Flasche trinken. Hinweis: 0 < M <1000, 0 < i <10 .
Betrachten Sie ein Beispiel, in dem der Tester 1st , 4th , 9th tot ist und andere Tester nach einem Monat noch aktiv sind. Wir schließen daraus, dass die 289th Flasche die vergiftete ist, da 0100100001 die binäre Darstellung der Dezimalzahl 289 ist.
Warum sind 10 Tester genug, um den vergifteten unter 1000 Flaschen zu identifizieren?
Da bei 10 -Testern am Ende alle tot oder lebendig sind, können wir insgesamt 1024 -Kombinationen haben, von denen jede verwendet werden kann, um eine Flasche aus 1024 -Flaschen eindeutig als vergiftet zu identifizieren .
Dies ist ein klassisches Puzzle, also möchte ich die Antwort nicht sofort weggeben, aber hier ist ein Hinweis: Angenommen, Sie teilen die Weinflaschen in zwei Gruppen auf, von denen jede die Hälfte der Flaschen enthält, dann haben Sie eine Person Testen Sie jede Hälfte. Das würde Ihnen einen Weg geben, um einzuschränken, welche Flasche zu einer Hälfte der Flaschen vergiftet wird.
Die Frage ist also: Gibt es eine Möglichkeit, viele verschiedene Möglichkeiten zu finden, die Weinflaschen in zwei Hälften zu zerlegen und den obigen Ansatz parallel zu betreiben? Als Hinweis, denken Sie an die binäre Darstellung von N.
Hoffe, das hilft!
Hier ist, was ich vorschlagen. Dies kommt im Wesentlichen von parallelen Algorithmen.
Das brauchen wir log2 (n) + 1 Monate. Da 1 eine Konstante ist, können wir das ignorieren und sagen, es ist O (log2 (n)).
liefert ein Beispiel:
Beschriften Sie jede Flasche mit 1 bis n und betrachten Sie jede als Binärzahl. z.B. 11 Flaschen
%Vor%Nun, von rechts nach links, nehmt zuerst einen Tropfen von jeder der Flaschen, deren hellstes Bit auf "1" gesetzt ist, und deponiert in der ersten Tasse. Zweitens nehmen Sie einen Tropfen aus jeder Flasche, deren 2. Bit auf "1" gesetzt ist, und legen Sie in der zweiten Tasse ab Fahren Sie in ähnlicher Weise durch das höchste Bit fort. Insgesamt benötigen wir 4 Tassen und 4 Verkoster.
%Vor% Wir ordnen jetzt die Verkoster den Bechern zu und bilden die Bechern in Bits ab
Command Tasters zu trinken. In einem Monat werden einige deiner Verkoster tot sein.
z.B. taster3 und taster1 werden tot
Setzen Sie dann die entsprechenden Bits auf 1 und alle anderen Bits auf 0. Die resultierende Binärzahl
00000101 identifiziert die vergiftete Flasche.
die Anzahl der Prüfer f (n) = (int) (logn) +1, also ist f (n) O (logn)
Tags und Links algorithm