Reprezentacja danych numerycznych i algorytmy numeryczne

Liczby całkowite zapisuje się w postaci binarnej, używając kodu uzupełnionego do dwóch.

Liczbę rzeczywistą można zapisać w systemie pozycyjnym o dowolnej podstawie wykorzystując reprezentacje stałopozycyjną lub reprezentacyjną zmiennopozycyjną. Ponieważ niektóre liczby wymagają dużej ilości bitów do zapisuj stałopozycyjnego, większość komputerów wykorzystuje zmiennoprzecinkowe.

Wybrane algorytmy

Wieża Hanoi:

Przy tworzeniu algorytmów często korzystamy z zasady "dziel i zwyciężaj". Zasada ta została zastosowana miedzy innymi w algorytmach sortowania przez scalenie, szybkiego sortowania i wyszukiwania binarnego.

Sito Eratostenesa:

Algorytm sita Eratostenesa polega na usuwaniu z zadanego przedział wszystkich liczb złożonych, czyli eliminowaniu z niego liczb będących wielokrotnościami kolejnych liczb pierwszych - inaczej szukanie liczb pierwszych.

Tworzenie własnych modułów

W PASCAL:

Interfejs - opisuje stałe, zmienne, typy danych, procedury i funkcje. Jest ona publiczna.

interface { część modułu określająca interfejs }

implementacja - opisuje działanie procedur i funkcji. Są one prywatne dla modułu.

implementation { część implementacyjna modułu }

W C++:

plik nagłówkowy - odpowiednik interfejsu, zawiera deklaracje (h)

plik zawierający właściwy kod - odpowiedniki implementacji. (.cpp)

Programowanie modularne i obiektowe

Moduł to zbiór stałych, zmiennych, typów danych, procedur i funkcji, który oznaczony jest unikatową nazwą.

W języku C++ dyrektywa preprocesora #include określa, jakie pliki nagłówkowe mają zostać dołączone do kodu programu.

#include <iostream>    - standar. biblioteka C++
#include <stdio.h>       - standar. biblioteka C

<cmath> - funkcje matematyczne
<cstdio> - operacje wejścia/wyjścia
<cstdlib> - funkcje narzędziowe
<ctstring> - opreacje na łańcuchach znakowych
<ctime> - funkcja czasu/daty

Dynamiczne struktury danych

Zmienna, która nie przechowuje wartości, tylko adres, pod którym znajduje się inna zmienna, nazywana jest zmienna wskaźnikową.

Zmienne dynamiczne to zmienne , dla których pamięć jest przydzielana i zwalnia w trakcie trwania programu.

Drzewo binarne jest nieliniową strukturą danych, która składa się z wyróżnionego wierzchołka, zwanego korzeniem i dwóch poddrzew binarnych.
Wyróżnia się lewego i prawego syna wierzchołka.

Przetwarzanie danych typu struktualnego

Aby w programach można było przetwarzać dane różnego rodzaju, w języki C++ wprowadzono typ strukturalny.

Do tworzeniach takich struktur służy: struct. 

Aby odwołać się do pojedynczego pola, podajemy nazwę zmiennej typu rekordowego i nazwę pola rekordu, oddzielone od siebie kropką.

Losowanie danych i sprawdzanie ich poprawności

 (szyfrowanie, gry komputerowe, rzuty sześcienną kostką, grafika komputerowa) - przypadkowość


Symulacja rzutów sześcienną kostką do gry

#include <iostream>
#include <cstdlib>
using namepsace std;
int i;
int main ()
{
   for(i=0; i<10; i++)
        cout << "Wypadło: " << rand()%6+1 << endl;
   return 0;
}

Pisząc programy, należy zapewnić sprawdzenie poprawności wprowadzanych funkcji rand() i srand() - C++ - umożliwia to losowanie danych liczbowych przez komputer.
Dobry program powinien być odporny na błędy użytkownika. W momencie wprowadzenia przez niego bezsensownych danych, działanie programu nie powinno zostać w żaden sposób przerwane.

Operacje na stosie

stack - ang. stos

Potrzebny do wywoływania procedur i funkcji aktualnie wywoływanej instrukcji, kładziony na wierzch stosu. Zakończenie procedury lub funkcji ze stosu powoduje zdjęcie adresu i procesora wykonującego skok pod ten adres.


#include
using namespace std;
int Stack[100];
int SP;
void Init()
{
    SP=-1;
}
void Push(int x)
{
    Stack[++SP]=x;
}
int Pop()
{
     return Stack[SP--];
}

Odwrotna notacja polska - nie potrzebuje ona nawiasów, stosuje się argumenty i symbole operacji.

2 + 3         ->     2 3 +
4 * (2 + 3) ->    4 2 3 + *

Własne typy danych i stałe

  W języku C++ do deklaracji własnych typów danych służy słowo kluczowe typedef, po którym podajemy definicję typu, a następnie jego własną nazwę.

typedef char *TSlowo;
typedef TSlowo *TTablicaSlow;
typedef int TCalkowity;
TTablicaSlow Tab1, Tab2, Tab3;
TCalkowity N;

Korzystanie z własnych typów jest niekiedy wręcz wymagane!

Określenie z góry wszystkich typów danych wykorzystywanych w programie to element dobrego stylu programowania.

Typ okrojony  -  korzystamy wtedy, gdy z góry wiemy, że pewna dana w naszym programie powinna przyjmować wartości z określonego zakresu.

Typ wliczeniowy - korzystamy wtedy, gdy chcemy używać wartości mających znaczenie wyłącznie symboliczne.

Stałe:

w języku C++ kluczowe słowo to: const służy do deklarowania zmiennych, których wartość nie ulega zmianie. Wartości porządkowe można przypisać zmiennym w momencie ich deklarowania.

Wprowadzanie danych i wyprowadzenie wyników

Zmienne typu:

a) float a;                        rzeczywiste 
b) int x[50];                    całkowite
c) char c[21];                  znakowe
d) chard d;                      znakowe
e) unsigned short k;        całkowite

Typ danych  określa zbiór wartości, które mogą przyjmować zmienna, wyrażenia lub stała, a format danych określa sposób prezentacji danych określonego typu na urządzeniach wejścia/wyjścia.

Formatowanie danych:

setprecision(dokładność)
setiosflags(atrybut)
setw(szerokość)
setfill(znak-wypełnienia)
printf(format, dana1, dana2..)