Champagner Brunnen Puzzle

Leere Gläser Wasser werden in der folgenden Reihenfolge angeordnet:

Wenn Sie Flüssigkeit in das erste Glas einfüllen, wenn es voll ist, wird die zusätzliche Flüssigkeit in gleichen Mengen in die Gläser 2 und 3 eingefüllt. Wenn Glas 2 voll ist, wird die zusätzliche Flüssigkeit in 4 und 5 usw. geflogen.

Bei einem Flüssigkeitsgehalt von N Litern und einem maximalen Fassungsvermögen von 1 Liter pro Glas geben Sie die in einem Glas vorhandene Flüssigkeitsmenge an, wenn Sie N Liter Flüssigkeit durch Eingießen in das Glas leeren, indem Sie die Funktion ausfüllen, getWaterInBucket(int N, int X)bei der X die Glaszahl ist. Wenn ich zum Beispiel am Anfang 4 Liter haben möchte und das Wasser in Glas 3 finden möchte, ist die FunktiongetWaterInBucket(4, 3)

Wie löse ich das programmatisch? Ich habe versucht, mit Pascals Dreieck eine mathematische Lösung zu finden. Das hat nicht funktioniert. Ich habe es als einen Baum betrachtet, also kann ich einen Parameter wie diesen hinzufügen getWaterInBucket(BTree root, int N, int X)und dann eine rekursive Lösung für jede Ebene versuchen, aber Parameter sind in diesem Problem nicht zulässig. Gibt es einen offensichtlichen Trick?

Sie müssen nur das Gießen simulieren, so etwas wie

void pour(double glasses[10], int glass, double quantity)
{
    glasses[glass] += quantity;
    if(glasses[glass] > 1.0)
    {
         double extra = glasses[glass] - 1.0;
         pour( glasses, left_glass(glass), extra / 2 );
         pour( glasses, right_glass(glass), extra / 2 );
         glasses[glass] = 1.0;
    }
}

double getWaterInGlass(int N, int X)
{
    double glasses[10] = {0,0,0,0,0,0};
    pour(glasses, 0, X);
    return glasses[N];
}

So wie es aussieht, ist dies kein Baum. Weil verschiedene Gläser in die gleichen Gläser fließen, wird verhindert, dass es sich um einen Baum handelt.

So würde ich diese Frage in einer Interview-Situation beantworten (ich habe diese Frage vorher noch nicht gesehen und mir die anderen Antworten nicht angesehen, bis ich meine Lösung gefunden habe):

Zuerst habe ich versucht, es herauszufinden (was Sie die "mathematische Lösung" nannten), und als ich zu Glas 8 kam, wurde mir klar, dass es härter sein würde, als es schien, weil Glas 5 vor Glas 4 überzulaufen beginnt. An diesem Punkt begann ich beschlossen, den Rekursionsweg zu beschreiten (nur zu Ihrer Information, viele Fragen zu Programmierinterviews erfordern eine Rekursion oder Induktion, um sie zu lösen).

Beim rekursiven Denken wird das Problem viel einfacher: Wie viel Wasser ist in Glas 8? Die Hälfte der Menge, die aus den Gläsern 4 und 5 verschüttet wurde (bis sie voll ist). Das bedeutet natürlich, dass wir beantworten müssen, wie viel aus den Gläsern 4 und 5 verschüttet wurde, aber es stellt sich heraus, dass das auch nicht allzu schwer ist. Wie viel ist aus Glas 5 verschüttet worden? Die Hälfte davon wurde jedoch aus den Gläsern 2 und 3 verschüttet, abzüglich des in Glas 5 verbleibenden Liters.

Wenn Sie dies vollständig (und unordentlich) lösen, erhalten Sie:

#include <iostream>
#include <cmath>
using namespace std;

double howMuchSpilledOutOf(int liters, int bucketId) {
    double spilledInto = 0.0;
    switch (bucketId) {
        case 1:
            spilledInto = liters; break;
        case 2:
            spilledInto = 0.5 * howMuchSpilledOutOf(liters, 1); break;
        case 3:
            spilledInto = 0.5 * howMuchSpilledOutOf(liters, 1); break;
        case 4:
            spilledInto = 0.5 * howMuchSpilledOutOf(liters, 2); break;
        case 5:
            spilledInto = 0.5 * howMuchSpilledOutOf(liters, 2) + 0.5 * howMuchSpilledOutOf(liters, 3); break;
        case 6:
            spilledInto = 0.5 * howMuchSpilledOutOf(liters, 3); break;
        default:
            cerr << "Invalid spill bucket ID " << bucketId << endl;
    }
    return max(0.0, spilledInto - 1.0);
}

