Aufgabe 4: Rekursion Assignment

Die Potenz einer reellen Zahl mit einem Exponenten aus den natürlichen Zahlen N0 :={0,1,2,...} kann man wie folgt definieren: 
      Sei x ∈ R, n ∈ N0, dann gilt xn = 1 für n = 0, x · xn-1 sonst

1. Schreiben Sie eine rekursive Funktion power(x, n), die die Potenz einer Zahl x mit einer natürlichen Zahl n im Exponenten zurückgibt, also xn mit Hilfe dieser Definition rekursiv berechnet.

2. Das Vorgehen in Aufgabenteil 1 ist nicht sonderlich effizient und wir werden nun einen effizienteren Algorithmus kennenlernen: Hierfür stellen wir den Exponenten n in seiner Binärdarstellung dar: 
      n = ∑i=0m   ai·2i, ai ∈ {0,1}
Ist Ihnen das Binärsystem nicht bekannt, finden Sie hier eine kleine Einführung: https://de.wikipedia.org/wiki/Dualsystem.
Nun gehen wir die ai dieser Darstellung von am−1 zu kleinen i sukzessive durch und quadrieren unsere Zahl und multiplizieren mit x (QM) jeweils, wenn wir eine 1 treffen und quadrieren (Q), wenn wir eine 0 in der Darstellung haben. Ein Beispiel: 
       23 = 1·24 +0·23 +1·22 +1·21 +1·20 =10111b 
          => x23 = QM(QM(QM(Q(x)))) = (((x2)2 · x)2 · x)2 · x

Scaffold Head

import sys _print = print print = lambda msg, *args, **kwargs: _print('#'+str(msg), *args, **kwargs)

Scaffold Foot

nums = [eval(line) for line in sys.stdin][0] for x, n in nums: _print(int(power(x,n))) for x, n in nums: _print(int(bin_power(x,n)))

Start time:

Do 14 Dez 2017 14:00:50

End time:

Do 21 Dez 2017 23:00:34

General test timeout:

10.0 seconds

Tests

(2,3), (4,5), (10,3), (6,4), (5,5), (1,2), (10,0)

8
1024
1000
1296
3125
1
1
8
1024
1000
1296
3125
1
1