Dokumentacja projektu
"Metoda Newtona. Metody zmodyfikowane
dla pierwiastków wielokrotnych"
Autor | Marcin Wiącek <marcin-wiacek@topnet.pl> |
Grupa dziekańska | 2P14 |
Prowadzący | dr inż. Michał Borecki |
Semestr | zimowy 2001 |
Metoda Newtona pozwala na obliczanie przybliżonych wartości pierwiastków (zarówno o parzystej i nieparzystej wielokrotności) równania f(x)=0.
Założenia tej metody są następujące: w przedziale <a;b>, w którym położony jest pierwiastek, funkcja f(x) ma na krańcach różne znaki oraz pierwsza i druga pochodna mają stałe znaki.
Kolejne przybliżenia pierwiastków są wtedy równe:
xn+1 = xn - f(xn)/f'(xn)
Projekt jest praktyczną realizacją tej metody. Pozwala on na policzenie pierwiastka z zadaną dokładnością. Wykorzystuje on jeden z trzech sposobów implementacji podanych w pozycji 1 literatury.
Pliki projektu zostały podzielone i zapisane w kilku katalogach:
Kolejne kroki potrzebne do kompilacji projektu:
Program "projekt" po uruchomieniu wymaga czterech linijek danych wprowadzonych od użytkownika:
./projekt < plik
Przykładowy plik może wyglądać następująco:
x^4-4*x^3-5*x^2-4*x+4+sin(x)+ln(10) 0.0005 3 50Program ignoruje spacje wprowadzone przez użytkownika.
Znakiem oddzielającym części całkowite od ułamkowych w liczbach jest kropka.
Przy wprowadzaniu wzoru funkcji zmienną jest "x". Możliwe jest używanie następujących operatorów matematycznych "+", "-", "*", "/", "^", następujących stałych matematycznych "pi" i "e" oraz funkcji matematycznych "sin", "cos", "tan", "ctg", "ln".
Po przyjęciu danych i sprawdzeniu ich poprawności program przystępuje do obliczeń (wypisując dla kolejnych przybliżeń pierwiastka wartość funkcji i pochodnej), a następnie pokazuje wynik obliczeń.
6. Znane błędy i
ograniczenia projektu
W przypadku, gdyby wynik działania projektu był różny od oczekiwanych, należy skompilować go z kodem używanym podczas sprawdzania poprawności jego działania (zostało to opisane w punkcie 3).
W przypadku, gdyby zaszła potrzeba skierowania komunikatów debugujących do pliku, należy użyć komendy "./projekt 2> plik" (jeżeli zachodzi konieczność zapisu do pliku normalnych komunikatów programu, używamy komendy "./projekt > plik").
Należy pamiętać, iż czasami występujące niezgodności mogą wynikać z tego, iż projekt przy obliczaniu kolejnych wartości stosuje przybliżoną dokładność (błędy mogą się sumować).
Od użytkownika nie jest wymagane podawanie przedziału obliczeń (zgodnie z założeniami metody) Jest to wygodne, gdyż nie musi on znać przebiegu zmienności funkcji, natomiast wymaga, aby ilość kroków, w których program ma szukać przybliżonego pierwiastka, była możliwie duża. Inaczej ciąg kolejnych pierwiastków może nie być wystarczająco "szybko" zbieżny do zera i projekt wykaże brak pierwiastka.
Należy również pamiętać o podawaniu możliwie najmniejszej wartości dokładności, jeżeli zależy nam na możliwie dokładnym obliczeniu pierwiastka podanej funkcji.
Makrodefinicje i stałe
Nazwa | Opis |
dprintf | funkcja wypisująca dane wyłącznie, gdy zdefiniowaną stałą DEBUG (w pliku config.h) |
DEBUG | Jej zdefiniowanie włącza kompilowanie kodu używanego przy pisaniu programu |
przyrost | Przyrost, dla którego ma być liczona pochodna funkcji zgodnie ze wzorem:
f'(x)=(f(x+przyrost)-f(x))/przyrost Im mniejszy, tym dokładniej liczona pochodna |
MAX_ELEMENTOW | Ilość elementów w każdej strukturze LICZBA |
ST_DODAWANIE | Używana przy liczeniu wag w strukturze LICZBA. Definiuje dodawanie |
ST_ODEJMOWANIE | Używana przy liczeniu wag w strukturze LICZBA. Definiuje odejmowanie |
ST_MNOZENIE | Używana przy liczeniu wag w strukturze LICZBA. Definiuje mnożenie |
ST_DZIELENIE | Używana przy liczeniu wag w strukturze LICZBA. Definiuje dzielenie |
ST_POTEGOWANIE | Używana przy liczeniu wag w strukturze LICZBA. Definiuje potęgowanie |
ST_FUNKCJA | Używana przy liczeniu wag w strukturze LICZBA. Definiuje funkcje matematyczne |
Struktury danych
LICZBA
Opis: struktura przechowująca opis funkcji (pochodnej) w postaci zrozumiałej dla programu
Nazwa | Typ | Opis |
liczby[MAX_ELEMENTOW] | double | Przechowuje liczby kolejnych elementów funkcji |
stringi[MAX_ELEMENTOW][100] | char | Przechowuje napisy kolejnych elementów funkcji |
wagi[MAX_ELEMENTOW] | int | Przechowuje wagi kolejnych elementów funkcji |
ile | int | Ilość elementów działania przechowywanych w liczby, stringi i wagi |
Zmienne globalne
Nazwa | Typ | Opis |
wart_funkcji | double | Wartość funkcji wyliczona dla konkretnego x |
wart_pochodnej | double | Wartość pochodnej funkcji wyliczona dla konkretnego x |
wzor[1000] | char | Wzór funkcji wczytanej od użytkownika |
mojblad | int | Błąd zwracane prze funkcje z funkcje.c |
Funkcje
int main()
Opis: główna funkcja programu
Zmienne:
Nazwa | Typ | Opis |
j | int | Używana w pętli |
i | int | Używana przy zwracaniu wartości błędu przez funkcje licz_funkcja_pochodna i wczytaj_liczba |
ile_krokow | int | W ilu krokach program ma próbować znaleźć pierwiastek |
iks | double | Aktualna wartość przybliżenia pierwiastka |
dokladnosc | double | Dokladność, z jaką ma być znaleziony pierwiastek |
wynik | int | Kod błędu, który jest zarazem kodem błędu programu |
Algorytm:
Opis: funkcja wczytująca liczbę z pliku stdin do zmiennej liczba
Zmienne:
Nazwa | Typ | Opis |
ciag[1000] | char | Bufor na wczytanie linii |
wartosc | double | Wczytana wartość liczby |
i | int | Miejsce na kod błędu zwracany z funkcji wez_liczba |
*liczba | double | Zmienna pozwalająca zwrócić liczbę na zewnątrz |
dodatnia | int | Jeżeli jest równa 1, zwracane są tylko liczby dodatnie |
wynik | int | zwracany kod błędu |
Algorytm:
Opis: funkcja obliczająca wartości funkcji i jej pochodnej dla zadanego xliczba
Zmienne:
Nazwa | Typ | Opis |
iks | double | Wartość x, dla której liczona jest wartość funkcji i pochodnej |
i | int | Używana do zwracania kodów błędów |
wynik | int | zwracany kod błędu |
Algorytm:
Opis: funkcja wypisująca błędy napotkane przez program przy obliczaniu (wzoru) funkcji lub jej pochodnej
Zmienne:
Nazwa | Typ | Opis |
j,z | int | Używane w pętlach |
i | int | Kod błędu, który będzie komentowany |
liczba[1000] | char | W tej zmiennej jest zawarty pierwotny wzór funkcji podany przez użytkownika |
dodaj | int | Ile znaków spacji ma być napisane, gdy program wskazuje konkretne błędne miejsce we wzorze funkcji |
Algorytm:
Opis: Funkcji należy podać wartość wagi działania zapisanego w tablicy wagi struktury LICZBA. Funkcja zwróci poziom zagłębienia danej wagi.
Zmienne:
Nazwa | Typ | Opis |
i | int | Waga, dla której będzie liczony poziom |
zwracana | int | Wartość zwracana |
wynik | int | zwracany poziom wagi |
Algorytm:
Opis: Funkcji należy podać wartość wagi działania zapisanego w tablicy wagi struktury LICZBA. Funkcja zwróci kod działania danej wagi.
Zmienne:
Nazwa | Typ | Opis |
i | int | Waga, dla której będzie liczone działanie |
zwracana | int | Wartość zwracana |
wynik | int | zwracany kod działania wagi |
Algorytm:
Opis: Funkcja dodaje jedno działanie na pozycji "numer" do struktury mojaliczba.
Zmienne:
Nazwa | Typ | Opis |
numer | int | Pozycja, na której będzie wstawione działanie |
*string | unsigned char | Ciąg znakowy działania |
liczba | double | Liczba działania |
waga | int | Waga działania |
*mojaliczba | LICZBA | W tej strukturze będzie przeprowadzona operacja dodawania |
wynik | int | zwracany kod błędu |
Algorytm:
Opis: Funkcja usuwa działania ze struktury mojaliczba.
Zmienne:
Nazwa | Typ | Opis |
numer | int | Pozycja, od której będą usuwane działania |
ileusunac | int | Ile kolejnych działań usunąć |
i | int | Używana w pętli |
*mojaliczba | LICZBA | W tej strukturze będzie przeprowadzona operacja odejmowania |
wynik | int | zwracany kod błędu |
Algorytm:
Opis: Funkcja oblicza wartość funkcji o wzorze podanym w ciąg dla x o wartości podanej w zmiennej iks.
Zmienne:
Nazwa | Typ | Opis |
*ciag | unsigned char | Wzór funkcji |
mojaliczba | LICZBA | wzór przechowywany w postaci zrozumiałej dla programu |
i,j | int | Używane w pętlach |
iks | int | x, dla którego obliczamy wartość funkcji |
*zwroc_wartosc | double | Tutaj jest wzracana wartość funkcji |
num | int | Numer "obrabianego" działania w strukturze mojaliczba |
poziom | int | Poziom "obrabianego" działania w strukturze mojaliczba |
wynik | double | Zmienna pomocnicza przechowująca liczbę pobraną ze struktury mojaliczba |
mnoznik | double | Mnożnik dla liczby pobranej ze struktury mojaliczba |
znaki[100] | char | Bufor pomocniczy na ciąg znaków ze struktury mojaliczba |
Algorytm:
Opis: Funkcja oblicza wartość pochodnej funkcji o wzorze podanym w ciąg dla x o wartości podanej w zmiennej iks.
Zmienne:
Nazwa | Typ | Opis |
*ciag | unsigned char | Wzór funkcji |
i | int | Używana do zwracania kodu błędu |
iks | int | x, dla którego obliczamy wartość funkcji |
*zwroc_wartosc | double | Tutaj jest wzracana wartość funkcji |
wynik, wynik2 | double | Zmienne pomocnicze na wartości funkcji |
Algorytm:
Opis: Z ciągu *ciag wyciąga liczbę rzeczywistą i zapisuje w zmiennej *wartosc.
Zmienne:
Nazwa | Typ | Opis |
*ciag | unsigned char | Z tego ciągu wyciągamy liczbę |
*wartosc | double | Wartość zwracana |
wynik | double | Liczba podczas wczytywania liczby z ciągu |
mnoznik | double | Mnożnik dla kolejnej cyfry liczby wczytywanej z ciągu |
num | int | Numer sprawdzanego znaku w ciągu znaków |
minus | int | Czy jest już liczba ujemna (wartość 1) czy nie (wartość!=1) |
wynik | int | zwracany kod błędu |
Algorytm:
Informacja: w stosunku do kodu źródłowego zapisanego w plikach w niektórych miejsach zastosowano łamane linii niezgodne z notacją języka C (ze względu na ograniczoną szerokość wydruku).
funkcje.c:
/* Biblioteka projektu zawierajaca funkcje pozwalajace wykonywac rozne ciekawe rzeczy z wzorami funkcji podanymi w postaci ciagu znakow. Rozprowadzana na licencji GNU GPL. Autor: Marcin Wiacek <marcin-wiacek@topnet.pl> Grupa: 2P14 Semestr: zimowy 2001 */ /* Definicje uzywanych bibliotek */ #include <stdio.h> #include <math.h> #include <string.h> #include "funkcje.h" #include "config.h" char napis[100]; /* Definicja stalych uzywanych przy wagach */ #define ST_DODAWANIE 1 #define ST_ODEJMOWANIE 2 #define ST_MNOZENIE 3 #define ST_DZIELENIE 4 #define ST_POTEGOWANIE 5 #define ST_FUNKCJA 6 /* Struktura zawierajaca struktury potrzebne do rozkladania i obliczania funkcji i pochodnych */ typedef struct { /* Tablice sluzace do przechowywania rozlozonego na elementy pierwsze */ /* dzialania - liczb, napisow i wag ich dzialan */ double liczby[MAX_ELEMENTOW]; char stringi[MAX_ELEMENTOW][100]; int wagi[MAX_ELEMENTOW]; /* Po uzyciu przygotuj_funkcja zmienna okresla, ile "klockow" zawiera dzialanie */ int ile; } LICZBA; /* Funkcja podaje dzialanie zawarte w wadze podanej jako "wartosc" */ int oblicz_dzialanie(int wartosc) { int zwracana; //wartosc zwracana zwracana=wartosc; while (zwracana>6) {zwracana=zwracana-6;}; return zwracana; } /* Dodaje jedno podane dzialanie do struktury "mojaliczba" */ int dodaj_klocek(int numer, unsigned char *string, double liczba, int waga, LICZBA *mojaliczba) {
if (numer+1>MAX_ELEMENTOW) return 6; //za malo pamieci mojaliczba->liczby[numer]=liczba; strcpy(mojaliczba->stringi[numer],string); mojaliczba->wagi[numer]=waga; mojaliczba->ile++; return 0; } /* Usuwa ze struktury "mojaliczba" dzialania od numeru "numer". "ileusunac" okresla, ile dzialan usunac */ int usun_klocek(int numer, int ileusunac, LICZBA *mojaliczba) { int i; if (numer-ileusunac>mojaliczba->ile) { dprintf("Blad w usun. Prosze raportowac\n"); return 1; } for (i=numer;i<mojaliczba->ile-ileusunac+1;i++) { mojaliczba->liczby[i]=mojaliczba->liczby[i+ileusunac]; strcpy(mojaliczba->stringi[i],mojaliczba->stringi[i+ileusunac]); mojaliczba->wagi[i]=mojaliczba->wagi[i+ileusunac]; } mojaliczba->ile=mojaliczba->ile-ileusunac; return 0; } /* Oblicza wartosc funkcji podanej w strukturze "moja liczba" dla x o wartosci "iks". Wynik zwracany w "zwroc_wartosc" */ int wartosc_funkcji(unsigned char *ciag, double *zwroc_wartosc, double iks) { int i,j; //petle LICZBA mojaliczba; int poziom=0; char znaki[100]; //przy parsowaniu ciagu znakow double wynik=0; //jezeli parsujemy liczbe - tutaj jest jej aktualna wartosc double mnoznik=1; //mnoznik dla kolejnej cyfry liczby int stan=0; // zmienna okreslajaca stan parsowania: //0-glowna petla,1-liczba,2-napis int num=0; // numer kolejnego obrabianego znaku/dzialania /* Warunki poczatkowe */ znaki[0]=0; mojaliczba.wagi[0]=0; mojaliczba.ile=0; /* Znak 0x00 konczy ciag. Wykonujemy petle az do niego */ while (*ciag!=0x00) { if (stan==0) { //start i znaki dzialan, nawiasy if ((*ciag>='0' && *ciag<='9') || *ciag=='.') { //cyfry lub kropka wynik=0; mnoznik=1; //wartosc domyslne dla liczby znaki[0]=0; //czyscimy stan=1; //teraz bedziemy obrabiac liczbe } else { if ((*ciag>='a' && *ciag<='z') || /* znaki alfabetu */ (*ciag>='A' && *ciag<='Z')) { /* -"- */ znaki[0]=0; //czyscimy wynik=0; //czyscimy stan=2; //teraz bedziemy obrabiac ciag znakow } else { switch (*ciag) { case '+': /* Znaki dzialan */ case '-': /* -"- */ case '*': /* -"- */ case '/': /* -"- */ case '^': /* -"- */ //znak dzialania jest ostatni w ciagu if (*(ciag+1)==0x00) return 7; /* Tworzymy nowa pozycje */ switch (*ciag) { case '+': if (dodaj_klocek(mojaliczba.ile, znaki, wynik, ST_DODAWANIE+6*poziom, &mojaliczba)!=0) return 6; //za malo pamieci break; case '-': if (dodaj_klocek(mojaliczba.ile, znaki, wynik, ST_ODEJMOWANIE+6*poziom, &mojaliczba)!=0) return 6; //za malo pamieci break; case '*': if (dodaj_klocek(mojaliczba.ile, znaki, wynik, ST_MNOZENIE+6*poziom, &mojaliczba)!=0) return 6; //za malo pamieci break; case '/': if (dodaj_klocek(mojaliczba.ile, znaki, wynik, ST_DZIELENIE+6*poziom, &mojaliczba)!=0) return 6; //za malo pamieci break; case '^': if (dodaj_klocek(mojaliczba.ile, znaki, wynik, ST_POTEGOWANIE+6*poziom, &mojaliczba)!=0) return 6; //za malo pamieci break; } ciag++;num++; //przechodzimy znak do przodu break; case '(': /* Otwieramy nawias */ //nawias jest ostatni w ciagu if (*(ciag+1)==0x00) return 7; poziom++; mojaliczba.liczby[mojaliczba.ile]=0; //czyscimy strcpy(znaki,""); //czyscimy wynik=0; //czyscimy ciag++;num++; //przechodzimy znak do przodu break; case ')': /* Zamykamy nawias */ if (poziom==0) { /* Za duzo nawiasow prawych */ mojaliczba.ile=num; return 1; } poziom--; ciag++;num++; //przechodzimy znak do przodu break; case ' ': /* Spacje po prostu ignorujemy */ ciag++;num++; //przechodzimy znak do przodu break; default: //nieznany znak mojaliczba.ile=num; return 5; } } } } if (stan==1) { //cyfry i kropka dziesietna /* Mamy cyfre */ if (*ciag>='0' && *ciag<='9') { /* ... wiec dodajemy odpowiednio do naszej liczby */ if (mnoznik>=1) { //liczby bez czesci ulamkowej mnoznik=mnoznik*10; wynik=wynik*10+(*ciag-'0'); } else { //i z czescia ulamkowa wynik=wynik+mnoznik*(*ciag-'0'); mnoznik=mnoznik*0.1; } ciag++;num++; //przechodzimy znak do przodu } else { switch (*ciag) { case '.': /* Kropka wprowadza znaki dziesietne */ if (mnoznik>0.9) { mnoznik=0.1; } else { /* Nie moze byc dwoch kropek w liczbie */ mojaliczba.ile=num; return 3; } ciag++;num++; //przechodzimy znak do przodu break; case ' ': ciag++;num++; //przechodzimy znak do przodu break; default: //nieznany znak w liczbie - wracamy do glownej petli stan=0; } } } if (stan==2) { //znaki if (*ciag>='a' && *ciag<='z') { //male znaki znaki[strlen(znaki)+1]=0; //zamykamy zwiekszony ciag znakiem 0 znaki[strlen(znaki)]=*ciag; //dodajemy znak ciag++;num++; //przechodzimy znak do przodu } else { if (*ciag>='A' && *ciag<='Z') { //duze znaki znaki[strlen(znaki)+1]=0; //zamykamy zwiekszony ciag znakiem 0 //dodajemy+ konwersja na male litery znaki[strlen(znaki)]=*ciag-('A'-'a'); ciag++;num++; //przechodzimy znak do przodu } else { if (*ciag=='(') { //dla funkcji typu cos(x).. if (dodaj_klocek(mojaliczba.ile, znaki, wynik, ST_FUNKCJA+6*poziom, &mojaliczba)!=0) return 6; //za malo pamieci } stan=0; //do glownej petli } } } } /* Po wyjsciu z petli cos tam zawsze zostalo niedokonczone. Wstawmy to */ if (dodaj_klocek(mojaliczba.ile, znaki, wynik, 0 , &mojaliczba)!=0) return 6; //za malo pamieci /* Wzor rozlozony i gotowy. Obliczmy teraz wartosc funkcji */ /* Zamieniamy napisy "pi" i "e" na odpowiadajace im stale matematyczne, jak rowniez zamiast iksa wstawiamy odpowiadajaca mu wartosc */ for (i=0;i<mojaliczba.ile;i++) { if (!strcmp(mojaliczba.stringi[i],"pi")) { //liczba PI mojaliczba.liczby[i]=M_PI; strcpy(mojaliczba.stringi[i],""); } if (!strcmp(mojaliczba.stringi[i],"e")) { //liczba Eulera mojaliczba.liczby[i]=M_E; strcpy(mojaliczba.stringi[i],""); } if (!strcmp(mojaliczba.stringi[i],"x")) { //iks mojaliczba.liczby[i]=iks; strcpy(mojaliczba.stringi[i],""); } } /* Dopoki waga dzialania!=0. Czyli dopoki mamy dzialania */ while (mojaliczba.ile!=0) { j=mojaliczba.wagi[0];num=0; //warunki poczatkowe /* szukamy dzialania o najwyzszej wadze */ for (i=0;i<mojaliczba.ile;i++) { if (mojaliczba.wagi[i]>j) {j=mojaliczba.wagi[i];num=i;} } j=oblicz_dzialanie(j); switch (j) { case ST_DODAWANIE : /* Dodawanie */ case ST_ODEJMOWANIE: /* odejmowanie */ case ST_MNOZENIE : /* mnozenie */ case ST_DZIELENIE : /* dzielenie */ case ST_POTEGOWANIE: /* potegowanie */ if (strcmp(mojaliczba.stringi[num+1],"")) { //jakis dziwny string strcpy(napis,mojaliczba.stringi[num+1]); return 4; } switch (j) { case 1:mojaliczba.liczby[num]= mojaliczba.liczby[num]+mojaliczba.liczby[num+1];break; case 2:mojaliczba.liczby[num]= mojaliczba.liczby[num]-mojaliczba.liczby[num+1];break; case 3:mojaliczba.liczby[num]= mojaliczba.liczby[num]*mojaliczba.liczby[num+1];break; case 4:if (mojaliczba.liczby[num+1]==0) return 2; mojaliczba.liczby[num]= mojaliczba.liczby[num]/mojaliczba.liczby[num+1]; break; case 5:mojaliczba.liczby[num]= pow(mojaliczba.liczby[num],mojaliczba.liczby[num+1]); } mojaliczba.wagi[num]=mojaliczba.wagi[num+1]; break; case ST_FUNKCJA: //funkcje matematyczne if (!strcmp(mojaliczba.stringi[num],"ln")) { mojaliczba.liczby[num]=log(mojaliczba.liczby[num+1]); if (isnan(mojaliczba.liczby[num])) return 9; strcpy(mojaliczba.stringi[num],""); mojaliczba.wagi[num]=mojaliczba.wagi[num+1]; } else { if (!strcmp(mojaliczba.stringi[num],"sin")) { mojaliczba.liczby[num]=sin(mojaliczba.liczby[num+1]); if (isnan(mojaliczba.liczby[num])) return 9; strcpy(mojaliczba.stringi[num],""); mojaliczba.wagi[num]=mojaliczba.wagi[num+1]; } else { if (!strcmp(mojaliczba.stringi[num],"cos")) { mojaliczba.liczby[num]=cos(mojaliczba.liczby[num+1]); if (isnan(mojaliczba.liczby[num])) return 9; strcpy(mojaliczba.stringi[num],""); mojaliczba.wagi[num]=mojaliczba.wagi[num+1]; } else { if (!strcmp(mojaliczba.stringi[num],"tan")) { mojaliczba.liczby[num]=tan(mojaliczba.liczby[num+1]); if (isnan(mojaliczba.liczby[num])) return 9; strcpy(mojaliczba.stringi[num],""); mojaliczba.wagi[num]=mojaliczba.wagi[num+1]; } else { if (!strcmp(mojaliczba.stringi[num],"ctg")) { if (mojaliczba.liczby[num+1]==0) return 2; mojaliczba.liczby[num]=1/tan(mojaliczba.liczby[num+1]); if (isnan(mojaliczba.liczby[num])) return 9; strcpy(mojaliczba.stringi[num],""); mojaliczba.wagi[num]=mojaliczba.wagi[num+1]; } else { strcpy(napis,mojaliczba.stringi[num]); return 4; } } } } } } usun_klocek(num+1,1,&mojaliczba); } *zwroc_wartosc=mojaliczba.liczby[0]; return 0; } /* Oblicza wartosc pochodnej funkcji o wzorze podanym w zmiennej "ciag" dla x o wartosci "iks". Wynik zwracany w "zwroc_wartosc" */ int wartosc_pochodnej(unsigned char *ciag, double *zwroc_wartosc, double iks) { double wynik,wynik2; int i; i=wartosc_funkcji(ciag,&wynik,iks+przyrost); if (i!=0) return i; i=wartosc_funkcji(ciag,&wynik2,iks); if (i!=0) return i; *zwroc_wartosc=(wynik-wynik2)/przyrost; return 0; } /* Z ciagu "ciag" wyciaga liczbe rzeczywista */ int wez_liczba(unsigned char *ciag, double *wartosc) { double wynik=0; //aktualna wartosc liczby double mnoznik=1; //mnoznik dla kolejnej cyfry liczby int num=0; //ktory znak "ciagu" parsujemy int minus=0; //czy liczba ujemna /* Znak 0x00 konczy ciag. Wykonujemy petle az do niego */ while (*ciag!=0x00) { /* Mamy cyfre */ if (*ciag>='0' && *ciag<='9') { /* ... wiec dodajemy odpowiednio do naszej liczby */ if (mnoznik>=1) { //liczby bez czesci ulamkowej mnoznik=mnoznik*10; wynik=wynik*10+(*ciag-'0'); } else { //i z czescia ulamkowa wynik=wynik+mnoznik*(*ciag-'0'); mnoznik=mnoznik*0.1; } ciag++;num++; } else { switch (*ciag) { case '-': if (num!=0) return 11; //minus nie na poczatku minus=1; ciag++;num++; break; case '.': /* Kropka wprowadza znaki dziesietne */ if (mnoznik>0.9) { mnoznik=0.1; } else { /* Nie moze byc dwoch kropek w liczbie */ *wartosc=num; return 3; } ciag++;num++; break; case ' ': ciag++;num++; break; default: //nieznany znak w liczbie return 5; } } } *wartosc=wynik; if (minus==1) *wartosc=-wynik; return 0; }funkcje.h
/* Plik naglowkowy projektu z PROG Rozprowadzany na licencji GNU GPL. Autor: Marcin Wiacek <marcin-wiacek@topnet.pl> Grupa: 2P14 Semestr: zimowy 2001 */ #include "config.h" /* Definicja nowej funkcji wypisujacej tekst tylko przy zdefiniowanej stalej DEBUG */ #ifndef DEBUG #define dprintf(a...) do { } while (0) #else #define dprintf(a...) do { fprintf(stderr, a); fflush(stderr); } while (0) #endif extern char napis[100]; /* Deklaracje publicznych funkcji */ int wartosc_funkcji(unsigned char *ciag, double *zwroc_wartosc, double iks); int wartosc_pochodnej(unsigned char *ciag, double *zwroc_wartosc, double iks); int wez_liczba(unsigned char *ciag, double *wartosc);projekt.c:
/* Plik glowny projektu. Rozprowadzany na licencji GNU GPL. Autor: Marcin Wiacek <marcin-wiacek@topnet.pl> Grupa: 2P14 Semestr: zimowy 2001 */ /* Definicje uzywanych bibliotek */ #include <stdio.h> #include <math.h> #include <string.h> #include "funkcje.h" #include "config.h" double wart_funkcji,wart_pochodnej; //wartosci funkcji i pochodnej char wzor[1000]; //wzor funkcji od uzytkownika int mojblad; // tutaj bedzie zapisywany blad zwracany przez funkcje z funkcje.c /* Generalnie tutaj sa zebrane prawie wszystkie bledy numeryczne i skladniowe */ void blad(int i, double value, char liczba[1000], int dodaj) { int j,z; switch (i) { case 0: break; case 1: for (j=0;j<dodaj;j++) {printf(" ");} for (j=0;j<mojblad-1;j++) {printf(" ");} printf("^\n"); printf("Blad: za duzo nawiasow prawych\n"); break; case 2: for (j=0;j<strlen(liczba)-1;j++) { if (!strcmp(liczba+j,"/0")) { printf(" "); for (z=0;z<j;z++) {printf(" ");} printf("^\n"); } } printf("Blad: dzielenie przez zero\n"); break; case 3: for (j=0;j<dodaj;j++) {printf(" ");} for (j=0;j<mojblad-1;j++) {printf(" ");} printf("^\n"); printf("Blad: w liczbie moze byc tylko jedna kropka czesci dziesietnej\n"); break; case 4: printf("Blad: nieznana funkcja matematyczna \"%s\"\n",liczba); break; case 5: for (j=0;j<dodaj;j++) {printf(" ");} for (j=0;j<mojblad-1;j++) {printf(" ");} printf("^\n"); printf("Blad: nie znam takiego operatora matematycznego\n"); break; case 6: printf("Blad: za duzo elementow w dzialaniu (max %i)\n",MAX_ELEMENTOW); break; case 7: printf("Blad: Podane wyrazenie konczy sie znakiem dzialania (nawiasem) !\n"); break; case 9: printf("Blad: funkcja ln jest zdefiniowana tylko dla wartosci dodatnich\n"); break; case 11: printf("Blad: minus moze byc TYLKO na poczatku liczby\n"); break; case 12: printf("Blad: dopuszczam tylko dodatnie liczby\n"); break; default: dprintf("BLAD w programie. Prosze raportowac (wartosc %i dla i)\n",i); break; } } /* Liczenie wartosci funkcji i pochodnej i przyporzadkowanie do wart_funkcji i wart_pochodnej. Parametrem jest iks, dla ktorego jest to liczone */ int licz_funkcja_pochodna(double iks) { int i; printf("Liczenie pochodnej i wartosci funkcji dla x=%f\n",iks); printf("Funkcja wejsciowa : %s\n",wzor); /* Liczmy wartosc funkcji */ i=wartosc_funkcji(wzor,&wart_funkcji,iks); if (i!=0) { blad(i,wart_funkcji,wzor,21); return i; } else { /* Wynik nie jest liczba */ if (isinf(wart_funkcji)) { printf("wartosc funkcji - wynik niewlasciwy \n"); } else { printf("wartosc funkcji = %f \n",wart_funkcji); } } /* Liczmy wartosc pochodnej */ i=wartosc_pochodnej(wzor,&wart_pochodnej,iks); if (i!=0) { blad(i,wart_pochodnej,wzor,21); return i; } else { /* Wynik nie jest liczba */ if (isinf(wart_pochodnej)) { printf("wartosc pochodnej - wynik niewlasciwy \n"); } else { printf("wartosc pochodnej = %f \n",wart_pochodnej); } } return 0; } /* Pobieramy linie z pliku "File". Funkcja z (my)gnokii */ int GetLine(FILE *File, char *Line, int count) { char *ptr; if (fgets(Line, count, File)) { ptr=Line+strlen(Line)-1; while ( (*ptr == '\n' || *ptr == '\r') && ptr>=Line) *ptr--='\0'; return strlen(Line); } else return -1; } /* Wczytuje liczbe z pliku */ int wczytaj_liczba(double *liczba, int dodatnia) { char ciag[1000]; //tutaj wczytujemy kolejna linijke double wartosc; //wartosc liczby int i; //kod bledu GetLine(stdin, ciag,1000); //pobieramy linijke z wejscia dprintf("ciag = %s\n",ciag); i=wez_liczba(ciag,&wartosc); mojblad=wartosc; if (i!=0) { blad(i,wartosc,ciag,30); return i; } if (dodatnia==1 && wartosc<0) { i=12; blad(i,wartosc,ciag,30); return i; } *liczba=wartosc; return 0; } int main() { int i,j; double z; int ile_krokow=50; // ile maksymalnie krokow double iks=2; // punkt startowy double dokladnosc=0.005; // zadana dokladnosc obliczen printf("Wczytywanie wzoru funkcji "); GetLine(stdin, wzor,1000); //pobieramy wzor funkcji z wejscia printf("\n"); printf("Wczytywanie dokladnosci "); i=wczytaj_liczba(&dokladnosc,1); if (i!=0) return i; printf("\n"); printf("Wczytywanie punktu startowego "); i=wczytaj_liczba(&iks,0); if (i!=0) return i; printf("\n"); printf("Wczytywanie ilosci krokow "); i=wczytaj_liczba(&z,1); if (i!=0) return i; ile_krokow=z; printf("\n"); printf("Wczytano dane: dokladnosc=%f, punkt startowy=%f, ile_krokow=%i\n",dokladnosc,iks,ile_krokow); /* Obliczanie pierwszego punktu */ i=licz_funkcja_pochodna(iks); if (i!=0) return i; for (j=0;j<ile_krokow;j++) { if (fabs(wart_funkcji)<dokladnosc) { printf("Pierwiastek osiagnieto dla x=%f przy kroku %i\n",iks,j); return 0; } /* Pochodna = 0, a my musimy przez nia dzielic (obliczanie nowego iks. */ if (wart_pochodnej==0) { printf("Blad: dla x=%f pochodna=0\n",iks); return 20; } /* Liczymy nowy punkt */ iks=iks-(wart_funkcji/wart_pochodnej); i=licz_funkcja_pochodna(iks); if (i!=0) return i; } printf("Blad: nie znaleziono pierwiastka w %i krokach\n",ile_krokow); printf("\n"); return 0; }config.h
/* Plik konfiguracyjny projektu z PROG Rozprowadzany na licencji GNU GPL. Autor: Marcin Wiacek <marcin-wiacek@topnet.pl> Grupa: 2P14 Semestr: zimowy 2001 */ /* Definiowac tylko przy sprawdzaniu poprawnosci dzialania programu */ //#define DEBUG /* Tutaj definiujemy, ile klockow (liczb, funkcji, itp.) moze zawierac dzialanie obrabiane przez przygotuj_string, wartosc_funkcji */ #define MAX_ELEMENTOW 100 // Przyrost delta x uzywany przy liczeniu pochodnej #define przyrost 0.0001Makefile
# Makefile dla projektu z PROG # Autor: Marcin Wiacek <marcin-wiacek@topnet.pl> # Grupa: 2P14 # Semestr: zimowy 2001 TOPDIR=. # dodajemy Makefile z globalna konfiguracja include $(TOPDIR)/Makefile.globalMakefile.global
# Opcje dla Makefile z projektu RM = /bin/rm -f # czym usuwamy pliki INCLUDEDIR = lib/include # katalog z plikami naglowkowymi CONFIGINCLUDEDIR = . # katalog z plikiem naglowkowym config.h CC = kgcc # uzywany kompilator CFLAGS = -O2 -Wall # opcje kompilatora #wewnetrzny kod OBJS = $(TOPDIR)/lib/funkcje.o \ $(TOPDIR)/projekt/projekt.o all: $(TOPDIR)/projekt/projekt $(TOPDIR)/projekt/projekt: $(OBJS) clean: $(RM) $(OBJS) $(TOPDIR)/projekt/projekt .PHONY: all clean CFLAGS += -I$(TOPDIR)/$(INCLUDEDIR) -I$(TOPDIR)/$(CONFIGINCLUDEDIR)10. Testowanie projektu
Projekt został przetestowany na różnych zestawach danych (przykładowe dwa są zawarte w katalogu /Docs).
Podczas testowania zwracano uwagę na eliminację błędów numerycznych oraz na odporność na różnego rodzaju niewłaściwe dane. Usunięto wszelkie znalezione usterki.
Wiele procedur zawiera obecnie różne informacje debugujące pozwalające kontrolować poprawność ich działania. Aby je uaktywnić, należy w pliku config.h usunąć komentarz z linii "#define DEBUG" i skompilować projekt ponownie.