Tworzenie funkcji kwadratowej() bez x * x w C++

Question

Jestem samokształceniem C++ i książką "Programowanie - zasady i praktyki przy użyciu C++" autorstwa Bjarne Stroustrup. Jeden z "Spróbuj tego" pyta:

Kwadrat narzędzia() bez użycia operatora mnożenia; to znaczy, wykonaj x * x, powtarzając dodawanie (rozpocznij zmienny wynik na 0 i dodaj x do niego x razy). Następnie uruchom pewną wersję "pierwszego programu" za pomocą tego kwadratu().

Zasadniczo potrzebuję funkcji kwadratowej (int x), która zwróci jej kwadrat bez użycia operatora mnożenia. Do tej pory mam to:

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

return i; 
} 

Ale zastanawiałem się, czy istnieje lepszy sposób, aby to zrobić. Powyższa funkcja działa, ale jestem pewien, że nie jest to najlepsza metoda. Jakaś pomoc?

Answer 1

W kadencji Czas złożoności, implementacja jest jasne i wystarczy po prostu, jego czas pracy jest T (n) = Θ (n) dla wejścia n elements.Of Oczywiście można również skorzystać dziel i -Konkursuje metoda, zakładając podział n elementów na n/2: n/2, a na końcu rekursywnie obliczy ją, następnie podsumuje dwie części, że czas działania będzie taki jak T (n) = 2 T (n/2) + Θ (n) = Θ (nlgn), możemy stwierdzić, że jego złożoność czasu działania staje się gorsza niż implementacja.

Answer 2

Mats Petersson ukradł pomysł z mojej głowy, jeszcze zanim pomyślałem, że to wymyśliłem.

#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

Możesz dołączyć <math.h> lub <cmath> i używać jej sqrt() Funkcja:

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