double getWaterInBucket(int liters, int bucketId) {
    double contents = 0.0;
    switch (bucketId) {
        case 1:
            contents = liters; break;
        case 2:
            contents = 0.5 * howMuchSpilledOutOf(liters, 1); break;
        case 3:
            contents = 0.5 * howMuchSpilledOutOf(liters, 1); break;
        case 4:
            contents = 0.5 * howMuchSpilledOutOf(liters, 2); break;
        case 5:
            contents = 0.5 * howMuchSpilledOutOf(liters, 2) + 0.5 * howMuchSpilledOutOf(liters, 3); break;
        case 6:
            contents = 0.5 * howMuchSpilledOutOf(liters, 3); break;
        case 7:
            contents = 0.5 * howMuchSpilledOutOf(liters, 4); break;
        case 8:
            contents = 0.5 * howMuchSpilledOutOf(liters, 4) + 0.5 * howMuchSpilledOutOf(liters, 5); break;
        case 9:
            contents = 0.5 * howMuchSpilledOutOf(liters, 5) + 0.5 * howMuchSpilledOutOf(liters, 6); break;
        case 10:
            contents = 0.5 * howMuchSpilledOutOf(liters, 6); break;
        default:
            cerr << "Invalid contents bucket ID" << bucketId << endl;
    }
    return min(1.0, contents);
}

int main(int argc, char** argv)
{
    if (argc == 3) {
        int liters = atoi(argv[1]);
        int bucket = atoi(argv[2]);
        cout << getWaterInBucket(liters, bucket) << endl;
    }
    return 0;
}

An diesem Punkt (oder als ich dies schrieb) würde ich dem Interviewer sagen, dass dies nicht die ideale Lösung in der Produktion ist: Es gibt doppelten Code zwischen howMuchSpilledOutOf()und getWaterInBucket(); Es sollte einen zentralen Ort geben, an dem die Eimer ihren "Feedern" zugeordnet werden. In einem Interview, in dem Schnelligkeit und Genauigkeit der Implementierung wichtiger sind als Schnelligkeit der Ausführung und Wartbarkeit (sofern nicht anders angegeben), ist diese Lösung vorzuziehen. Dann würde ich anbieten, den Code umzugestalten, um näher an der Qualität zu sein, die ich für die Produktion halte, und den Interviewer entscheiden lassen.

Letzte Anmerkung: Ich bin sicher, dass mein Code irgendwo einen Tippfehler enthält. Ich würde das auch dem Interviewer gegenüber erwähnen und sagen, dass ich mich sicherer fühlen würde, wenn ich es entweder überarbeitet oder auf Unit-Tests getestet hätte.

Wenn man dies als ein Baumproblem betrachtet, ist es ein roter Hering, es ist wirklich eine gerichtete Grafik. Aber vergiss das alles.

Denken Sie an ein Glas irgendwo unter dem oberen. Darüber befinden sich ein oder zwei Gläser, die überlaufen können. Mit der richtigen Wahl des Koordinatensystems (keine Sorge, siehe Ende) können wir eine Funktion schreiben, um die "Eltern" -Brille für jedes gegebene Glas zu erhalten.

Nun können wir uns einen Algorithmus überlegen, mit dem die in ein Glas gegossene Flüssigkeitsmenge unabhängig vom Überlauf aus diesem Glas ermittelt werden kann. Die Antwort ist jedoch, dass jedem Elternteil viel Flüssigkeit eingefüllt wird, abzüglich der Menge, die in jedem Elternglas gespeichert ist, geteilt durch 2. Summieren Sie dies einfach für alle Eltern. Schreiben Sie dies als Python-Fragment des Körpers einer amount_poured_into () -Funktion:

# 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)

Mit max () soll sichergestellt werden, dass kein negativer Überlauf auftritt.

