From Tomasz Żok

WprowadzenieDoInformatyki: MetodyNumeryczne

Reprezentacja stałoprzecinkowa

• Na wcześniejszych zajęciach mówiliśmy o tym, że wartość liczby binarnej liczymy następująco:

• Można jednak indeksować bity inaczej (czyli nadać też inne wartości wykładnika potęgi przy liczbie 2) co pozwoli na użycie tej samej liczby bitów do reprezentacji zupełnie innej liczby:

• Jest to jednak nienajlepszy pomysł. Mając do dyspozycji np. 8 bitów, mogliśmy wcześniej zapisać liczby z przedziału od 0 do {$ 2^8 - 1 = 255 $}. Przeznaczając 4 bity na część całkowitą, a 4 na ułamkową, ogranicza to możliwość zapisu liczby jedynie do przedziału od 0 do {$ 2^3 + 2^2 + 2^1 + 2^0 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{16} = 15.9375 $}. Co więcej, dwie liczby rzeczywiste tak zapisane różniłyby się co najwyżej o {$ \frac{1}{16} $}. Żadnych mniejszych różnic nie moglibyśmy przedstawić.

Reprezentacja zmiennoprzecinkowa

• W zmiennoprzecinkowej reprezentacji, liczby rzeczywiste przedstawiane są następująco: {$$ x = -1^s \cdot 2^c \cdot m $$}
  • x - wejściowa liczba rzeczywista
  • s - bit znaku (wartość 0 lub 1)
  • c - cecha, odpowiada za część całkowitą
  • m - mantysa, odpowiada za część ułamkową
• Zauważyć trzeba, że cecha opisuje wykładnik potęgi liczby 2, a nie część całkowitą bezpośrednio. Jeśli więc cecha przyjmowałaby wartości 0, 1, 2, 3, ... to część całkowita liczby będzie kolejno równa 1, 2, 4, 8, ...
• Mantysa jest jednak ułamkowa, a w reprezentacji zmiennoprzecinkowej poszczególne części są mnożone. Dlatego też można przedstawić np. {$ 3 = 2^2 \cdot \frac{3}{4} $} (cecha = 2, mantysa = {$ \frac{3}{4} $}) albo {$ 7 = 2^3 \cdot \frac{7}{8} $} (cecha = 3, mantysa = {$ \frac{7}{8} $}).
• Podobnie przedstawia się dowolne liczby rzeczywiste np. {$ 6.5 = 2^3 \cdot \frac{13}{16} $} (cecha = 3, mantysa = {$ \frac{13}{16} $})
• Oczywiście nie wszystkie liczby rzeczywiste da się tak przedstawić. Są one wówczas reprezentowane jako przybliżenia np. wpisanie liczby 6.1 tak naprawdę wpisze do rejestru wartość 6.09999990463256835936
• Jak dokładnie reprezentowana jest dowolna liczba rzeczywista w komputerze można zobaczyć na tym formularzu oraz można podejrzeć  kod źródłowy w asemblerze

Liczby rzeczywiste w języku C

• Deklaracja zmiennych:
  float f;
  double d;

  [$[Get Code]]
• Wczytanie/wypisanie tych zmiennych:
  scanf("%f", &f);
  scanf("%lf", &d);
  
  printf("%f\n", f);
  printf("%lf\n", d);

  [$[Get Code]]

Rekurencja

• Funkcja rekurencyjna to taka, która wywołuje samą siebie np.
  int f(int n) {
      if (n == 0) {
          return 1;             // warunek graniczny wyjścia z rekurencji
      } else {
          return 1 + f(n - 1);  // wywołanie rekurencyjne
      }
  }

  [$[Get Code]]
• W niektórych sytuacjach ułatwia to zaprojektowanie rozwiązania np. przeszukiwanie drzewa BST można zaimplementować rekurencyjnie
• Trzeba bezwzględnie pamiętać o prawidłowym umieszczeniu warunku wyjścia z rekurencji. Bez tego, funkcja raz wywołana będzie nieskończenie wywoływać samą siebie (w praktyce skończą się zasoby typu przydzielona pamięć i program się zakończy z błędem)
• Rekurencja bywa kosztowna szczególnie jeśli funkcja ma wiele argumentów i/lub zmiennych lokalnych
• Przykład zależności rekurencyjnej odwołującej się do dwóch elementów wstecz to ciąg Fibonacciego:{$$ F_n = \begin{cases}0 & \mbox{dla } n = 0 \\ 1 & \mbox{dla } n = 1 \\ F_{n-1} + F_{n-2} & \mbox{dla } n > 1 \end{cases} $$}
  int fib(int n) {
      if (n == 0) {
          return 0;
      } else if (n == 1) {
          return 1;
      } else {
          return fib(n - 1) + fib(n - 2);
      }
  }

  [$[Get Code]]

Zadania na laboratorium

1. Symbol Newtona: {$$ {n \choose k} = \begin{cases}1 & \mbox{dla } k = 0 \mbox{ lub } k = n \\ {n - 1 \choose k - 1} + {n - 1 \choose k} & \mbox{dla } 0 < k < n\end{cases} $$}
   #include <stdio.h>
   
   int newton(int n, int k) {
      ...
   }
   
   int main() {
       int n, k;
       scanf("%d %d", &n, &k);
       int y = newton(n, k);
       printf("%d\n", y);
       return 0;
   }

   [$[Get Code]]
2. Wielomian Legendre'a: {$$ P_{n}(x) = \begin{cases}1 & \mbox{dla } n = 0 \\ x & \mbox{dla } n = 1 \\ \frac{2n+1}{n+1}P_{n-1}(x) - \frac{n}{n+1}P_{n-2}(x) & \mbox{dla } n > 1\end{cases} $$}
   #include <stdio.h>
   
   double legendre(double n, double x) {
      ...
   }
   
   int main() {
       double n, x;
       scanf("%lf %lf", &n, &x);
       double y = legendre(n, x);
       printf("%lf\n", y);
       return 0;
   }

   [$[Get Code]]
3. Wielomian Hermite'a: {$$ H_{n}(x) = \begin{cases}1 & \mbox{dla } n = 0 \\ 2x & \mbox{dla } n = 1 \\ 2x H_{n-1}(x) - 2(n-1) H_{n-2}(x) & \mbox{dla } n > 1\end{cases} $$}
   #include <stdio.h>
   
   double hermite(double n, double x) {
      ...
   }
   
   int main() {
       double n, x;
       scanf("%lf %lf", &n, &x);
       double y = hermite(n, x);
       printf("%lf\n", y);
       return 0;
   }

   [$[Get Code]]