001    package de.hska.info1.klausur.ws07;
002    
003    
004    /**
005     * Lösungsvorschläge zu Aufgabe 4.
006     * Teil a)
007     * <pre>
008     * 9 7 2 5 3 2 1 4
009     * 7 9
010     *     2 5
011     * 2 5 7 9
012     *         2 3
013     *             1 4
014     *         1 2 3 4
015     * 1 2 2 3 4 5 7 9
016     * </pre>
017     * Richtige Reihenfolge der Unterteilungsschritte beachten.
018     * <p>
019     * Teil b)
020     * O(n)
021     * </p>
022     * 
023     * <p>
024     * Teil d) O(log n) (Rekursionstiefe, Verbrauch Laufzeitkeller)
025     * </p>
026     * @author Christian Pape
027     */
028    public class Aufgabe4 {
029    
030            public double potenzBerechnen(double a, int n) {
031                    double potenz = 1;
032    
033                    if (n > 0) {
034                            potenz = potenzBerechnen(a, n / 2);                     
035                            potenz *= potenz;
036                            if (n % 2  == 1) {
037                                    potenz *= a;
038                            }
039                    }
040                    
041                    return potenz;  
042            }
043            
044            /**
045             * Weiter Variante (Lösunge eines Studenten in der Klausur)
046             * Nutzt aus, dass für gerade n folgende gilt:
047             * <center>
048             *   a<sup>n</sup> = (a<sup>2</sup>)<sup>n/2</sup>
049             * </center>
050             */
051            public double potenzBerechnenVariante(double a, int n) {
052                    double potenz = 1;
053    
054                    if (n > 0) {
055                            potenz = potenzBerechnenVariante(a * a, n / 2);                 
056                            if (n % 2  == 1) {
057                                    potenz *= a;
058                            }
059                    }
060                    
061                    return potenz;  
062            }
063    }