Poprawność algorytmów i ich skończoność

Algorytm:

• całkowicie poprawny - wszystkie dane wejściowe spełniające warunki początkowe zostaną wyprowadzone wyniki spełniające warunki końcowe i obliczenia zostaną zakończone
• częściowo poprawny - wyniki są poprawne względem warunków początkowych i końcowych
• dobrze określony i uniwersalny - występują w nim polecenia, operacje zrozumiałe oraz kolejność jest jednoznacznie określona

Algorytm który nie jest skończony nie może zostać uznany za poprawny.

Powodem nieskończonego działania algorytmu może być np. błędnie określony warunek itd.

Metody sortowania

• Sortowanie Bąbelkowe jest to prosta metoda sortowania, pozwala poukładać elementy danej tablicy w kolejności rosnącej lub malejącej. Elementami tablicy mogą być cyfry albo litery. Algorytm sortowania bąbelkowego porównuje dwa sąsiadujące elementy tablicy. Jeżeli element n jest większy od elementu n+1, wtedy zostają one zamienione miejscami. Algorytm powtarza się w koło do czasu, kiedy nie zajdą żadne zmiany, czyli do czasu kiedy tablica nie zostanie posortowana. Sortowanie bąbelkowe jest to podstawowy algorytm i warto go znać.

• Sortowanie kubełkowe jest algorytmem przeznaczonym dla pewnej specyficznej grupy danych. Jest podobnym algorytmem do sortowania przez zliczanie. Algorytm jest wydajny w sytuacji, gdy dane rozmieszczone równomiernie. Nazwa wzięła się stąd, że dane wrzucamy do kubełków, które są już z definicji posortowane.

• Sortowanie przez wstawianie jest to rodzaj sortowania możemy porównać do układania kart pokerzysty. Pierwszą kartę wstawiamy w odpowiednie miejsce przesuwając pozostałe, następną także wstawiamy między odpowiednie karty i tak układamy zestaw kart. Sortowanie przez wstawianie można zaliczyć do atrakcyjniejszych algorytmów. ma swoje zalety: jest stabilny, bardzo dobrze zachowuje się w przypadku zbioru posortowanego lub częściowo posortowanego, prosty, dobrze radzi sobie z niedużymi zbiorami.

Zasada programowania i typy danych

Kilka podstawowych zasad programowania:

Zasada 1. 
Należy stosować zrozumiałe nazwy zmiennych. W nazewnictwie zmiennych należy przestrzegać norm danego języka.

Zasada 2. 
Warto zarezerwować pewne nazwy na zmienne używane wielokrotnie np. sterujące pętlami i,j; elementy zbiorów, liczby - a,x,liczba; liczba elementów w zbiorze - n,m.

Zasada 3. 
Dobrze jest sporządzić listy używanych zmiennych. Niektóre języki programowania obligują do sporządzenia takich list.

Zasada 4. 
Należy podzielić program  ma podprogramy realizujące mniejsze fragmenty zadania, zwłaszcza w złożonych problemach.
Zasada 5. 
Trzeba dbać o przejrzystość tekstu programu i zachowywać czytelność jego struktury.
Zasada 6. 
Należy pisać programy odporne na błędy użytkowników. Program powinien instruować swojego użytkownika o działaniach, jakie musi on podejmować oraz wyświetlać komunikaty dotyczące oczekiwanego rodzaju danych. Trzeba zabezpieczać program przed błędem typu zmiennych lub przed wprowadzeniem błędnych danych.

Typy danych w C++ :

• typy proste
• porządkowe (m.in. całkowity, logiczny, znakowy, wyliczeniowy)
• typy pochodne
• tablice
• struktury
• unie
• typy wslaźnikowe
• typy obiektowe

Funkcje zwracające w języku C++ i zasięgi zmiennej

Funkcja zwracająca wartość wylicza wartość i odsyła tę wartość do funkcji wywołującej, wtedy mówi się, że funkcja zwraca wartość.

Funkcje zwracające wartość muszą zawierać instrukcje return z wartością, która ma być zwrócona do funkcji wywołującej. Zwracana wartość może być stałą, zmienną lub wyrażeniem, np.

• return a*b;
• return Wynik;

Parametr - wartość przekazywana funkcji, a wartość zwracana to wartość przekazywana z funkcji.

W funkcjach czy procedurach parametry mogą być przekazywane na dwa sposoby:

• przez wartość: dla parametru formalnego i aktualnego o dwóch różnych nazwach zostaną zarezerwowane dwa miejsca w pamięci (o różnych adresach)
• są traktowane jako zmienne lokalne
• void nazwa_funkcji (lista parametrów)

Wartości zmiennych
x	y	a	b
Na początku procedury Wartości
3	8	3	8
Na końcu procedury Wartości
13	-2	3	8
Po powrocie do programu głównego
(zmienna przestała istnieć)	(zmienna przestała istnieć)	3	8

