Nederlands
Menu

Datastructuren en algoritmen

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.

Dit onderwerp oefenen Naar de onderwerppagina

Meer vragen over Datastructuren en algoritmen

  1. Een functie fib(n) voor Fibonaccigetallen is met recursie gedefinieerd als „als n kleiner dan of gelijk aan 1 is, geef n terug; geef anders fib(n−1) + fib(n−2) terug”. Hoe vaak wordt fib aangeroepen als fib(5) wordt aangeroepen, de eerste aanroep meegerekend?
  2. Je betaalt 8 yen met munten van 1 yen, 4 yen en 6 yen. Welke uitspraak over het aantal munten dat een gretig algoritme kiest (dat eerst zoveel mogelijk van de grootste munt gebruikt), vergeleken met het minimale aantal munten, is juist?
  3. Een knapzak met capaciteit 8 wordt gevuld met voorwerpen gekozen uit vier voorwerpen met (gewicht, waarde) (2, 3), (3, 4), (4, 5) en (5, 6). Van elk voorwerp is er maar één, en voorwerpen kunnen niet worden gesplitst. Wat is de maximale totale waarde bij een totaal gewicht van hoogstens 8?
  4. Welke eigenschap van het Boyer-Moore-algoritme om een patroon in een tekenreeks te vinden is juist?
  5. Een dynamische array reserveert, als er een element wordt toegevoegd terwijl hij vol is, een nieuw gebied met de dubbele capaciteit en kopieert alle elementen daarheen. Hoeveel elementkopieën worden er in totaal gemaakt als 1000 elementen één voor één worden toegevoegd aan een lege array met capaciteit 1?