Najważniejsze własności algorytmów, ich skończoność i poprawność

1. Najważniejsze własności algorytmów

Algorytm – w matematyce oraz informatyce to skończony, uporządkowany ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego zadania.Podstawowe cechy

Cechy algorytmów:
- poprawność (algorytm daje dobre wyniki),
- jednoznaczność (daje takie same wyniki przy takich samych danych),
- skończoność (wykonuje się w skończonej ilości kroków),
- sprawność (czasowa - szybkość działania i pamięciowa - "zasobożerność")

Sposoby prezentacji

Najbardziej przejrzystym sposobem prezentacji są schematy blokowe - narzędzia nakierowane na prezentację kolejnych czynności w projektowanym algorytmie.

2. Poprawność algorytmów

Co to znaczy, że algorytm działa poprawnie? Intuicja podpowiada nam, że chodzi tu o to, by dla dowolnych danych uzasadnić zgodność uzyskanych wyników z zamierzeniami. Aby jednak taką zgodność ustalić ponad wszelką wątpliwość, musimy jasno sformułować intencje, podać tzw. specyfikację algorytmu.

Specyfikacją algorytmu nazywać będziemy parę własności: <wp, wk>, gdzie wp jest warunkiem początkowym, a wk warunkiem końcowym. Intuicyjnie, warunek początkowy to ten, który mają spełniać dane początkowe, a warunek końcowy to ten, który ma być spełniony po wykonaniu algorytmu. Ogólnie, oba warunki powinny opisywać zależności między zmiennymi przed i po wykonaniu algorytmu.

3. Skończoność algorytmów

Algorytm jest skończony, jeżeli gwarantuje wyznaczenie wyniku w skończonej liczbie kroków.

ALGORYTM KTÓRY NIE JEST SKOŃCZONY NIE MOŻE ZOSTAĆ UZNANY ZA POPRAWNY.

Algorytmy sortowania

Sortowanie danych jest jednym z podstawowych problemów programowania komputerów, z którym prędzej czy później spotka się każdy programista. Poniżej są tylko nieliczne dziedziny, w których występuje potrzeba sortowania danych:

• sport - wyniki uzyskane przez poszczególnych zawodników należy ułożyć w określonej kolejności, aby wyłonić zwycięzcę oraz podać lokatę każdego zawodnika.
• bank - spłaty kredytów należy ułożyć w odpowiedniej kolejności, aby wiadomo było kto i kiedy ma płacić odsetki do banku.
• grafika - wiele algorytmów graficznych wymaga porządkowania elementów, np. ścian obiektów ze względu na odległość od obserwatora. Uporządkowanie takie pozwala później określić, które ze ścian są zakrywane przez inne ściany dając w efekcie obraz trójwymiarowy.
• bazy danych - informacja przechowywana w bazie danych może wymagać różnego rodzaju uporządkowania, np. lista książek może być alfabetycznie porządkowana wg autorów lub tytułów, co znacznie ułatwia znalezienie określonej pozycji.

Metoda sortowania przez wybór. 

Polega ona na wyszukaniu w ciągu liczby największej (lub najmniejszej - zależności od  przyjętego porządku), ustawieniu jej na początku ciągu, a następnie powtarzaniu tych czynności z pominięciem już uporządkowanych elementów. 

Metoda sortowania bąbelkowego. 

Polega na porównywaniu parami kolejnych liczb i przestawianiu ich, jeśli występują w niewłaściwej kolejności. 

Metoda sortowania pozycyjnego.

W algorytmie tym według porządku alfabetycznego metodą pozycyjną porównywane są litery umieszczone na tych samych pozycjach, począwszy od ostatniej litery w najdłuższym słowie (słowach). 

Sposoby przekazywania parametrów

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


1. PRZEKAZYWANIE PARAMETRÓW PRZEZ WARTOŚĆ 

Najpopularniejszą metodą budowania funkcji jest przekazywanie argumentów przez wartość. Funkcja musi zawierać argumenty wraz z ich typami, oddzielone przecinkami. Kiedy przekazujemy do funkcji jakąś zmienną, zostaje utworzona w pamięci jej kopia. Wszystko co dzieje się wewnątrz funkcji odbywa się tak naprawdę na kopii zmiennej przekazanej w argumencie poprzez wartość.
W takim wypadku konieczne staje się zwrócenie odpowiedniej wartości za pomocą return i przypisanie zwróconej wartości do odpowiednich zmiennych. Jeżeli funkcja nie zwróci żadnej wartości, wtedy jej wywołanie może stać się bezcelowe. Utworzona kopia zmiennej, nawet jeżeli zostanie zmodyfikowana, zostanie usunięta z pamięci po zakończeniu funkcji.

Przykład:
#include <iostream>
using namespace std;
int a,b;
void Wartosci (int x, int y)

{ 

x=x+10;

y=y-10;

cout << "x=" << x << endl;

cout << "y=" << y<< endl;

}

int main()

{

cin >> a >> b;

Wartosci(a,b);

cout << a=" << a << endl;

cout << "b=" << b << endl;

return 0;

}