Wir sind fast fertig! Wir wählen ein Koordinatensystem mit 'y' auf der ganzen Seite, die erste Reihe ist 0, die zweite Reihe ist 1 usw. Die 'x'-Koordinaten haben eine Null unter der oberen Reihe und die zweite Reihe hat x-Koordinaten von -1 und +1, dritte Reihe -2, 0, +2 und so weiter. Der wichtige Punkt ist, dass das Glas ganz links oder ganz rechts in Stufe y abs (x) = y hat.

Wenn Sie das alles in Python (2.x) packen, haben wir:

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)

Verwenden Sie also amount_in (total, p), um die tatsächliche Menge in einem Glas bei p zu erhalten.

Es ist nicht von der OP klar, aber das Bit über „Sie Parameter hinzufügen kippen“ bedeuten kann , die ursprüngliche Frage in Bezug auf dem Glas beantwortet werden muss Zahlen gezeigt. Dies wird gelöst, indem eine Zuordnungsfunktion von den Showglasnummern in das oben verwendete interne Koordinatensystem geschrieben wird. Es ist fummelig, aber es kann entweder eine iterative oder eine mathematische Lösung verwendet werden. Eine leicht verständliche iterative Funktion:

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)

Schreiben Sie jetzt einfach die Funktion amount_in () um, um eine Glaszahl zu akzeptieren:

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)

Interessant.

Dies erfolgt nach dem Simulationsansatz.

private void test() {
  double litres = 6;
  for ( int i = 1; i < 19; i++ ) {
    System.out.println("Water in glass "+i+" = "+getWater(litres, i));
  }
}

private double getWater(double litres, int whichGlass) {
  // Don't need more glasses than that.
  /*
   * NB: My glasses are numbered from 0.
   */
  double[] glasses = new double[whichGlass];
  // Pour the water in.
  pour(litres, glasses, 0);
  // Pull out the glass amount.
  return glasses[whichGlass-1];
}

// Simple non-math calculator for which glass to overflow into.
// Each glass overflows into this one and the one after.
// Only covers up to 10 glasses (0 - 9).
int[] overflowsInto = 
{1, 
 3, 4, 
 6, 7, 8, 
 10, 11, 12, 13, 
 15, 16, 17, 18, 19};

private void pour(double litres, double[] glasses, int which) {
  // Don't care about later glasses.
  if ( which < glasses.length ) {
    // Pour up to 1 litre in this glass.
    glasses[which] += litres;
    // How much overflow.
    double overflow = glasses[which] - 1;
    if ( overflow > 0 ) {
      // Remove the overflow.
      glasses[which] -= overflow;
      // Split between two.
      pour(overflow / 2, glasses, overflowsInto[which]);
      pour(overflow / 2, glasses, overflowsInto[which]+1);
    }
  }
}

welche druckt (für 6 liter):

Water in glass 1 = 1.0
Water in glass 2 = 1.0
Water in glass 3 = 1.0
Water in glass 4 = 0.75
Water in glass 5 = 1.0
Water in glass 6 = 0.75
Water in glass 7 = 0.0
Water in glass 8 = 0.25
Water in glass 9 = 0.25
Water in glass 10 = 0.0
...

das scheint in etwa richtig zu sein.

Dies ist die Binomialfunktion. Das Verhältnis des Wassers zwischen den Gläsern der Stufe N kann mit nCr für jedes Glas in der Stufe ermittelt werden. Darüber hinaus ist die Gesamtzahl der Gläser vor der Stufe N die Summe von 1 bis (N - 1), eine Formel, für die Sie ziemlich leicht verfügbare finden sollten. Wenn X gegeben ist, sollten Sie in der Lage sein, den Füllstand zu bestimmen, und nCr verwenden, um die Verhältnisse der Gläser für diesen Füllstand zu überprüfen und so zu bestimmen, wie viel Wasser in X ist, wenn es genug Liter gibt, um trotzdem zu X zu gelangen.

Zweitens ist Ihre Idee, den BTree zu verwenden, in Ordnung. Der BTree ist lediglich eine interne Variable, kein externer Parameter.

IOW, wenn Sie diese Mathematik in Ihrer Ausbildung behandelt haben (hier in Großbritannien wird sie vor der Universität unterrichtet), sollten Sie in der Lage sein, dies ohne zu große Probleme zu lösen.