To tylko jedna z 58 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
Wykład 1 Algorytm - formalny i jednoznaczny opis wynikania czynności w skończonej liczbie kroków (ciąg czynności).
Przykład: Znajdowanie d=nwd(x,y) x=120 y=68 120
52
36
20
4
68
16
12
8
4
Sposoby zapisu algorytmu:
Metoda 1.
Metoda 2
W celu zapisu algorytmu, możemy wykorzystać tzw. metajęzyk.
Jego elementami składniowymi są:
OBIEKTY
Liczbowe (liczby całkowite oraz niecałkowite)
Znakowe (znaki i ciągi znaków)
Logiczne
Różne zestawy powyższych
OPERACJE
Działania
Liczbowe (np. operacje arytmetyczne)
Na znakach
Relacyjne (porównania)
Logiczne
Inne
Instrukcja przypisania („:=”)
Instrukcje warunkowe
Jeżeli prawdziwy warunek W to wykonaj instrukcję I.
Jeżeli W to wykonaj ; w przeciwnym wypadku wykonaj Przypadek P spośród - forma uogólniona
Instrukcje iteracyjne
Dopóki W, to wykonuj I
Wykonuj I, dopóki W
Dla wykonuj I
Instrukcja skoku Idź do etykiety E
Instrukcja złożona początek ; koniec
Instrukcje wejścia/wyjścia
Wczytaj
Wypisz
DOBRY ALGORYTM TO ALGORYTM BEZ INSTRUKCJI SKOKU!
Przykład - zapis metodą 2: początek wczytaj (x,y); a:=x; b:=y; dopóki (ab), to wykonuj jeżli (ab), to wykonuj a:=a-b; wpp a:=b-a; wypisz (nwd(x,y)=a); koniec Wykład 2 Język programowania - umowny zbiór identyfikatorów, symboli i pojęć, które służą do wyrażenia algorytmu w formalnej formie zrozumiałej przez komputer.
TYPY DANYCH W JĘZYKU C stałe (ich wielkości nie zmieniają się w trakcie działania programu):
liczbowe (całkowitoliczbowe i niecałkowitoliczbowe) przykłady zapisu liczb: 12.34 12.34e2 system szesnastkowy - cyfry od 1 do 9 i od A do F.
znakowe (`a' - znak umieszczamy zawsze w pojedynczych apostrofach, również znaki specjalne `\n'- znak przejścia do nowej linii, ` ” ', ` \ ')
tekstowe (ciągi znaków np. „oa”)
zmienne proste liczbowe
całkowitoliczbowe:
int - intiger (2 lub 4 bajty)
long - long intiger; 2x dłuższy intiger (4 lub 8 bajtów)
(…)
… JEDNOKIERUNKOWA (POJEDYNCZO WIĄZANA)
Dynamiczna struktura danych, która składa się z ciągu elementów tego samego typu powiązanych wskaźnikami.
Przykład:
class lista
{
private:
struct element *głowa;
struct element
{
typ_klucza klucz;
struct element *nast;
} public:
lista();
~lista();
wstaw_element (typ_klucza, struct element*);
usun_element (struct element *);
znjadz_element (typ_klucza);
} ;
lista :: lista…
… straty ogólności), że elementy w tablicy są parami różne. Drzewo decyzyjne to struktura przedstawiająca schemat porównań wykorzystywanych przez dowolny algorytm sortowania wykorzystujący porównanie, każdy węzeł wewnętrzny w tym drzewie reprezentuje elementarne porównanie dwóch elementów tablicy, natomiast każdy węzeł końcowy to możliwa permutacja elementów tablicy A. Wykonanie algorytmu sortowania…
…. Na tej podstawie ograniczenie dolne na wysokości drzewa decyzyjnego, czyli długość najdłuższej ścieżki od korzenia do jednego z węzłów końcowych jest dolnym ograniczeniem na złożoność czasową pesymistyczną dowolnego algorytmu sortowania wykorzystującego porównanie.
Twierdzenie
Każde drzewo decyzyjne dla algorytmu sortowania wykorzystującego porównanie ma wysokość Dowód:
Każda spośród n! permutacji…
…; x++) tab[x]=x+2;
Wniosek:
6) Instrukcja skoku:
a) goto etykieta;
b) break; (przerwanie aktualnie wykonywanej pętli)
c) continue; (w pętli wraca do sprawdzenia warunku)
d) return; (powrót z funkcji)
Wykład 4
Funkcją w języku C nazywamy podprogram, z którym możemy komunikować się, przekazując mu argumenty oraz pobierając wynik.
Definicja funkcji:
typ_zwracanej_wartości nazwa_funkcji (lista argumentów…
…: punkt (void) punkt (); lub punkt (double, double, double);
Definicja konstruktora:
punkt :: punkt (double a, double b, double c)
{
x=a;
y=b;
z=c;
}
definicja w main: punkt D(1,2,3), E; //dla punktów D I E zostają uruchomione różne konstruktory
Destruktory
Funkcje składowe klasy o następujących własnościach:
nazwa destruktora to nazwa klasy poprzedzona znakiem „~”
destruktor nie zwraca żadnego wyniku…
…;
}
Operatory new (rezerwacja pamięci) i delete (zwolnienie pamięci)
Deklaracja:
wskaźnik = new typ;
wskaźnik = new typ [liczba obiektów];
delete wskaźnik;
przykład: int *w;
w=new int;
delete w;
ZADANIE KLASA W class wektor
{
private:
int n;
int t; //tymczasowość użyteczności obiektu
double *w;
public:
wektor (int);
~wektor();
wektor operator + (wektor);
wektor operator = (wektor);
}
wektor :: wektor (int m…
... zobacz całą notatkę
Komentarze użytkowników (0)