Raupen und Blätter. Können wir tun, besser als O(n*c)?

Fand diese Frage während der Vorbereitung für die interviews.

Nehme an, dass einige Raupen von unten anfangen und Sprung zum nächsten Blatt. Sie
Essen Sie das Blatt vor dem Sprung zum nächsten. Wir bekommen ein array repräsentiert springen Schritte
gemacht von Raupen. Wenn das array [2,4,7], es bedeutet, caterpillar[0] Essen Blatt-2,4,6..
caterpillar[1] fressen Blatt-4,8,12.. und caterpillar[2] Essen 7,14,21...0 stellt Boden.
Berechnen Sie die Anzahl der übrig lässt.

Lassen Sie uns davon ausgehen, dass die Raupe springt zum nächsten Ziel, wenn das aktuelle Blatt ist gegessen. Dies bedeutet, dass bei caterpillar[7] findet, dass Blatt 28 wird gegessen, es wird gehen, um zu Essen, Blatt 35.

Sei c die Anzahl der Raupen und n die Anzahl der Blätter.

Des offensichtlichen brute-force-Lösung ist die Iteration über ein bool-array der Größe n für jede Raupe und markieren Sie es als wahr, wenn gegessen oder sonst false. Es dauert O(n*c) Zeit. Können wir besser machen?

Jedes Blatt, deren Anzahl nicht ein Vielfaches von jeder der zahlen in der gegebenen array bleibt übrig.
Sie möchten möglicherweise verwenden Sie das Einschluss-Ausschluss-Prinzip
Ja, ich verstehe, dass das problem reduziert sich auf die Aussage, die Sie soeben gegeben. Dann ist die Frage, konvertiert zu was ist der beste Weg zu finden, zahlen, die kein Vielfaches von jedem die Nummer.

InformationsquelleAutor Hoxeni | 2014-12-02

algorithm math

12

Einer Raupe frisst alle mehrere seiner "jump-step"j, so, wenn Sie allein waren, jede Raupe Essen würde floor(n/j) Blätter.

Nun haben Sie, um herauszufinden, welche Blätter Sie haben mehrfach gerechnet werden. Zum Beispiel, wenn Sie zählen alle Blätter, die sind teilbar durch 2 für die erste Raupe, dann brauchen Sie sich nicht zu zählen, die Blätter für die zweite Raupe, die Sprünge 4, die von 4.