• przez zmienną (przez referencję): dla parametru formalnego i aktualnego o dwóch różnych nazwach zostanie zarezerwowane to samo miejsce w pamięci ( o tym samym adresie)
• void nazwa_funkcja (nazwa_typu &parametr1, nazwa_typu &parametr2)
• przed nazwą parametru należy umieścić znak &

Wartości zmiennych
x	y	a	b
Na początku procedury Wartości
3	8	3	8
Na końcu procedury Wartości
13	-2	13	-2
Po powrocie do programu głównego
(przestała istnieć nazwa zmiennej x)	(przestała istnieć nazwa zmiennej y)	13	-2

Ze względu na zasięgi zmiennej rozróżniamy zmienne:

• globalne
• lokalne

Parametry formalne przekazywane przez wartość w treści danej procedury lub funkcji są traktowane jak zmienne lokalne. Ewentualnie operacje wykonywane na tych parametrach wewnątrz procedury lub funkcji nie powodują zmian wartości odpowiadających im parametrów aktualnych.

Stosowanie procedur i funkcji w językach programowania

1. Modele programowania:

• liniowe - program jest ciągiem instrukcji języka programowania. Nie ma instrukcji warunkowych i nie wyodrębnia się podprogramów.
• struktularne - program ma odpowiednią strukturę, można wyodrębnić deklaracje (modułów, zmiennych i stałych), definicję podprogramów oraz bloki instrukcji, w tym sterujące wykonaniem programu (warunkowe, iteracyjne). Każda zmienna ma swój ściśle określony typ.
• modularne - jest to rozszerzenie podejścia proceduralnego, w którym powtarzające się w programie ciągi instrukcji zapisuje się w postaci procedur i funkcji, nadających się do wielokrotnego wykorzystania. Procedury i funkcje zebrane są w modułach, które zapisane są pod unikatową nazwą i mogą być wykorzystane w wielu programach.
• obiektowe - program jest definiowany jako zbiór obiektów, które posiadają określone właściwości (związane z obiektem dane) i metody (operacje, jakie można na obiekcie wykonać)
• zdarzeniowe - podobnie jak w programowaniu obiektowym, program to zbiór obiektów, jednak kolejność wykonywania instrukcji programu zależy od zaistnienia określonych zdarzeń (naciśnięcie przycisku, wprowadzenie danej, upływ czasu.

2. Programowanie zstępujące i wstępujące:

• Programowanie zstępujące - "z góry do dołu" polegające na zdefiniowaniu problemu ogólnego i podzielenie go na podproblemy, które są dzielone na jeszcze mniejsze podproblemy łatwe do rozwiązania.
• Programowania wstępujące - "z dołu do góry" polega na rozwiązaniu elementarnych problemów, które składa się w całość prowadzą do rozwiązania problemu.

3. Zalety stosowania podprogramów - procedur i funkcji:

• dzielenie zadania na mniejsze części
• zwiększenie czytelności i przejrzystości programu
• skrócenie programu - fragmenty programu które się powtarzają, są wyodrębnione w postaci podprogramów
• łatwiejsze wyszukiwanie błędów
• łatwiejsze poprawianie programu
• możliwość programowania zespołowego

Algorytm z pętlą zagnieżdżoną

1. Specyfikacja

• Zagnieżdżenie pętli, podobnie jak instrukcji warunkowej, polega na wywołaniu jednej pętli wewnątrz drugiej. Oznacza to, że na jedną iterację pętli zewnętrznej, zostanie wykonany cały przebieg pętli wewnętrznej. Instrukcje iteracyjne w C++ można dowolnie zagnieżdżać. Im więcej zagnieżdżeń tym większa złożoność obliczeniowa algorytmu.

2. Schemat blokowy

3. Listing programu:

• Przykładowe zastosowanie pętli zagnieżdżonej, przy tworzeniu programu komputerowego:

#include <iostream>

using namespace std;

int main ()

{

    cout << "Wysokosc: ";

    int n;

    cin>>n;

    for (int i=0; i<n;i++)

    {

        for(int j=0;j<i+1;j++)

        cout << "*";

        cout <<endl;

    }

    return 0;

}

Algorytm iteracyjny, iloczyn n liczb

1. Specyfikacja

• Iteracja polega na wielokrotnym powtarzaniu tej samej operacji (ciągu operacji).
• Iterację implementujemy stosując tzw. pętlę
• Z pętlą mamy do czynienia gdy w pewnym kroku algorytmu wracamy do jednego z wcześniejszych kroków co powoduje,że kroki te mogą zostać wykonane wiele razy.

2. Schemat blokowy

3. Listing programu

• Zapisywanie algorytmu iteracyjnego w postaci programu komputerowego:

#include <iostream>

using namespace std;

int main ()

{

   int i,a, iloczyn, n;

   cin >> n;

   iloczyn=1;

   for (i=0; i<n; i++)

   {

         cin >> a;

         iloczyn*=a;

    }

    cout << iloczyn;

    return 0;

}