Bitte helft uns mit diesem Informatik - Rätsel
Es gibt eine Gruppe an n Leuten (n>=2), diese kommen immer in einen Raum mit abzählbar unendlichen Schubladen (nummeriert) und unendlich vielen Steinen. Die Person, welche in den Raum kommt weiß nicht die wie vielte Person sie ist, kann aber nun beliebig viele Steine herausnehmen oder hineinlegen. Es passt aber immer nur ein Stein in eine Schublade! Das Team kann vorher eine Strategie besprechen, aber nicht eine Reihenfolge.
Eine Lösung zu finden ist einfach, das Problem ist aber, dass wir eine Lösung mit der Laufzeit O(n*log(n)) finden sollen. Es muss also sehr effizient sein.
Wenn ihr dieses Rätsel schon irgendwo gehört habt oder eine gute Lösung habt, dann helft uns bitte!
2 Antworten
Ohne die Antwort zu kennen würde ich empfehlen das hier durchzulesen. https://de.m.wikipedia.org/wiki/Quicksort der quicksort hat die selbe komplexitätsklasse und lässt sich ggf. auf das Problem adaptieren
Was ist überhaupt das Ziel? Wieso sollte auch nur einer da rein gehen und irgendwo einen Stein heraus nehmen oder rein legen?
Meine Idee wäre es, binär hochzuzählen. Stein = 1, kein Stein = 0
K. A., ob es noch besser geht.
Am Ende soll der Letzte wissen dass er die letzte Person ist - sorry vergessen