o metodzie

Ogólna zasada algorytmu polega na dzieleniu zakresu na połowę i sprawdzaniu, czy element znajdujący się dokładnie pośrodku jest elementem szukanym, a jeśli nie, to czy jest większy, czy mniejszy od szukanego, oraz na przeszukaniu odpowiednio w prawo i lewo.
W ten sposób szybko zawęża się zakres poszukiwań, aż w końcu otrzymuje się przedział jednoelementowy.
Można wtedy wskazać szukany element lub stwierdzić, że go nie ma.

pierwiastek kwadratowy

Jak znaleźć wartość √2 z dokładnością 0,001, jeśli nie ma funkcji pierwiastek?
Stosować możemy jedynie podstawowe operacje arytmetyczne.

Wartość pierwiastka możemy podać z określonym przybliżeniem (nie ma skończonej wartości).
Szukamy zatem liczby a spełniającej nierówność |√2 - a| < przyb

Algorytm można zdefiniować następująco:

Do zapisu algorytmu potrzebujemy zmiennej rzeczywistej podwójnej długości, czyli long double oraz funkcji obliczającej wartość bezwzględną, czyli fabs().
Funkcja ta znajduje się w biblitece procedur matematycznych, musimy ją zatem dołączyć: #include <cmath>

Program przedstawia się następująco:

#include <iostream>
#include <cmath>
        
using namespace std;

double pierwiastek (double x, double przyb) {
    double a = 0.0;
    double b = x;
    double c;
    
    while (fabs(b-a) > przyb) {
        c = (a + b)/2;
        if(c * c > x)
            b = c;
        else 
            a = c;
    }

    return c;
}

int main() {

    double x = 2;
    double przyb = 0.001;
    cout << "Pierwiastek z " << x << " = " << pierwiastek(x, przyb);

    return 0;
}

metoda Newtona-Raphsona

Metoda opiera się na wzorze:

Tak wygląda nasz algorytm:

pobierz liczbę
x<-liczba/2
dopóki |x-liczba/x|> ustalona dokładność wykonuj
     x=(x+liczba/x)/2
     jeżeli x*x równa się liczbie zakończ działanie pętli

zwróć x

I bazująca na nim procedura:

double pierwiastek(double liczba)
{
    double x = liczba/2;

    while(fabs(x-liczba/x)>0.000001) 
    {
        x = (x + liczba/x)/2;   //nową wartością boku jest średnia arytmetyczna dwóch poprzednich
        cout << x << "\n";
    if(x*x == liczba) break;
    }
    return x;
}

zadanie

1. Napisz procedurę pierwiastekn(x, n, przyb) obliczającą pierwiastek stopnia n.
   
   Wskazówka: Wykorzystaj funkcję pow(x,n)
2. Określ poziom dokładności obliczeń, aby pierwiastki wymierne podawane były bez przybliżenia.
   Np.:
   √4 = 2
   ∛27 = 3
3. Na podstawie procedury pierwiastekn napisz procedurę wyznaczającą miejsce zerowe funkcji liniowej (definiowanej w oddzielnej procedurze) w zadanym przedziale <a..b>.
4. Porównaj metodę poławiania i Newtona-Raphsona.
   Zmodyfikuj procedury, tak aby wyświetlane były wykonywane operacje.
   Zdefinjuj wniosek.