FUNKCJE MATEMATYCZNE

Menu

 


     Algorytmy rekurencyjne implementujemy w języku C++ przy użyciu funkcji rekurencyjnych, czyli takich, które wywołują same siebie. Funkcje rekurencyjne w języku C++ odpowiadają definicjom rekurencyjnym funkcji matematycznych.


 Funkcja silnia (implementacja rekurencyjna).

    Ta funkcja oblicza wartość n! przy użyciu definicji rekurencyjnej. Algorytm zwraca poprawną wartość, jeżeli zostaje wywołany z wartością nieujemną n, przy czym wartość n! musi być dostatecznie mała, by mogła być wyrażona przez zmienną typu int:

// Plik źródłowy np. Unit1.cpp
//--------------------------------
int silnia(int n)
{
 if(n == 0) return 1;
 return n * silnia(n - 1);
}
//--------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
  Edit1->Text = IntToStr(silnia(12));
}
//--------------------------------

Występuje jednak problem z tą funkcją, otóż będzie ona działał poprawnie tylko dla n <= 12. Dzieje się tak dlatego, że zmienna typu int może przechowywać maksymalnie liczbę '4294967296', dla n = 12 wynik będzie się równał '479001600', ale dla n = 13 będzie to już '6227020800', czyli tym samym przekroczy pojemność zmiennej int. Żeby zwiększyć zakres możliwości silni należy zastąpić typ int, zmienną typu long double, zmienna ta posiada pojemność '3,36x10-4932 ... 1,18x104932':

// Plik źródłowy np. Unit1.cpp
//--------------------------------
long double silnia(int n)
{
  if(n == 0) return 1;
  return (double)n * silnia((double)n - 1);
}
//--------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
  Edit1->Text = FloatToStr(silnia(12));
}
//--------------------------------

Niestety i tutaj wystąpi problem ponieważ dla n = 18 zostanie przedstawiony taki wynik '6,402373705728E15', dlatego że taka wartości n przekracza pojemność zmiennej long double. Sprawdzałem mnożenie pisemnie i przy n = 18  wystarczy usunąć przecinek i wstawić zamiast E15 trzy zera by uzyskać prawidłowy wynik, przy n = 19 otrzymamy końcówkę E17 i tutaj również wystarczy usunąć przecinek i zmienić końcówkę E17 na trzy zera, przy n = 20 otrzymujemy końcówkę E18 i tutaj postępujemy tak samo, ale przy n = 21 otrzymujemy końcówkę E19 i tutaj końcówka wyniku nie zgadza się już o jedną cyfrę, a przy n = 21 otrzymamy końcówkę 1E21, tak więc nie wiem jaka jest zasada kodowania tych dłuższych liczb za pomocą E.

...powrót do menu.

Liczby Fibonacciego

     Fibonacci Leonardo, (znany również jako Leonardo z Pizy, Leonardo Pisano, Filius Bonacci), około 1175-około 1250. Matematyk włoski, jeden z najwybitniejszych uczonych średniowiecza; wprowadził w Europie cyfry arabskie; autor dzieł poświęconych arytmetyce i algebrze: m.in. Liber abaci (1202); od 1960 wzrosło zainteresowanie ciągiem Fibonacciego, gdzie każda liczba jest sumą dwóch poprzednich (1,1,2,3,5,8,13,...); liczby te posiadają niezwykłe cechy, umożliwiające zastosowanie ich w obliczeniach w botanice, psychologii i astronomii (np. dokładniejsza zgodność odległości między Słońcem a planetami niż przedstawiona w prawie Bode’a).
    Rozważmy taki oto problem: Pewien gospodarz zamknął w dużej klatce parę królików. Ile par królików będzie w klatce po roku, jeżeli każda para królików co miesiąc rodzi nową parę, a ta staje się ,,reproduktywna'' po upływie miesiąca?

Miesiąc

 

 Pary

dorosłe

 Pary

młode

 Całkowita

liczba par
1 1 1 2
2 2 1 3
3 3 2 5
4 5 3 8
5 8 5 13
6 13 8 21
7 21 13 34
8 34 21 55
9 55 34 89
10 89 55 144
11 144 89 233
12 233 144 377

Liczba par w kolejnym miesiącu to suma: liczby par poprzedniego miesiąca, powiększonej o liczbę par przychówku. Ostatnia liczba jest równa liczbie par sprzed dwóch miesięcy. Liczby Fibonacciego to:

F0 = 0, F1 = F2 = 1, Fn = Fn - 1 + Fn - 2, n ≥ 2

Dodanie dwóch jedynek na początku można też interpretować przy pomocy królików: jeżeli para została zamknięta w klatce zaraz po urodzeniu to po miesiącu w klatce ciągle była tylko ta jedna parka.
Zapisując obliczone wartości w tablicy statycznej, unika się wprost obliczania tych samych wartości. Podany algorytm wyznacza liczbę Fn w czasie proporcjonalnym do liczby n, a oto algorytm rozwiązujący problem z królikami dla dowolnej liczby miesięcy (w przykładzie dla 12 miesięcy):

// Plik źródłowy np. Unit1.cpp
//--------------------------------
#define MAX 65536
int F(int i)
{
 static int K[MAX];
 if(K[i] != 0) return K[i];
 int t = i + 1;
 if(i < 0) return 0;
 if(i > 1) t = F(i - 1) + F(i - 2);
 return K[i] = t;
}
//--------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
 ShowMessage("Po roku w klatce będzie: " + IntToStr(F(12)) + " królików.");
}
//--------------------------------