Für zwei Elemente, sind diese zahlen doppelt gezählt werden, die ein Vielfaches der least common multiple der beiden Elemente, und es gibt floor(n/lcm(j,j')) von denen.

Beachten Sie, dass für die drei Bedingungen, wenn Sie diese Berechnung, Sie könnten entfernen Sie einige Elemente doppelt : laßt uns die 28 in deinem Beispiel. Es wird gegessen werden durch die Raupe mit jump step 7, sondern zählte für die beiden anderen (da 28 % 4 == 28 % 2 == 0), so müssen Sie die Multiplikatoren, die entfernt wurden mehrmals : floor(n/lcm(j,j',j"))

Sehen Sie hier ein Muster, es ist die Einschluss-Ausschluss-Prinzip. Die Allgemeine Formel folgt :

Lassen Aj werden die Blätter gegessen, die von einem caterpillar-springen mit Schritt j (wenn Sie allein waren). Dann ist für J ein Satz von mehreren capterpillar springen-sets, A_J ist die Menge der Blätter gegessen werden, die durch alle diese Raupen.

Lassen Sie uns definieren Sie auch das kleinste gemeinsame Vielfache von a als kleinste gemeinsame Vielfache aller Elemente in der Menge, so können wir schreiben lcm(J).

Den [n] in der Einschluss-Ausschluss-Formel ist der Satz, der als Raupe springt, also in deinem Fall [2,4,7], und wir iterieren über alle Teilmengen davon. |J| ist die Größe der Teilmenge, und |A_J| ist die Größe von der Anzahl der Blätter, die jede Raupe in J Essen konnte, also erhalten wir |A_J| = floor(n/lcm(J)).

Haben Sie jetzt eine Summe von 2^c - Bezug *, denn das ist die Anzahl von Teilmengen der c Raupen. Beachten Sie, dass Sie können sparen Sie einige Zeit durch die Einsparung der kleinste gemeinsame Vielfache statt recomputing Sie von Grund auf.

Lasse ich das eigentliche schreiben von code "wie-übung", wie manche sagen : es ist im Grunde der Iteration über Teilmengen und computing least common multiple, dann setzen Sie alle zusammen in die oben genannte Summe.

Dies wird Ihnen die Gesamtzahl der Blätter gegessen. Immer die uneaten diejenigen von hier aus ist trivial.

Wenn wir es auf ein kleines Beispiel (kann es nicht überprüfen), mit 0 dem Boden 1..24 die Blätter, und [2,3,4] die Raupe springen Schritte.

Die einzigen erhaltenen Blätter werden {1, 5, 7, 11, 13, 17, 19, 23} : entfernen Sie alle geraden zahlen und alle zahlen teilbar durch 3. Das heißt, wir erwarten die Antwort zu 8.
- Erste Runde : Teilmengen der Größe 1.
  - Caterpillar j=2 würde, allein, Essen 24/2 = 12 Blätter
  - Caterpillar j=3 würde, allein, Essen 24/3 = 8 Blätter
  - Caterpillar j=4 würde, allein, Essen 24/4 = 6 Blätter
- Zweite Runde : Teilmengen der Größe 2.
  - Caterpillar j=2 und j=3 würde beide gerne Essen 24/6 = 4 Blätter : {6, 12, 18, 24}
  - Caterpillar j=3 und j=4 würde beide gerne Essen 24/12 = 2 Blätter : {12, 24}
  - Caterpillar j=4 und j=2 würde beide gerne Essen 24/4 = 6 Blätter : alle diejenigen, die gegessen von 4 sind im Visier 2
- Dritte Runde : Teilmengen der Größe 3 : alle Raupen zusammen
  - Sie alle gerne Essen, 24/lcm(2,3,4) = 24/12 = 2 Blätter : {12, 24}.
- Letzte Runde : 12 + 8 + 6 - 4 - 2 - 6 + 2 = 26 - 12 + 2 = 16 Blätter werden gegessen
Also 24 - 16 = 8 Blätter bleiben.

* das ist natürlich ein worst-case-Szenario. Hoffentlich wird das Durchlaufen von Teilmengen von Zunehmender Größe, und sobald das kleinste gemeinsame Vielfache von a Teilmenge J ist größer als n können Sie ignorieren alle Obermengen von J. insbesondere, wenn alle Teilmengen der Größe k haben ein lcm größer als n ist, können Sie aufhören zu iterieren.
- Danke. Von Ihnen positiv bewertet werden. Das scheint eine gute Lösung für kleine Werte von c, so dass n*c > 2^c. Allerdings lasse ich die Frage offen, um zu sehen, ob es gibt andere Lösungen, die nicht exponentiell in c.
- O(2^c) ist nicht so schlimm, wie es klingt. Wenn n groß ist (n>O(2^c)), O(2^c) besser als O(n); wenn n klein ist, wird die Fußnote auf die Antwort garantiert Komplexität O(n) (tatsächlich, ich vermute, sogar noch besser, aber ich bin mir nicht sicher). Also, in jedem Fall ist dieser Algorithmus schneller als O(n*c).
InformationsquelleAutor Cimbali
3

Dies ist in Bezug auf O(n*c) algo, die Sie erwähnt. Es ist O(n logc) wenn man genau hinschaut.

Einer Raupe frisst alle mehrere seiner "jump-step" j, so, wenn Sie allein waren, jede Raupe Essen würden, floor(n/j) Blättern.

Diese Komplexität begrenzt ist durch:
n+n/2+n/3+...+n/c <= n log(c)

Es wird nicht einen Unterschied machen wie c ist klein, aber nur darauf hin 🙂

Überprüfen Sie diesen link für die Umsetzung der Einschluss-Ausschluss von Cimbali: Abbildung aus Gefressenes Blätter Algorithmus bug

EDIT: Hier ist der Beweis, dass die harmonische Reihe ist begrenzt durch log(c). Wir verwenden die Ungleichheit für die untere Grenze der integration.
- Was ist c in Ihre Gleichung? n + n/2 + ... + n/c ist glich n(1 + 1/2 + ... + 1/c) und 1 + 1/2 + ... + 1/c ist die harmonische Reihe, diese Reihe ist divergent Reihe und existiert nicht eine Grenze Harmonic series. Bitte geben Sie einen Nachweis für die abgeleitete Formel.
- c steht für die Anzahl von Schritten oder die Anzahl der Raupen, die wie erwähnt in der ques. Ich habe ein edit zu erwähnen, der Beweis der Formel.
InformationsquelleAutor Kartik Raj
0

Dies ist nur eine Optimierung über den vorgeschlagenen Ansatz von @cimbali ist. Aus dem array mit den Schritten für caterpillar. Sie können entfernen Sie die vielfachen der stride-Wert aus diesem array zu reduzieren, die Anzahl der Kombinationen gefunden.

Z.B. 24 Blätter, und [2,3,4] die Raupe springen Schritte.
- Ersten Schritt:
  Gehen Sie durch die Schritte-Arrays und entfernen ein Vielfaches von 2. Da die 4 ist ein Vielfaches von 2. Entfernen Sie die 4 aus dem array
- Zweiter Schritt : die Teilmengen der Größe 1.
  Caterpillar j=2 wäre, allein, Essen 24/2 = 12 Blätter
  Caterpillar j=3 wäre, allein, Essen 24/3 = 8 Blätter
- Dritter Schritt : Teilmengen der Größe 2.
  Caterpillar j=2 und j=3 würde die beiden gerne Essen, 24/6 = 4 Blätter : {6, 12, 18, 24}
So 24 - 16 (12+8-4) = 8 bleiben die Blätter.

InformationsquelleAutor Mudits
0

Kann die Komplexität nicht von O(N) oder auch O(N/K). Mein Algorithmus ist O(2^K), die die riesigen, in sich selbst aber noch akzeptabel. Auch wenn ich den pass N = Lang.MAX_VALUE, bekomme ich sofort die Ergebnisse. Obwohl, wenn K größer ist, kann der code die Zeit nehmen, oder den code brechen kann, wenn LCM von springen alle Werte übersteigt Lang.MAX_VALUE.

Es zu erklären, nehmen wir A = {4, 5, 6} und N = 20.

Können wir zählen gefressenes Blätter sind {1, 2, 3, 7, 9, 11, 13, 14, 17, 19} = 10

Wie können wir dieses Ergebnis ohne zu zählen?
N - (N /4) - (N /5) - (N /6) + (N /20) + (N /12) + (N /30) - N /60
= 20 - 5 - 4 - 3 + 1 + 1 + 0 - 0 = 20 - 12 + 2 = 10

Caterpillar Gefressenes Blätter Problem

InformationsquelleAutor Deepak

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.