Nederlands
Menu

Datastructuren en algoritmen

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?

  1. A6
  2. B9
  3. C15
Antwoord en toelichting tonen

Antwoord: C. 15

Stel dat C(n) het aantal aanroepen voor fib(n) is. Dan geldt C(0) = C(1) = 1 en C(n) = 1 + C(n−1) + C(n−2), dus C(2) = 3, C(3) = 5, C(4) = 9 en C(5) = 15. Omdat dezelfde waarden steeds opnieuw worden berekend, groeit het aantal exponentieel met n; fib(30) doet ongeveer 2,69 miljoen aanroepen. Met memoisatie (een vorm van dynamisch programmeren), die berekende waarden in een tabel bewaart, worden alleen de zes waarden fib(0) tot fib(5) berekend en daalt het aantal aanroepen tot 9 (2n − 1). 6 is het aantal verschillende argumenten, en 9 het aantal aanroepen met memoisatie.

Dit onderwerp oefenen Naar de onderwerppagina

Meer vragen over Datastructuren en algoritmen

  1. 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?
  2. 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?
  3. Welke eigenschap van het Boyer-Moore-algoritme om een patroon in een tekenreeks te vinden is juist?
  4. 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?
  5. Wat is de meest passende reden dat open adressering met lineair proberen bij een hashtabel met veel elementen en een bezettingsgraad van ongeveer 0,5 vaak sneller is dan chaining (elementen koppelen met gelinkte lijsten)?