Das lernst du heute
- Lineare Suche
- Minimum und Maximum
- Früh abbrechen
Das Lager hat eine Inventartabelle im Stack: welcher Barren, wie viele. Jemand fragt nach Stahl. Der Chip muss die Zeile finden – und am besten nicht alle Einträge lesen, wenn Stahl schon an vierter Stelle steht.
Tabelle mit Paaren
Jeder Eintrag hat zwei Werte. Du legst sie hintereinander ab: Hash auf Adresse 2i, Menge auf 2i + 1. Die Adresse rechnest du mit sll adr i 1 aus – einmal nach links schieben ist mal 2, aus der Bitwoche.
| i | Adresse | Inhalt |
|---|---|---|
| 0 | 0, 1 | Eisen, 40 |
| 1 | 2, 3 | Kupfer, 45 |
| 2 | 4, 5 | Gold, 8 |
| 3 | 6, 7 | Stahl, 120 |
Lineare Suche
Die einfachste Suche geht die Einträge der Reihe nach durch und vergleicht. Hashes sind ganze Zahlen, beq ist hier also sicher:
move fund -1
move i 0
suche:
sll adr i 1 # Adresse = 2 · i
get wert db adr
beq wert ziel gefunden # früh abbrechen
add i i 1
blt i ANZAHL sucheFrüh abbrechen
Sobald der Eintrag gefunden ist, springt der Chip aus der Schleife. Steht Stahl an vierter Stelle, liest er vier Einträge statt sechs. Bei einer Tabelle mit 100 Einträgen spart das im Mittel die Hälfte. Wird nichts gefunden, läuft die Schleife bis zum Ende, und fund bleibt −1.
−1 als „nicht gefunden“ funktioniert nur, wenn −1 keine echte Menge sein kann. Bei Werten, die negativ werden dürfen, nimm einen eigenen Merker, etwa ein zweites Register mit 0 oder 1.
Minimum und Maximum
Für das Minimum reicht min. Für das Maximum willst du zusätzlich wissen, welcher Eintrag es ist – das kann max nicht. Also vergleichst du selbst und merkst dir Wert und Position:
bge maxw wert weiter # nicht größer: überspringen
move maxw wert
move maxi i
weiter:Die Startwerte pinf und ninf sorgen dafür, dass der erste echte Eintrag immer gewinnt.
Suchen und Minimum/Maximum brauchen einen Durchlauf, also n Vergleiche. Sortieren bräuchte n · (n − 1) / 2. Für „wovon haben wir am meisten?“ ist die Suche immer die bessere Wahl.
Schaubild
Übung
Aufgabe
Die Inventartabelle liegt schon im Stack (Paare aus Hash und Menge). In ziel (r0) steht ein gesuchter Hash. Schreibe:
fund= Menge des gesuchten Eintrags, −1 wenn er fehlt; brich die Suche ab, sobald er gefunden istmaxi= Nummer i des Eintrags mit der größten Mengeminw= kleinste Menge
Hinweise
Hinweis 1
Adresse des Hashes: sll adr i 1, die Menge liegt eins dahinter.
Hinweis 2
Gefunden: aus der Schleife springen, add adr adr 1, get fund db adr.
Hinweis 3
Maximum mit Position: bge maxw wert weiter, sonst move maxw wert und move maxi i.
Quiz
3 Fragen. Ab 60 % ist das Quiz bestanden – die Auswertung macht der Server.
Tag abschließen
- Übung im Simulator bestanden
- Quiz mit mindestens 60 % bestanden
Ohne Konto wird der Fortschritt nur in diesem Browser gespeichert.
Fehler in dieser Lektion melden
Zum Melden bitte anmelden. Anmelden