dr inż. Tadeusz BURAK
1
Algorytm Euklidesa
Algorytm Euklidesa
Algorytm Euklidesa to algorytm znajdowania
największego wspólnego dzielnika (NWD)
dwóch liczb naturalnych. Nie wymaga on
rozkładania tych liczb na czynniki pierwsze.
Algorytm
dane są dwie liczby naturalne a i b
jeśli b jest równe zeru, to NWD jest równe a
w przeciwnym wypadku oblicz c jako resztę
z dzielenia a przez b
zastąp a przez b, zaś b przez c i zacznij od
początku.
dr inż. Tadeusz BURAK
2
Algorytm Euklidesa
Algorytm Euklidesa
Przykład
Przykład
NWD liczb 1029 i 42 wynosi 21
obliczany jest następująco:
a
b
c
1029
42
21
42
21
0
21
0
dr inż. Tadeusz BURAK
3
Sortowanie
Sortowanie
metodą przez porównanie sąsiednich
metodą przez porównanie sąsiednich
elementów
elementów
32
24
45
-13
26
24
32
45
-13
26
24
32
45
-13
26
24
32
-13
45
26
24
32
-13
26
45
dr inż. Tadeusz BURAK
4
Sortowanie 2
Sortowanie 2
24
32
-13
26
45
24
32
-13
26
45
24
-13
32
26
45
24
-13
26
32
45
dr inż. Tadeusz BURAK
5
Sortowanie 3
Sortowanie 3
24
-13
26
32
45
-13
24
26
32
45
-13
24
26
32
45
dr inż. Tadeusz BURAK
6
Sortowanie 4
Sortowanie 4
-13
24
26
32
45
-13
24
26
32
45
32
24
45
-13
26
Wynik
Dane
wejściowe
dr inż. Tadeusz BURAK
7
Sortowanie schemat
Sortowanie schemat
blokowy
blokowy
START
We: N,L
1
,L
2
...L
N
Do tablicy: (1),A(2),
…,A(N)
J=2
ZAMIEŃ
A(J-1) z A(J)
J > N - I
I = N -1
A(J-1) > A(J)
J =J + 1
I =I + 1
Tak
Nie
Nie
I=1
dr inż. Tadeusz BURAK
8
Miejsce zerowe funkcji
Miejsce zerowe funkcji
metoda bisekcji – podziału
metoda bisekcji – podziału
połówkowego
połówkowego
-15
-10
-5
0
5
10
15
20
-4
-2
0
2
4
6
8
10
Dana jest następująca funkcja:
Zadaniem jest znalezienie miejsca zerowego
2
2
sin
5
)
cos(
3
x
x
x
y
dr inż. Tadeusz BURAK
9
Miejsce zerowe funkcji
Miejsce zerowe funkcji
(
(
metoda bisekcji)
metoda bisekcji)
ALGORYTM 1
ALGORYTM 1
Założenia:
•Funkcja jest monotoniczna w założonym
przedziale.
•Wartości funkcji na końcach przedziału są
różnego znaku.
( F(Xp) * F(Xk) ) < 0
Algorytm:
•znajdujemy wartość funkcji dla połowy długości
przedziału
•Jeżeli wartość funkcji na początku i w środku
przedziału jest tego samego znaku to wybieramy
jako nowy początek przedziału punkt środkowy –
jeśli znaki się różnią to punkt środkowy staje się
nowym końcem przedziału.
dr inż. Tadeusz BURAK
10
Miejsce zerowe funkcji
Miejsce zerowe funkcji
(
(
metoda bisekcji)
metoda bisekcji)
ALGORYTM 2
ALGORYTM 2
2
2
sin
5
)
cos(
3
x
x
x
y
Dla danej funkcji:
Przedział początkowy przyjmuje: Xp=1 ,
Xk=2
I odpowiednio Yp= -1,02 ; Yk=0,498
Wyliczone Xs = 1,5 i odpowiednio Ys =
-0,213
-1,5
-1
-0,5
0
0,5
1
0,5
1
1,5
2
2,5
dr inż. Tadeusz BURAK
11
Xp= 1,50
0
Xs= 1,62
5
Xk= 1,75
0
0,250
F(Xp)
=
-
0,21
F(Xs)
=
-
0,02
6
F(Xk)
=
0,15
5
Miejsce zerowe funkcji
Miejsce zerowe funkcji
(
(
metoda bisekcji)
metoda bisekcji)
ALGORYTM 3
ALGORYTM 3
Xp= 1,00
0
Xs= 1,50
0
Xk= 2,00
0
1,000
F(Xp)
=
-
1,02
F(Xs)
=
-
0,21
3
F(Xk)
=
0,49
8
Xp= 1,50
0
Xs= 1,75
0
Xk= 2,00
0
0,500
F(Xp)
=
-
0,21
F(Xs)
=
0,15
5
F(Xk)
=
0,49
8
Xp= 1,63
0
Xs= 1,68
8
Xk= 1,75
0
0,125
F(Xp)
=
-
0,02
6
F(Xs)
=
0,06
5
F(Xk)
=
0,15
5
dr inż. Tadeusz BURAK
12
Algorytm obliczania całki
Algorytm obliczania całki
oznaczonej metodą prostokątów
oznaczonej metodą prostokątów
a a+h a+2h ....
b
A+h
/2
N
a
b
h
gdzie
h
i
h
x
f
y
dx
x
f
y
N
i
b
a
:
)
2
(
)
(
1
a a+h/2 a+h
F(h/2)