POLITECHNIKA WARSZAWSKA
POLITECHNIKA WARSZAWSKA
Instytut Automatyki i Robotyki
Instytut Automatyki i Robotyki
ZASADY PROGRAMOWANIA STRUKTURALNEGO
ZASADY PROGRAMOWANIA STRUKTURALNEGO
( ZAP )
( ZAP )
Przedmiot prowadzony systemem obieralnym:
Przedmiot prowadzony systemem obieralnym:
Język programowania: Pascal lub C/C++
Język programowania: Pascal lub C/C++
Środowisko programistyczne: Delphi lub Builder C++
Środowisko programistyczne: Delphi lub Builder C++
Wykład 1 : Podstawowe pojęcia
Wykład 1 : Podstawowe pojęcia
1
POLITECHNIKA WARSZAWSKA
POLITECHNIKA WARSZAWSKA
Instytut Automatyki i Robotyki
Instytut Automatyki i Robotyki
ZASADY PROGRAMOWANIA STRUKTURALNEGO
ZASADY PROGRAMOWANIA STRUKTURALNEGO
( ZAP )
( ZAP )
TYGODNIOWY WYMIAR ZAJ
Ć
TYGODNIOWY WYMIAR ZAJ
Ć
Rok ak. Semestr W L P ECTS
Rok ak. Semestr W L P ECTS
2006/2007 II 1EE 2 -- 5
2006/2007 1 2 5
2006/2007 II -- -- 1 3
2006/2007 II 1 3
2
Program
Program
Zasady Programowania Strukturalnego
Instytut Automatyki i Robotyki
Autorzy programu:
dr hab. inż. Barbara Putz, dr inż. Andrzej Mazurek
Semestr I  II
Liczba godzin zajęć według planu studiów:
Wykład 15E
Laboratorium 30
Projektowanie 15
Liczba punktów kredytowych: 5 (sem. I) + 3 (sem. II)
3
Program wykładu
Program wykładu
Temat 1: Podstawowe pojęcia. Przedstawienie podstawowych pojęć i zagadnień
związanych z programowaniem komputerów. Pojęcia algorytmu, programu, kodu
wykonywalnego. Kompilacja i wykonanie programu. Struktura programu. Komentarze i
dokumentacja programu.
Temat 2: Proste programy. Nazwy. Stałe, typy, zmienne: całkowite, rzeczywiste, logiczne,
znaki i napisy. Klasyfikacja typów. Wyrażenia i funkcje. Instrukcje czytania, pisania, warunkowa,
złożona. Instrukcje cykliczne: pętla for, pętle sterowane warunkiem. Instrukcje przerywające
wykonanie pętli. Instrukcja wielokrotnego wyboru.
Temat 3: Tablice, rekordy i pliki. Tablice: deklaracja tablic, zmienna tablicowa i
indeksowana. Operacje na tablicach. Algorytmy sortowania i przeszukiwania w tablicach,
porównanie złożoności obliczeniowej. Rekordy (struktury) i operacje wykonywane na nich.
Definiowanie plików, zasady dostępu, operacje wejścia  wyjścia.
Temat 4: Podprogramy i rekurencja. Deklaracja i wywołanie podprogramu. Parametry
formalne i aktualne. Wiązanie parametrów, wykonanie podprogramu. Zasięg identyfikatorów,
zasłanianie. Rekurencja jako jedna z podstawowych technik konstruowania algorytmów. Zasada
działania rekurencji i warunek końca. Rekurencja bezpośrednia i pośrednia. Przykłady
algorytmów rekurencyjnych.
4
Program wykładu (c.d.)
Program wykładu (c.d.)
Temat 5: Wskaz
niki i listy. Zmienne dynamiczne i wskaz
niki. Przydział i zwalnianie pamięci.
Przykład tablicy rezerwowanej dynamicznie. Listy jednokierunkowe: zasada tworzenia,
podstawowe operacje na listach. Listy dwukierunkowe i cykliczne. Iteracyjne i rekurencyjne
algorytmy przetwarzania list.
Temat 6: Drzewa i grafy. Zasada tworzenia drzew i podstawowe operacje na drzewach z
wykorzystaniem rekurencji. Binarne drzewa sortowane (BST) i drzewa wyważone (AVL).
Zastosowanie drzew do przeszukiwania i sortowania baz danych. Podstawowe pojęcia teorii
grafów. Sposoby reprezentacji grafu, przeszukiwanie grafu, problem najkrótszej ścieżki.
Temat 7: Podsumowanie algorytmów. Przegląd zasad konstruowania algorytmów:
programowanie typu  dziel i zwyciężaj , programowanie dynamiczne, algorytmy z powrotami,
metody zachłanne.
5
Literatura
Literatura
Zalecane pozycje:
1. Barbara Putz, Paweł Wnuk: Informatyka 2 - Programowanie. OKNO PW, 2002.
2. Paweł Wnuk, Barbara Putz: Informatyka 2 - Programowanie. Wersja w języku C/C++. OKNO PW, 2004.
3. Sue Walmsley, Shirley Williams: Programowanie: Pascal w środowisku Delphi. ReadMe 2003.
4. Wiesław Porębski: Pascal. Wprowadzenie do programowania. Help 2002.
5. Bruce Eckel: Thinking in C++. Edycja polska. Helion 2002.
6. Jerzy Grębosz: Symfonia C++ standard. Tom I. Edition 2000.
7. Stephen Prata: Język C. Szkoła programowania. Robomatic 2001.
8. Niklaus Wirth: Algorytmy+struktury danych=programy. WNT 2002.
9. Piotr Wróblewski: Algorytmy, struktury danych i techniki programowania. Helion 2003.
10. Richard Neapolitan, Kumarss Naimipour: Podstawy algorytmów z przykładami w C++. Helion 2004.
Inne książki nt. Delphi i Buildera C++:
http://www.borland.pl/cgi-bin/ksiazki.exe/produkty
PODRECZNIKI PROGRAMOWANIA (Delphi, C/C++) dostępne online,
napisane dla studiów internetowych PW:
http://iair.mchtr.pw.edu.pl/bputz (>Zasady programowania)
Nalezy podac uzytkownika i haslo.
6
Programowanie
Programowanie
PROBLEM ALGORYTM PROGRAM
Algorytmizacja Kodowanie
Założony cel zajęć:
" Nabycie umiejętności algorytmizacji różnorodnych problemów
" Nabycie umiejętności kodowania algorytmów z wykorzystaniem języka
wysokiego poziomu
Środowisko programowania:
Delphi Personal wersja 6.0 lub 7.0
Borland C++ Builder Personal wersja 6.0
Możliwość skopiowania wersji Personal w pok. 307 lub ze strony
7
http://www.borland.pl
Dane do programu i wyniki z programu
Dane do programu i wyniki z programu
dane wyniki
program
8
Kompilacja i wykonanie programu
Kompilacja i wykonanie programu
" Błędy kompilacji  jeśli kompilator  nie rozumie programu z
ródłowego.
" Błędy wykonania programu  jeśli program po kompilacji nie daje się wykonać.
" Błędy logiczne  jeśli program wykonuje się nieprawidłowo.
9
Konsolidacja programu (linkowanie)
Konsolidacja programu (linkowanie)
10
Prezentacja algorytmu
Prezentacja algorytmu
Algorytmy przedstawiane są z różnym stopniem szczegółowości. Najczęściej
stosuje się: opis słowny lub sieci działań (schematy blokowe).
Symbole graficzne do budowy sieci działań
Przykład
Koniec
Początek
Oznaczenie początku, końca sieci działań
A
ączniki dzielące sieć działań na fragmenty
5 5
Opis realizowanej w algorytmie
Realizacja operacji
czynności
Tak Nie
Rozgałęzienie - przejście do części
Warunek
prawdziwy ?
algorytmu wynikającej ze spełnienia warunku
Odpowiednio: wczytanie lub wydrukowanie
WE WY
a, b, c a, b, c
wartości: a, b, c
11
Przykład sieci działań
Przykład sieci działań
Sprawdzić, czy wczytana liczba całkowita N>3 jest pierwsza (dzieli się tylko przez jeden i
siebie). (Przykład z: D. van Tassel:  Praktyka programowania . WNT Warszawa)
Początek
WE
N
Tak
reszta z dzielenia N przez 2 = 0
k 3
Tak
reszta z dzielenia N przez k = 0
WY
N,  - nie pierwsza 
Nie
Koniec
k k +2
k  zmienna pomocnicza
Nie
k >
N
Tak
WY
N,   pierwsza 
12
Koniec
Program w Pascalu
Program w Pascalu
Program jest TEKSTEM (ciagiem znaków), dla którego zdefiniowano:
" ALFABET ( dopuszczalny ciag znaków )
" SLOWA KLUCZOWE ( predefiniowane, majace specjalne znaczenie )
" DEFINICJE i DEKLARACJE oraz INSTRUKCJE
STRUKTURA PROGRAMU
program nazwa ; �! naglówek programu
�!
�!
�!
definicje i deklaracje �! czesc opisowa
�!
�!
�!
begin
blok
ciag instrukcji czesc wykonawcza
end .
13
Program w C/C++
Program w C/C++
Program jest TEKSTEM (ciagiem znaków), dla którego zdefiniowano:
" ALFABET ( dopuszczalny ciag znaków )
" SLOWA KLUCZOWE ( predefiniowane, majace specjalne znaczenie )
" DEFINICJE i DEKLARACJE oraz INSTRUKCJE
STRUKTURA PROGRAMU
# include dołączanie plików nagłówkowych bibliotek
.....
using namespace std; �! udostepnienie nazw ze standardowych bibliotek
�!
�!
�!
int main ( )
{
definicje i deklaracje
funkcja main (główna) - musi być w programie
instrukcje
}
.....
inne funkcje - niekonieczne
14
Przykłady programów
Przykłady programów
1) Najprostszy program 2) Wydrukowac najwieksza wartosc sposród dwóch wczytanych:
w Pascalu:
program max_liczba;
var x, y : real;
begin
begin
end .
readln( x,y);
if x>y then writeln (x) else writeln (y)
end .
w C/C++:
# include
using namespace std;
int main ( )
int main ( )
int main ( )
int main ( )
{
{
{
{
int main ( )
{
}
}
}
}
float x, y;
cin >> x >> y;
if (x>y)
cout << x << endl;
else
cout << y << endl;
}
15
Przykłady programów c.d.
Przykłady programów c.d.
3) Wczytac promien kola, a nastepnie obliczyc i wydrukowac jego obwód i pole.
program kolo;
const pi=3.14159;
var r, obwod, pole : real;
begin
write( Podaj promien kola :  );
readln(r);
Pascal
obwod:=2*pi*r;
pole:=pi*r*r;
writeln ( Obwod =  ,obwod,  Pole =  , pole )
end .
#include
using namespace std;
int main ( )
{
const pi=3.14159;
float r, obwod, pole;
C/C++
cout << "Podaj promien kola" << endl;
cin >> r;
obwod = 2*pi*r;
pole = pi*r*r;
cout << "Obwod = " << obwod << " Pole = " << pole << endl;
16
}
Szkielety aplikacji konsolowych
Szkielety aplikacji konsolowych
program Project1;
{$APPTYPE CONSOLE}
uses
SysUtils;
begin Delphi 7
{ TODO -oUser -cConsole Main : Insert code here }
end.
//---------------------------------------------------------------------------
#pragma hdrstop
//---------------------------------------------------------------------------
#pragma argsused
Builder C++
int main(int argc, char* argv[ ] )
{
return 0;
}
//---------------------------------------------------------------------------
17
Przykłady aplikacji konsolowych
Przykłady aplikacji konsolowych
zatrzymujących wyniki na ekranie
zatrzymujących wyniki na ekranie
program przyklad1;
{$APPTYPE CONSOLE}
uses
SysUtils;
begin Delphi 7
writeln ( Wcisnij Enter );
readln
end.
//---------------------------------------------------------------------------
#pragma hdrstop
//---------------------------------------------------------------------------
#pragma argsused
#include
#include
using namespace std;
int main(int argc, char* argv[ ]) Builder C++
{
cout <<"Wcisnij jakis klawisz"< getch ();
return 0;
}
18
//---------------------------------------------------------------------------
Komentarze w Pascalu i Delphi
Komentarze w Pascalu i Delphi
Są ignorowane przez kompilator, służą wyłącznie osobie czytającej tekst programu.
Zapisuje się je w nawiasach klamrowych {....} . Ewentualnie można je też zapisywać
wewnątrz par znaków (*.....*), co jest przydatne w przypadku komentarzy
zagnieżdżonych.
Przykład komentarzy zagnieżdżonych:
(* Zobaczymy, co się stanie, jeśli w programie nie będzie instrukcji readln na końcu.
readln {to oznacza: poczekaj, aż użytkownik wciśnie Enter;
ta instrukcja zatrzymuje więc działanie programu,
dzięki czemu wyniki pozostają na ekranie, dopóki nie wciśniemy
Entera}
*)
Uwaga 1: Jeśli zaraz po nawiasie klamrowym { występuje znak $, to mamy do czynienia z tzw.
dyrektywą dla kompilatora (która ma określone znaczenie), a nie komentarzem, np.
{$APPTYPE CONSOLE}  oznacza, że kompilator ma utworzyć aplikację konsolową.
Uwaga 2: W Delphi dopuszczalne są również komentarze pomiędzy znakami // a końcem
linii:
readln // ta instrukcja oznacza oczekiwanie na wciśnięcie Entera
19
Komentarze w C/C++
Komentarze w C/C++
Są ignorowane przez kompilator, służą wyłącznie osobie czytającej tekst programu.
Zapisuje się je pomiędzy wewnątrz par znaków /*.....*/, cp pozwala tworzyć komentarze
złożone z wielu linii, lub pomiędzy znakami // a końcem linii.
Dwa różne typy komentarzy pozwalają tworzyć komentarze zagnieżdżone.
Przykład komentarzy i komentarzy zagnieżdżonych:
#include // ten plik nagłówkowy należy dołączyć, jeśli chcemy używać instrukcji getch()
/* Zobaczymy, co się stanie, jeśli w programie nie będzie instrukcji getch(); na końcu.
getch(); // to oznacza: poczekaj, aż użytkownik wciśnie jakiś przycisk;
// ta instrukcja zatrzymuje więc działanie programu,
// dzięki czemu wyniki pozostają na ekranie, dopóki nie wciśniemy
// jakiegoś przycisku
*/
20
21