Pierwiastek n-tego stopnia

Wstęp

Istnieje wiele algorytmów rozwiązujący dane zagadnienie, ale zwykle tylko jeden osiąga największą efektywność. W przypadku wyliczania pierwiastka n-tego stopnia bardzo szybko można uzyskać wynik na podstawie metody wyliczania pierwiastka kwadratowego Newtona-Raphsona. Wyliczona wartość algorytmem jest jedynie przybliżeniem, ale bardzo szybko pozwala uzyskać wynik do p miejsc po przecinku.

Zasada działania

Kolejne przybliżenia liczby a oblicza się na podstawie poprzedniego przybliżenia. Na początek zakłada się, że przybliżenie wynosi tyle co liczba P0 = a. W pętli dopóki nie zostanie spełniony warunek należy obliczyć kolejne przybliżenia zgodnie z poniższym wzorem:

Ostatnia wyliczona wartość Px przed spełnieniem warunku stopu jest poszukiwaną wartością przybliżenia.

Warunek stopu

Bardzo ważne, aby dodatkowo określić także warunek zatrzymania algorytmu. Może on działać na kilka różnych sposobów. Najprostszy z nich polega na wykonaniu określonej ilości powtórzeń. Innym sposobem jest sprawdzanie o ile zmieniło się przybliżenie. W przypadku, gdy przybliżenie zostało zmienione niż żądana dokładność to dalsze obliczenia można zaniechać. Druga metoda jest jednak ryzykowna, ponieważ ze względu na ograniczenia przechowywania liczb rzeczywistych program może wpaść w nieskończoną pętle. Najlepszym rozwiązaniem jest stosowanie dwóch metod równocześnie.

Implementacja

Obliczenia

Przypuśćmy, że program ma wykonać maksymalnie n iteracji, a obliczenia powinny zostać wykonane z pewnym przybliżeniem r. Wtedy program będzie wyglądał następująco:

1. double pierwiastekn(double a, int n, double r = 0.0000001, int max_n = 10) {
2.   double x = a, xp;
3.   do {
4.     xp = x;
5.     x = (1 / (double)n)*((n - 1)*xp + a/pow(xp, n - 1));
6.   } while (--max_n > 0 && xp - x > r);
7.   return x;
8. }

(1.) Funkcja przyjmuje cztery argumenty: a - liczba pierwiastkowana, n - stopień pierwiastka, r - dokładność przybliżenia oraz max_n - maksymalna ilość iteracji. (2.) Przypisz aktualnemu przybliżeniu wartość a i zadeklaruj zmienną przechowująca poprzednie przybliżenie. (3.) W pętli: (4.) zapamiętaj poprzednie przybliżenie i (5.) oblicz kolejne. (6.) Czynność powtórz dopóki obydwa warunki są spełnione. Po zakończeniu (7.) zwróć wynik.

Precyzja wyniku

W celu zmiany ilości wypisywanych miejsc po przecinku należy skorzystać z funkcji setprecision(int n), która znajduje się w bibliotece iomanip. Po przekazaniu parametru n program będzie wiedział, że ma wypisać n cyfr.

W celu zmiany precyzji można skorzystać z funkcji Round w klasie Math. Jako pierwszy argument podaje się liczbę do zaokrąglenia, a w drugim do ilu cyfr ma zostać przybliżona liczba.

Testowanie funkcji

Poniższa funkcja main() wyświetla na ekranie wyświetla wynik √2 z 12 cyfrową precyzją:

1. int main() {
2.   cout << setprecision(12);
3.   cout << pierwiastekn(2, 2) << endl;
4.   system("pause");
5.   return 0;
6. }

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Napisz funkcję pierwiastekn(), która przyjmie trzy argumenty (kolejno): a - liczbę pierwiastkowaną, n - stopień pierwiastka oraz k - ile liczb po przecinku ma się zgadzać z najdokładniejszym możliwym przybliżeniem. W funkcji main() zaprezentuj działanie funkcji wypisując na ekran kolejne przybliżenia począwszy od k = 0 do k = 6. Wszystkie wyniki wypisz z precyzją z jaką miało być obliczone przybliżenie.

Poprawnie napisana funkcja powinna wypisać:

1. 0     2
2. 1     1.3
3. 2     1.32
4. 3     1.316
5. 4     1.3161
6. 5     1.31607
7. 6     1.316074

• Kod źródłowy Zadanie 1