Creazione di una funzione square() senza x * x in C++

Question

Sono un C++ autodidatta e il libro "Princìpi di programmazione e pratiche con C++" di Bjarne Stroustrup. Uno dei "Try This" richiede questo:

Implementare square() senza utilizzare l'operatore di moltiplicazione; cioè, esegui x * x aggiungendo ripetutamente (avvia un risultato variabile a 0 e aggiungi x ad esso x volte). Quindi esegui una versione del "primo programma" usando quel quadrato().

Fondamentalmente, ho bisogno di creare una funzione square (int x) che restituisca il quadrato di esso senza utilizzare l'operatore di moltiplicazione. Finora ho questo:

int square(int x) 
{ 
    int i = 0; 
    for(int counter = 0; counter < x; ++counter) 
    { 
     i = i + x; 
    } 

return i; 
} 

Ma mi stavo chiedendo se ci fosse un modo migliore per farlo. La funzione sopra funziona, ma sono sicuro che non è il modo migliore per farlo. Qualsiasi aiuto?

Answer 1

In termini di corsa complessità temporale, l'implementazione è chiaro e abbastanza semplicemente, il suo tempo di esecuzione è T (n) = Θ (n) per l'ingresso n elements.Of Naturalmente è anche possibile utilizzare Divide-e -Conquer metodo, assumendo split n elementi in n/2: n/2, e infine ricorsivo calcola quindi riassume due parti, che il tempo di esecuzione sarà come T (n) = 2T (n/2) + Θ (n) = Θ (nlgn), possiamo constatare che la complessità del tempo di esecuzione peggiora rispetto all'implementazione.

Answer 2

Mats Petersson mi ha rubato l'idea prima ancora che pensassi di pensarlo.

#include <iostream> 

template <typename T> 
T square(T x) { 
    if(x < 0) x = T(0)-x; 
    T sum{0}, s{x}; 
    while(s) { 
     if(s & 1) sum += x; 
     x <<= 1; 
     s >>= 1; 
    } 
    return sum; 
} 

int main() { 
    auto sq = square(80); 
    std::cout << sq << "\n"; 
} 

Answer 3

È possibile includere o <math.h><cmath> e utilizzare la funzione sqrt():

#include <iostream> 
#include <math.h> 
int square(int); 

int main() 
{ 
    int no; 
    std::cin >> no; 

    std::cout << square(no); 
    return 0; 
} 

int square(int no) 
{ 
    return pow(no, 2); 
} 

Answer 4

int square(int x) 
{ 
    int result = 0; 
    for (int counter = 0; counter < x; ++counter) result += x; 
    return result; 
}