Basis van programmeren (pseudocode traceren)

÷ staat voor deling; bij toekenning aan een variabele van het type integer (ook een argument) worden de cijfers achter de komma weggelaten. Hoe vaak wordt pow aangeroepen, de eerste aanroep meegerekend, als de volgende functie pow wordt aangeroepen als pow(2, 10)?

○integer: pow(integer: x, integer: n)
  if (n = 0)
    return 1
  endif
  integer: h ← pow(x, n ÷ 2)
  if (n mod 2 = 0)
    return h × h
  endif
  return h × h × x

Antwoord en toelichting tonen

Antwoord: A. 5

pow(x, n) berekent x tot de macht n door het resultaat van pow(x, n ÷ 2), met n gehalveerd, te kwadrateren (en nog eens met x te vermenigvuldigen als n oneven is). n wordt achtereenvolgens 10, 5, 2, 1 en 0, en de recursie stopt bij n = 0, dus pow wordt 5 keer aangeroepen. De retourwaarde is 2¹⁰ = 1024. Wie n telkens met 1 verlaagt, zoals in x × pow(x, n − 1), krijgt 11 aanroepen, van n = 10 tot 0. Door n te halveren groeit het aantal aanroepen ruwweg evenredig met log₂ n.

÷ staat voor deling; bij toekenning aan een variabele van het type integer (ook een argument) worden de cijfers achter de komma weggelaten. Hoe vaak wordt pow aangeroepen, de eerste aanroep meegerekend, als de volgende functie pow wordt aangeroepen als pow(2, 10)?

Meer vragen over Basis van programmeren (pseudocode traceren)