To tylko jedna z 34 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)
(…)
… (pesymistyczna): gdzie: s(d) - liczba komórek pamięci potrzebnych do wykonania algorytmu dla d
Złożoność czasowa średnia: gdzie: p(d) - prawdopodobieństwo z jakim dane d pojawią się na wejściu
Przykład:
Dana jest tablica T[n]
Pytamy, czy dana ?
wyszukaj()
{ int i;
i=0;
while (i<n)
if (T[i]= =X) return 1;
else i++;
return 0;
}
T(n) = 1+3*n+1+1=3n+3
S(n) = n+1
załóżmy, że pierwsze wystąpienie x w T jest jednakowo…
… 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 musi się pojawić w jednym węźle końcowym. Drzewo o wysokości h ma co najmniej węzłów końcowych. Czyli wszystkie węzły końcowe muszą być na jednym poziomie.
SORTOWANIE PRZEZ ZLICZANIE (w czasie pesymistycznym liniowym) czyli nie korzystamy z porównań, dlatego złożoność może być liniowa.
Bierzemy liczby naturalne ograniczone, np. od 0 do 100
Przykład:
n=12
3 6 4 7 1 2 5 3 8 8 9 1
za m przypisujemy tworzymy tabelkę…
…; 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…
… programu:
Standardowa biblioteka wejścia/wyjścia: stdio.h
Podstawowe funkcje wejścia/wyjścia:
I) Dla pojedynczych znaków:
1) Pisania: putchar(char) - wypisanie znaku
2) czytania: char getchar() - pobranie znaku
II) Dla ciągów znaków:
1) Pisania: printf()
2) Czytania: scanf()
Deklaracja printf:
int printf(const char*format, arg1, arg2, ...);
znaki sprecjalne w formacie: %[flaga][szerokość][.precyzja…
... zobacz całą notatkę
Komentarze użytkowników (0)