2. PRZEKAZYWANIE PARAMETRÓW PRZEZ ZMIENNĄ - PRZEZ REFERENCJĘ 

W procedurze lub funkcji, w której parametry przekazywane są przez zmienną (przez referencję), operacje wykonywane w tej treści procedury na parametrach formalnych w momencie wywołania danej procedury powodują wykonanie tych operacji na odpowiednich parametrach aktualnych. 

Przykład: 

#include <iostream>
#include <cstdlib>
using namespace std;
void zwieksz_kilka(int *dl, int *wys, int *waga)
{
*dl = *dl * 2;
*wys = *wys * 2;
*waga = *waga * 2;
}
int main()
{

int dlugosc = 125;
int wysokosc = 300;
int waga = 20;

int *wsk_dlugosc = &dlugosc;
int *wsk_wysokosc = &wysokosc;
int *wsk_waga = &waga;
zwieksz_kilka(wsk_dlugosc, wsk_wysokosc, wsk_waga);
cout << dlugosc << endl;
cout << wysokosc << endl;
cout << waga << endl;
system("pause >nul");
return 0;
}

Zasięg zmiennej

1. Ze względu na zasięg zmiennej  rozróżniamy zmienne globalne i lokalne. Jeżeli zmienna zadeklarowana jest w ciele klasy, na przykład formatki, to podział ten przechodzi na prywatny i publiczny.
Zmienna lokalna dostępna jest w czasie wykonywania tego fragmentu kodu, do którego jest przypisana. W naszym przypadku będzie, to występować w ciele funkcji zdarzeń używanych komponentów. Zmienna globalna, ma zasięg w całym kodzie programu.

2. ZMIENNA GLOBALNA  I JEJ STOSOWANIE

Zaletą zmiennych globalnych jest to, że są one widoczne w całym programie. Nie miało to dużego znaczenia w przypadku naszych dotychczasowych programach, jednak nabierze bardzo dużego znaczenia, kiedy przedstawię Ci pojęcie funkcji w C++.

Zmienne globalne deklaruje się (i ewentualnie inicjalizuje) pomiędzy blokiem dołączonych plików nagłówkowych a funkcją main. Ponieważ są to zwykłe zmienne (mają tylko dodatkowe właściwości), to deklaracja, inicjalizacja oraz posługiwanie się tymi zmiennymi wygląda dokładnie tak samo, jak to robiliśmy w dotychczasowych programach.

Ponieważ zmienne globalne są widoczne w całym programie, zatem są również widoczne wewnątrz funkcji main. Oznacza to, że wewnątrz funkcji main (oraz wszystkich innych funkcji), możemy dokonywać wszystkich operacji jakie są tylko możliwe dla zmiennej danego typu.

Przykład programu: 

 #include <iostream> 

using namespace std;

int i;

void Usmiechy()

{

int i;

for (i=0; n i++) cout << ":-)";

}

int main()

{

i=10;

Usmiechy();

cout << i;

return 0;

}

3. ZMIENNA  LOKALNA I JEJ ZASTOSOWANIE
Nazwy zmiennych globalnych muszą być między sobą różne. Nie jest możliwe utworzenie zmiennych globalnych o tej samej nazwie. Sprawia to, że w przypadku dużej liczby zmiennych, należy tworzyć coraz dłuższe nazwy zmiennych, których zapamiętanie staje się coraz bardziej uciążliwe.
Poza tym, ponieważ zmienne globalne są dostępne wszędzie, można je zatem w dowolnym miejscu zmienić. Oczywiście może to stanowić zaletę, jednak w większych programach jest tak naprawdę wadą. Nasza zmienna może bowiem zostać zmieniona w dowolnym miejscu programu, często przez przypadek.
Nawet jeśli program piszemy sami, możemy się łatwo zapomnieć lub pomylić, a co dopiero gdy program pisze kilku programistów. Wówczas prawdopodobieństwo przypadkowej i niechcianej zmiany wartości zmiennej globalnej jest bardzo duże, a znalezienie takiego błędu w programie, który liczy kilka lub kilkanaście tysięcy linii, może zająć zbyt dużo cennego czasu.
Ostatnią ważną kwestią jest to, że ponieważ zmienne globalne istnieją przez cały czas działania programu, to przez cały czas zajmują miejsce w pamięci operacyjnej. W przypadku dużej liczby zmiennych lub bardzo rozbudowanych programów, nie można oczywiście dopuszczać do przechowywania wszystkich zmiennych przez cały czas działania programu w pamięci, dlatego też należy szukać innych rozwiązań.
W tym momencie dobrze by było, gdyby udało Ci się zapamiętać - zmienne globalne mają zaletę, bo są wszędzie dostępne, ale przez to ich używanie jest bardzo ryzykowne, gdyż wszędzie może nastąpić zmiana ich wartości. Mamy zatem połączenie teoretycznej wygody z dużym niebezpieczeństwem.
Wierzę, że w ten oto sposób zachęciłem Cię do przeczytania dalszej części lekcji i zapoznania się ze zmiennymi lokalnymi, które są znacznie wygodniejsze w użyciu.

