N-th Power



  • Darf man std::pow verwenden? ... das erscheint mir etwas komisch. Ich kenne die Seite nicht, aber meistens geht es doch darum den Algo zu schreiben und nicht einen fertigen zu nehmen und mehr oder weniger in ne wrapper Methode zu stecken (Das if kann ja hier nicht Herausforderug gewesen sein?)



  • Habe ich mich auch gefragt. Ebenso, ob man vector nehmen darf und ob dieser sortiert sein muss. Die Aufgabe (unter anderen Aufgaben) lautete genau so:

    This Week's Featured Kata
    =========================
    
     
    
    ###[N-th Power](http://r.news.codewars.com/mk/cl/f/-cZPNffmIzuFjmlTsDbfmYI90kjlr0sQSOGX1jzt0T875RkiC04Wdy9wJtZ1t59sZgl8r9CyTeAsNiXyB-dKfo0DwiozNQe7pVUBVEVtcZgXaKkSQcc98LDv_xpSnkdTPlYI10zmKV0tHCg_Lmq41f4WZCMwNVZb81yq43ncKGgQSwfePVxrbAS2Lr_yx7f-TCWuaM-m9cRs9wYUiao6DpX_T8KYAoynxVc3zESvFQjY6XGORw)
    
    This kata is from check py.checkio.org
    
    You are given an array with positive numbers and a non-negative number N. You should find the N-th power of the element in the array with the index N. If N is outside of the array, then return -1. Don't forget that the first element has the index 0.
    
    Let's look at a few examples:
    
    
    - array = [1, 2, 3, 4] and N = 2, then the result is 3^2 == 9; 
    - array = [1, 2, 3] and N = 3, but N is outside of the array, so the result is -1.
    
    [Milford](http://r.news.codewars.com/mk/cl/f/7OtVBuVB5IBhgWIXl4NnGe2yBydjqHhO-Wr70DX9_z5y1j7spWyEuQX1sSdiLsY4Z-dfWCBSH7R1VMbQdVkUWztKqi00z77oK8UPxAUjpXBXgSjtLqm8_sCBqW1MquVsnrOFIfptbWyiiaISvxEakwEucBh68-0Ra8HEtrzGWHgNw7_l0ofN0F7MAHIONyeGPI13hHNsg0XtvDEPax7_MvMUOGbl)
    
    

    Deshalb wußte ich auch sofort, das ich sowas ohne groß nachzudenken kann. Ich glaube, die größte Herausforderung ist, zwischen positiven und nicht-negativen Werten zu unterscheiden? Wegen 0 und so?



  • @zeropage sagte in N-th Power:

    Letzendes kannst du es ja intepretieren wie du willst. Aber ich würde fast wetten, dass man pow selbst schreiben sollte. Einen Vektor zu verwenden wird schon in Ordnung sein. Ist ja auch gar keine C++ Aufgabe original.



  • Ja, die Aufgabe ist für alle möglichen Sprachen gemeint.

    In diesem Fall ist ein eigenes pow auch keine große Sache. Finde ich aber gut, wenn es auch mal so einfache Aufgaben gibt.



  • Das pow würde ich dann so machen:

    int nPow(unsigned int v, const std::size_t N)
    {
    	int result = 1;
    	for (std::size_t i = 0; i < N; ++i)
    		result *= v;
    
    	return result;
    }
    


  • Einen unsigned int als Basis, einen size_t als Exponenten und dann einen int zurückgeben passt imho nicht.

    Wie die einzelnen Werte gespeichert sind (std::vector, std::array, std::deque oder C-Array) sollte egal sein, daher würde ich bei getNthPower auch zwei Iteratoren oder einen Zeiger und die Anzahl entgegennehmen.



  • Kannst Du ein Beispiel geben? Ich habe das extra so gemacht, das es oben passt.

    int getNthPower(const std::vector<unsigned int>& vec, const std::size_t N)
    {
    	if (N >= vec.size())
    		return -1;
    	else
    		return (int)std::pow(vec[N], N); //oder
                    return nPow(vec[N], N);
    }
    


  • @yahendrik sagte in N-th Power:

    daher würde ich bei getNthPower auch zwei Iteratoren oder einen Zeiger und die Anzahl entgegennehmen.

    Ups, jetzt erst gesehen.

    Jopp, nur wär dann die Aufgabe nicht mehr so einfach gewesen und ich wäre erst gar nicht drauf aufmerksam geworden. Außerdem hätte mir man das in die Aufgabe reinschreiben sollen, damit ich es so mache.

    Aber gut, es stand auch nicht drin, mach es so einfach wie möglich.



  • @zeropage Nein, das war mein Fehler, es war nicht eindeutig und daher habe ich es editiert.



  • Davor hatte ich mir überlegt, ob ich dann überall gleichintnehmen sollte, aber spätestens beim Vergleich N mit vec.size() hätte es die erste Warnung gegeben.

    Außerdem hatte ich geglaubt, die Anforderung bei dieser Aufgabe wäre es, positive und nicht-negative Zahlen abzubilden.



  • @zeropage sagte in N-th Power:

    Das pow würde ich dann so machen:

    int nPow(unsigned int v, const std::size_t N)
    {
    	int result = 1;
    	for (std::size_t i = 0; i < N; ++i)
    		result *= v;
    
    	return result;
    }
    

    Wenn du Wert auf Code mit Sahnehäubchen legst, dann könntest du hier noch ein paar Schleifendurchläufe einsparen. Ein result *= result; verdoppelt z.B. den Exponenten in einem Schritt, statt ihn immer nur um 1 zu erhöhen. Mit der Regel axay=ax+ya^x \cdot a^y = a^{x+y} kann man sich auf jeden Fall mit etwas Tüfteln einen O(logn)\mathcal{O}(\log n)-Algorithmus für die Integer-Potenz stricken.

    Ausserdem würde ich empfehlen, für diese Funktion nur einen einzigen Datentypen zu verwenden. 3 verschiedene Typen für Rückgabewert und Parameter ist für so eine grundlegende Funktion etwas chaotisch. Wenn du nicht wirklich weisst, welchen Typen du nehmen willst, dann machs generisch und entscheide dich später:

    // C++14
    #include <type_traits>
    
    template <typename T>
    std::enable_if_t<std::is_integral<T>::value, T> nPow(T v, T N)
    {
        ...
    }
    
    // C++20
    #include <concepts>
    
    template <std::integral T>
    T nPow(T v, T N)
    {
        ...
    }
    


  • This post is deleted!


  • This post is deleted!


  • @zeropage
    @Finnegan

    Ein result *= result; verdoppelt z.B. den Exponenten in einem Schritt, statt ihn immer nur um 1 zu erhöhen. Mit der Regel ax⋅ay=ax+ya^x \cdot a^y = a^{x+y}a​x​​⋅a​y​​=a​x+y​​ kann man sich auf jeden Fall mit etwas Tüfteln einen O(logn)\mathcal{O}(\log n)O(logn)-Algorithmus für die Integer-Potenz stricken.

    Hierfür kenne ich die binäre Exponentiation.

    https://de.wikipedia.org/wiki/Binäre_Exponentiation
    https://en.wikipedia.org/wiki/Exponentiation_by_squaring

    Ich habe diese mal im Bereich von GNSS / GPS eingesetzt, kenne diese aber durch einen Kryptographie Kurs.



  • @Quiche-Lorraine sagte in N-th Power:

    Hierfür kenne ich die binäre Exponentiation.

    Ja, da gab es was, ich erinnere mich. Ich wollte es nicht direkt posten um @zeropage die Möglichkeit zu geben selbst drauf zu kommen, aber ich hatte mir gestern das hier überlegt:

    int ipow(int x, int n)
    {
        if (n == 0)
            return 1;
        
        int result = x;
        int i = 1;
        
        for (; i <= n / 2; i *= 2)
            result *= result;
        
        return result * ipow(x, n - i);
    }
    

    Der macht eigentlich unterm Strich dasselbe. Die ganzen / 2 und * 2 kann man auch als Bit-Operationen und die Endrekursion als fortgesetzte Schleife umformulieren, dann landet man ist man wahrscheinlich bei der Binären Exponentiation.



  • @Finnegan sagte in N-th Power:

    Die ganzen / 2 und * 2 kann man auch als Bit-Operationen [...] umformulieren

    Brrrr. Schauder.



  • @zeropage sagte in N-th Power:

    Das hätte mich jetzt aber interessiert

    Ja, weil's so blöd dasteht:

    @zeropage sagte in N-th Power:

    	if (N >= vec.size())
    

    da muss man (ich zumindest) nachdenken. Vorschlag:

    if (vec.size() <= N)
    

    Aber vielleicht liegt es auch nur an mir.


    @others: Overflow check?? Anyone??



  • @Swordfish Finde ich schon okay das N auf der linken Seite. Die frage ist ja "Liegt N im Vector?" und nicht "Hat der Vector höchstens N (+1) Elemente?" ... danach entscheide zumindest ich was links und was rechts steht.



  • @Finnegan Ich stelle mir das optisch vor. Nimm einen Zahlenstrahl:

    +--------------------------->
              |          |
         vec.size()      |
                         |
                         N
    

    aber wie gesagt:

    @Swordfish sagte in N-th Power:

    Aber vielleicht liegt es auch nur an mir.



  • @Swordfish Hehe... habs grad auch verschnöselt. Die Frage hier ist "Liegt N außerhalb des Vector?". Kann man so machen, aber ich hätte wohl eher !(N < vec.size()) geschrieben. "Liegt N nicht im Vector?" 😉


Log in to reply