2024 - Adventskalender der Fakultät für Informatik
Die Zeit bis Heiligabend wird immer knapper, und jetzt haben die Such- und Sortier-Wichtel eine Erkältung bekommen, und fallen wahrscheinlich bis Weihnachten aus :(
Santa muss sich wohl oder übel selbst darum kümmern, dass die Geschenke später auf dem Schlitten schnell greifbar sind. Er geht in das Geschenkelager und sieht beim Ausgang der Geschenkemaschine folgende Anordnung (jedes Geschenk ist mit einer eindeutigen Zahl gekennzeichnet):
| Stapel 1 | Stapel 2 | Stapel 3 | Stapel 4 | Stapel 5 | Stapel 6 |
|---|---|---|---|---|---|
| 2345496786594 | 4569343253322 | 2333249845232 | 2323455523842 | 2348234658403 | 2349234038572 |
| 2345934503458 | 4954234952423 | 2349655668432 | 2304234023492 | 2340234757234 |
Um welchen Sortieralgorithmus handelt es sich? Was passiert mit 2345934502347? Ist das eine gute Idee bei 1 Milliarde Geschenken?
Die Such- und Sortier-Wichtel verwenden eine Hashtabelle. Die Hashfunktion ist "mod 13", und die Hashwerte sind:
| 0 | 3 | 7 | 11 | 10 | 5 |
|---|---|---|---|---|---|
| 2345496786594 | 4569343253322 | 2333249845232 | 2323455523842 | 2348234658403 | 2349234038572 |
| 2345934503458 | 4954234952423 | 2349655668432 | 2304234023492 | 2340234757234 |
Das Geschenk 2345934502347 wird in auf den Stapel "7" gelegt.
In echt wäre natürlich mod 13 viel zu klein, da dann viel zu viele Geschenke in jedem Stapel linear zu durchsuchen wären. Selbst mit "mod 31622" wäre man bei im Mittel 31623 Geschenken pro Stapel. Dann könnte man diese nochmals sortieren...