Nederlands
Menu

Wat is Modulo-operatie?

Een bewerking die de rest van een deling geeft, in de pseudotaal geschreven als mod en in veel talen als %. x mod 10 geeft het eenhedencijfer, x mod 2 geeft aan of x even of oneven is, en i mod n + 1 geeft een index die rondgaat langs 1 tot en met n. Het teken van de rest bij negatieve getallen verschilt per taal.

Japanse benaming: 剰余演算

“Modulo-operatie” komt voor in 9 oefenvragen uit 4 onderwerpen, bijv. Basis van programmeren (pseudocode traceren), Datastructuren en algoritmen, Computerarithmetiek.

Vakgebied: Basis van programmeren (pseudocode traceren)

Nu oefenen: vragen over Modulo-operatie

De sleutels 10, 17, 24 en 3 worden in deze volgorde opgeslagen in een hashtabel van grootte 7 (posities 0 tot 6) met de hashfunctie h(k) = k mod 7. Botsingen worden opgelost met lineair proberen (linear probing): de positie schuift telkens één plaats op (na 6 komt 0) tot er een vrije plaats is gevonden. Op welke positie wordt sleutel 3 opgeslagen?

  1. APositie 3
  2. BPositie 4
  3. CPositie 6
Antwoord en toelichting tonen

Antwoord: C. Positie 6

Alle vier de sleutels geven bij deling door 7 de rest 3, dus elk probeert eerst positie 3. Sleutel 10 komt op positie 3; 17 vindt positie 3 bezet en komt op positie 4; 24 vindt posities 3 en 4 bezet en komt op positie 5. Sleutel 3 vindt posities 3, 4 en 5 bezet en wordt op positie 6 opgeslagen. Zoals dit laat zien, gaan bij lineair proberen bezette posities aaneengesloten blokken vormen (clustering), zodat later aankomende sleutels meer pogingen nodig hebben.

Een functie f(x, y) is gedefinieerd als „als y gelijk is aan 0, geef x terug; geef anders f(y, x mod y) terug”. Wat is de teruggegeven waarde van f(84, 36), en hoe vaak wordt f aangeroepen, de eerste aanroep meegerekend?

  1. AGeeft 12 terug; 3 keer aangeroepen
  2. BGeeft 12 terug; 4 keer aangeroepen
  3. CGeeft 6 terug; 3 keer aangeroepen
Antwoord en toelichting tonen

Antwoord: A. Geeft 12 terug; 3 keer aangeroepen

f(84, 36) roept f(36, 12) aan, omdat 84 mod 36 = 12; die roept f(12, 0) aan, omdat 36 mod 12 = 0; en omdat y gelijk is aan 0, wordt 12 teruggegeven. De aanroepen zijn f(84, 36), f(36, 12) en f(12, 0), in totaal drie; dit is het algoritme van Euclides voor de grootste gemene deler. Omdat de functie het resultaat van haar recursieve aanroep direct teruggeeft (staartrecursie), kan een compiler met tail-call-optimalisatie haar omzetten in een lus, zodat ze geen ruimte op de stack blijft gebruiken, hoe diep de recursie ook gaat.

“Modulo-operatie” in de toelichting

Vragen met “Modulo-operatie” (9)

  1. De sleutels 10, 17, 24 en 3 worden in deze volgorde opgeslagen in een hashtabel van grootte 7 (posities 0 tot 6) met de hashfunctie h(k) = k mod 7. Botsingen worden opgelost met lineair proberen (linear probing): de positie schuift telkens één plaats op (na 6 komt 0) tot er een vrije plaats is gevonden. Op welke positie wordt sleutel 3 opgeslagen?
  2. Een functie f(x, y) is gedefinieerd als „als y gelijk is aan 0, geef x terug; geef anders f(y, x mod y) terug”. Wat is de teruggegeven waarde van f(84, 36), en hoe vaak wordt f aangeroepen, de eerste aanroep meegerekend?
  3. Een wachtrij gebruikt de array q (4 elementen van het type string) als ring. head en tail beginnen bij 1. enq(v) voert q[tail] ← v uit en daarna tail ← tail mod 4 + 1; deq() geeft de waarde van q[head] terug en voert daarna head ← head mod 4 + 1 uit. In welk element van q wordt „E” opgeslagen als het volgende programma wordt uitgevoerd?
  4. Wat is in C het resultaat van het aftrekken van 1 van 0 bij een niet-ondertekend 32-bits geheel getal (unsigned int)?
  5. In een cache met regelgrootte 64 byte en 64 sets: welk setnummer krijgt het adres 0x1234?
  6. ÷ staat voor deling; bij toekenning aan een variabele van het type integer (ook een argument) worden de cijfers achter de komma weggelaten. Wat is de retourwaarde als de volgende functie f wordt aangeroepen als f(9087)?
  7. ÷ staat voor deling; bij toekenning aan een variabele van het type integer (ook een argument) worden de cijfers achter de komma weggelaten. Wat is de retourwaarde als de volgende functie toBin wordt aangeroepen als toBin(12)?
  8. Het volgende programma trekt de twee gehele getallen a en b van elkaar af tot ze gelijk zijn. Wat is de waarde van k nadat het is uitgevoerd?
  9. De volgende functie isLeap geeft true terug als het jaar y een schrikkeljaar is. and wordt vóór or geëvalueerd. Voor welke y geeft isLeap(y) true terug?

Verwante termen

Variabele Argument Retourwaarde (return value) Hashtabel (hash table) Hashfunctie Recursie Stack (stapelgeheugen) Wachtrij (queue) Array Gehele deling (integer division)

Naar de woordenlijst