Ten przykład rozwiązuje problem z królikami, jednak podaje nieprawdziwe wyniki, dla F0 wynik będzie się równał 1, dla F1 wyniesie 2, a dla F2 wyniesie 3, a to się z kolei nie zgadza ze wzorem F0 = 0, F1 = F2 = 1, dlatego algorytm powinien mieć taką postać:

// Plik źródłowy np. Unit1.cpp
//--------------------------------
#define MAX 65536
int F(int i)
{
 static int K[MAX];
 if(K[i] != 0) return K[i];
 int t = i;
 if(i < 0) return 0;
 if(i > 1) t = F(i - 1) + F(i - 2);
 return K[i] = t;
}
//--------------------------------

W języku C++ w tablicy statycznej elementom przypisywane są na początku liczby 0, dlatego chcąc rozwiązać problem z królikami należy podać funkcji F jako argument nie liczbę 12, lecz liczbę większą o 2, czyli 14.

...powrót do menu.

Obliczanie całki metodą Monte Carlo.

Ta funkcja oblicza całkę z funkcji f po przedziale (x0,x1) przy użyciu funkcji rekurencyjnej. Algorytm działa poprawnie dla każdej zdefiniowanej przez użytkownika funkcji, lecz dokładność obliczeń jest zależna od wartości n. Żeby używać funkcji Power należy włączyć do projektu bibliotekę #include <math.hpp>

// Plik źródłowy np. Unit1.cpp
//--------------------------------

double f(double x)

{

 return(Power(x, 2));  // funkcja tu zdefiniowana może być dowolna, byle ciągła

}

//--------------------------------

long double suma(long int n, double x0, double dx)

{

 long double s = 0;

 if(n > 0) s = f(x0+((double)rand()/(double)(RAND_MAX + 1)*dx)) + suma(n-1, x0, dx);

 return s;

}

//--------------------------------

long double calka(double x0, double x1)

{

 long double s;

 double dx;

 dx = x1 - x0;

 n = 1000;

 s = dx * suma(n, x0, dx)/n;

 return s;

}
//--------------------------------

Opracował: Anatholius
 Przykładowy program - pobierz - ZIP 14 KB

...powrót do menu.

Obliczanie Całki przybliżoną metodą Reimanna (pomysł autora):

Poniższa funkcja również oblicza całkę z funkcji f po przedziale (x0,x1), lecz metodą opartą na ściśle matematycznej całce Reimanna. Jej dokładność również zależy od wartości n, lecz wynik całki jest dokładniejszy od wyniku metody Monte Carlo. Czas działania obydwu procedur jest taki sam. Żeby używać funkcji Power należy włączyć do projektu bibliotekę #include <math.hpp>

// Plik źródłowy np. Unit1.cpp
// Wersja nie rekurencyjna
//--------------------------------

double f(double x)

{

 return(Power(x, 2));  // funkcja tu zdefiniowana może być dowolna, byle ciągła

}

//--------------------------------

long double cr(double x0, double x1)

{

 long double s;

 double dx;

 dx = x1 - x0;

 s = dx * f(x0 + ((double)rand()/(double)(RAND_MAX + 1)*dx));

 return s;

}

//--------------------------------

long double calka(double x0, double xkon)

{

 long double s = 0;

 double dx;

 dx = xkon - x0;

 n = 1000;

 long double dt = dx * Power(n,-1);

 for(long int i = 1; i <= n; i++)

  s += cr(x0 + i * dt, x0 + (i + 1)*dt);

 return s;

}

//--------------------------------


// Plik źródłowy np. Unit1.cpp
// Wersja rekurencyjna
//--------------------------------

double cr(int i, double x0, double x1, int n)

{

 double s = 0;

 double dx;

 dx = x1 - x0;

 if(i > 0) s = calka(x0, x1) + cr(i - 1, x1, x1 + dx, n);

 return s;

}

//--------------------------------

double calkarimm (double x0,double xkon)

{

 double s=0;

 double dx;

 dx = xkon - x0;

 int n = 1000;

 double dt = dx * Power(n, -1);

 s = cr(n, x0, x0 + dt, n);

 return s;

}

//--------------------------------

Ponieważ funkcja zwraca wartość long double to aby móc tą wartość reprezentować w obiekcie typu np. TLabel lub TEdit należy ją przypisać do zmiennej typu double i taka wartość da się już przypisać do odpowiedniego obiektu.

// Plik źródłowy np. Unit1.cpp
// Wersja rekurencyjna
//--------------------------------

void __fastcall TForm1::Button1Click(TObject *Sender)

{

 x0 = 0; //początek przedziału

 x1 = 1; //koniec przedziału

 double c = calka (x0, x1);

 Edit1->Text = (AnsiString)c;

}

//--------------------------------

W programie przykładowym całka jest liczona dla funkcji x2 po przedziale (0,1). Całkę tą da się łatwo wyliczyć:

.

Wynosi ona 1/3, ale w zapisie dziesiętnym 0,3333… można więc porównywać dokładność wyliczanej przez program całki w zależności od metody i od wartości n.

Opracował: Anatholius
 Przykładowy program - pobierz - ZIP 14 KB

...powrót do menu.