Nawiasy klamrowe wyznaczają zasięg lokalny.

  Przykłąd programu:
#include <iostream> 

using namespace std;

int k, i;

void Usmiechy()
{
int k;
cin >> k;
if (k>0) for (i=0; i<20; i++) cout << ":-)";
else for (i=0; i<20; i++) cout << ":-(";
}

int main()

{

i=10;

Usmiechy();

cout << i;

return 0;

}

Funkcje niezwracające wartości w języku C++

1. Aby w jezyku C++ wywołać funkcję niezwracającą wartości (typu void) , należy wpisać jej nazwę w odpowiednim miejscu funkcji głównej - main - a w przypadku funkcji a parametrami - dodatkowo podać parametry aktualne.


2. Wywoływanie funkcji ma postać:
nazwa_funkcji (lista parametrów aktualnych);

3. Przykład takiego programu:
#include <iostream>
using nameapace std;
int i;
void Usmiechy()
{
for (i=0; i<20; i++)
cout << ":-)";
}
int main ()
{
cout << "usmiechnij sie: " << endl;
Usmiechy();
return 0;
}


4. Stosowanie takiej funkcji z parametrem:
#include <iostream>
using nameapace std;
int i;
void Usmiechy(int n)
{
for (i=0; i<n; i++)
cout << ":-)";
}
int main ()
{
cout << "podaj liczbe usmiechow: ";
cin >> m;
cout << "usmiechnij sie: " << endl;
Usmiechy(m);
return 0;
}

Funkcje zwracające wartość w języku C++

1. Każda funkcja posiada trzy własności:

- zwraca dane (lub nie jeśli tego nie chcemy);
 - posiada swoją nazwę;
- może posiadać dowolną liczbę argumentów wejściowych (lub może nie mieć żadnego, jeśli tego nie chcemy).

2. Funkcja zwracająca wartość - wylicza wartość i odsyła tę wartość do funkcji wywołującej. Mówimy, że funkcja zwraca wartość. 

Są to funkcje, które w swojej budowie zawierają słowo return.

opis_typu nazwa_funkcji (lista parametrów formalnych)
{
instrukcje;
return zwracana_wartość;
}

3. Wywołanie funkcji zwracającej wartość
Aby użyć takiej funkcji można:
1) wywołać ją umieszczając jej wynik w zmiennej
zmienna = nazwa_funkcji(lista parametrów)

2) wykorzystać jako element wyrażenia lub instrukcji
cout << nazwa_funkcji(lista parametrów)

4. Przykłady programu: 

#include <iostream>

using namespace std;

int x, y;

int SumaKwadratow (int a, int b)

{ 

return a*a+b*b;

}

int main()

{ 

cout << "wprowadz skladniki" << endl;

cin >> x >> y;

cout << SumaKwadratow(x,y);

return 0;

}

____________________________________

#include <iostream> 

using namespacd std;

int x,y;

int SumaKwadrat ()

{

return x*x+y*y 

} 

int main ()

{ 

cin >> x>> y;

cout << SumaKwadrat();

return 0;

}

Stosowanie procedur i funkcji w językach

1. Programowanie zstępujące i wstępujące.
Programowanie zstępujące (projektowanie zstępujące, ang. top-down design) – rozwiązanie programistyczne polegające na zdefiniowaniu problemu ogólnego poprzez podzielenie na podproblemy, które są dzielone na jeszcze mniejsze podproblemy aż do rozwiązań oczywistych, łatwych do zapisania. Następnie złożenie z rozwiązań podproblemów niższego rzędu rozwiązań problemów wyższego rzędu aż do całkowitego rozwiązania problemu

Programowanie wstępujące - oznacza rozpoczęcie pracy z interfejsem, zaimportowanie go do modułu, a następnie, jeśli to konieczne, zmodyfikowanie go w edytorze interfejsów.
Poniższa ilustracja przedstawia to programowanie:

2. Zalety stosowania podprogramów - procedur i funkcji

Stosowanie procedur i funkcji umożliwia: 

- dzielenie zadania na mniejsze części 

- każda może być realizowana w oddzielnej procedurze lub funkcji. 

-wprowadzenie porządku do programu

- zwiększenie jego czytelności i przejrzystości. 

-łatwiejsze wyszukiwanie błędów i dokonywanie poprawek 

- w procedurze lub w funkcji można zlokalizować błędy szybciej niż na długiej liście instrukcji programu głównego. 

-programowanie zespołowe 

- po uzgodnieniu postaci procedur lub funkcji każdy z członków zespołu może zająć się pracą się nad "swoimi" procedurami lub funkcjami. Zaletami programowania strukturalnego są szczególnie widoczne przy pisaniu dużych programów,rozwiązujących złożone problemy

3. Modele programowania:
- liniowe,



- strukturalne -  paradygmat programowania opierający się na podziale kodu źródłowego programu na procedury i hierarchicznie ułożone bloki z wykorzystaniem struktur kontrolnych w postaci instrukcji wyboru i pętli.
- modularne - 

- obiektowe - 

- zdarzeniowe -