Grundlagen der Programmierung (Pseudocode nachverfolgen)

÷ ist die Division; wird das Ergebnis einer ganzzahligen Variablen (auch einem Funktionsargument) zugewiesen, wird der Nachkommaanteil abgeschnitten. Wie oft wird pow einschließlich des ersten Aufrufs aufgerufen, wenn die folgende Funktion pow als pow(2, 10) aufgerufen wird?

○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

Antwort und Erläuterung anzeigen

Antwort: A. 5

pow(x, n) berechnet x hoch n, indem das Ergebnis von pow(x, n ÷ 2) mit halbiertem n quadriert wird (bei ungeradem n wird zusätzlich einmal mit x multipliziert). n ändert sich zu 10, 5, 2, 1 und 0, und bei n = 0 endet die Rekursion; pow wird also 5-mal aufgerufen. Der Rückgabewert ist 2¹⁰ = 1024. Würde n wie bei x × pow(x, n − 1) jeweils um 1 verringert, gäbe es 11 Aufrufe, von n = 10 bis 0. Durch das Halbieren von n wächst die Zahl der Aufrufe ungefähr proportional zu log₂ n.

÷ ist die Division; wird das Ergebnis einer ganzzahligen Variablen (auch einem Funktionsargument) zugewiesen, wird der Nachkommaanteil abgeschnitten. Wie oft wird pow einschließlich des ersten Aufrufs aufgerufen, wenn die folgende Funktion pow als pow(2, 10) aufgerufen wird?

Weitere Fragen zu Grundlagen der Programmierung (Pseudocode nachverfolgen)