N-th Power

Leon0402

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.

zeropage

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.

zeropage

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;
}

yahendrik

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.

zeropage

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);
}

zeropage

@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.

yahendrik

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

zeropage

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.

Finnegan

@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 $a^x \cdot a^y = a^{x+y}$ kann man sich auf jeden Fall mit etwas Tüfteln einen $\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)
{
    ...
}

zeropage

Dieser Beitrag wurde gelöscht!

zeropage

Dieser Beitrag wurde gelöscht!

Quiche Lorraine

@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}ax⋅ay=ax+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.

Finnegan

@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.

Swordfish

@Finnegan sagte in N-th Power:

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

Brrrr. Schauder.

Swordfish

@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??

Finnegan

@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.

Swordfish

@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.

Finnegan

@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?"

hustbaer

@Finnegan sagte in N-th Power:

Die frage ist ja "Liegt N im Vector?

So wie der Code dasteht eher "liegt N ausserhalb vom Vektor" bzw. "ist N zu gross".
Aber ja, kann man ruhig so schreiben.

Verwirrend finde ich dagegen das grosse N. Da hätte ich etwas konstantes erwartet.

Swordfish

@hustbaer sagte in N-th Power:

Verwirrend finde ich dagegen das grosse N. Da hätte ich etwas konstantes erwartet.

Oh ja, autsch, das ist ja garkein Template