1 opracowała: Anna MikućPRZYKŁADY ALGORYTMÓW Z ROZGAŁĘZIENIAMI opracowała: Anna Mikuć

2 ALGORYTM W matematyce oraz informatyce to skończony uporządkowany zbiór jasno zdefiniowanych czynności koniecznych do wykonania pewnego zadania w skończonej liczbie kroków. Ma on przeprowadzić system z pewnego stanu początkowego do pożądanego stanu końcowego. Potocznie – jest to schemat postępowania, dokładny opis sposobu rozwiązania problemu, uwzględniający: opis danych wejściowych, wyniku oraz procedur, które prowadzą od danych do wyniku. Sposoby zapisu algorytmu: opis słowny lista kroków schemat blokowy pseudokod (pośredni między językiem potocznym a językiem programowania)

3 Algorytmy z rozgałęzieniamiWystępują w nich alternatywne ciągi działań. Wybór jednego z nich następuje w zależności od spełnienia bądź niespełnienia określonego warunku. WYBIERZ PRZYKŁAD RÓWNANIE LINIOWE RÓWNANIE KWADRATOWE UKŁAD RÓWNAŃ LINIOWYCH KONIEC

4 RÓWNANIE LINIOWE Wybierz rodzaj zapisu algorytmu OPIS SŁOWNYLISTA KROKÓW SCHEMAT BLOKOWY Wybierz rodzaj zapisu algorytmu MENU

5 Równanie liniowe z jedną niewiadomą ax + b = 0Równanie liniowe ax + b = 0 posiada rozwiązania w zależności od współczynników a i b. Jeśli a = 0 i b = 0 to równanie ma nieskończenie wiele rozwiązań. Jeśli a = 0 i b ≠ 0 to równanie nie ma rozwiązania. Jeśli a ≠ 0 to równanie ma jedno rozwiązanie x0 = . Specyfikacja: Dane: a, b  R Wynik : x o  R

6 Równanie liniowe z jedną niewiadomą ax + b = 01) Wczytaj współczynniki a i b równania liniowego. Jeśli a = 0 i b = 0, to wypisz wynik „nieskończenie wiele rozwiązań” STOP 3) Jeśli a = 0 i b ≠ 0, to wypisz wynik równanie sprzeczne”. STOP 4) Jeśli a ≠ 0 i b ≠ 0, to xo : = 5) Wypisz wynik xo. STOP Złożoność obliczeniowa algorytmu: rzędu jedności.

7 Równanie liniowe z jedną niewiadomą ax + b = 0START Wczytaj współczynniki a, b T a=0 N T b=0 N x0 : = Wypisz: „nieskończenie wiele pierwiastków” Wypisz: „równanie sprzeczne” Wypisz x0 STOP

8 RÓWNANIE KWADRATOWE Wybierz rodzaj zapisu algorytmu OPIS SŁOWNYLISTA KROKÓW SCHEMAT BLOKOWY Wybierz rodzaj zapisu algorytmu MENU

9 Równanie kwadratowe ax2 + bx + c = 0Równanie kwadratowe ax2 + bx + c = 0 można rozwiązać stosując wyróżnik (tzw. deltę). W algorytmie oznaczony jest literą D. D := b2 – 4ac W zależności od wartości tego wyróżnika można rozpatrywać następujące sytuacje: Jeśli D > 0, to równanie posiada dwa pierwiastki x1 i x2. x1 := x2 := Jeśli D = 0, wtedy równanie posiada jeden pierwiastek x1 := Jeśli D < 0, to wówczas równanie nie posiada rozwiązań rzeczywistych. Algorytm wyklucza sytuację, że a = 0 w równaniu kwadratowym. Specyfikacja: Dane: a, b, c  R Zmienna pomocnicza: D  R Wynik : x1, x2  R

10 Równanie kwadratowe ax2 + bx + c = 01) Wczytaj współczynnik a równania kwadratowego (różny od zera) oraz współczynniki b i c. 2) Oblicz wyróżnik równania D := b 2 – 4ac 3) Jeśli D = 0, to oblicz x1 := i wypisz wynik: x1. STOP 4) Jeśli D < 0, to wypisz wynik „równanie nie ma pierwiastków”. STOP 5) Jeśli D > 0, to oblicz: x1 := x2 := 6) Wypisz wynik: x1, x2. STOP Złożoność obliczeniowa algorytmu: rzędu jedności.

11 Wczytaj współczynniki b, cSTART T Wczytaj współczynnik a N a=0 Wczytaj współczynniki b, c Równanie kwadratowe ax2 + bx + c = 0 D := b2 – 4ac T N D=0 T N x1 := D < 0 x1:= x2:= Wypisz „brak pierwiastków” Wypisz x1 Wypisz x1, x2 STOP

12 UKŁAD RÓWNAŃ LINIOWYCHOPIS SŁOWNY LISTA KROKÓW SCHEMAT BLOKOWY Wybierz rodzaj zapisu algorytmu MENU

13 Układ równań liniowychUkład równań liniowych a1 x + b1  y = c można rozwiązać obliczając wyznaczniki. a2  x + b2  y = c2 W zależności od wartości wyznaczników W, Wx i Wy można rozpatrywać następujące sytuacje: Jeśli W <> 0 to układ  równań posiada rozwiązanie x = i y = Jeśli W = 0 i Wx <> 0 lub Wy <> 0 wtedy układ  nie posiada rozwiązań (układ sprzeczny). Jeśli W = 0 i Wx = 0 i Wy = 0 to układ równań posiada nieskończenie wiele rozwiązań. Specyfikacja: Dane: a1, b1, c1, a2, b2, c2  R Zmienne pomocnicze: W, Wx, Wy  R Wynik : x, y  R

14 Układ równań liniowychWczytaj współczynniki a1, b1, c1 pierwszego równania oraz a2, b2, c2 drugiego równania. Oblicz wyznacznik główny W := a1b2 – a2b1 oraz Wx := c1b2 – c2b1 i Wy := a1c2 – a2c1 Jeżeli W = 0 i Wx = 0 i Wy = 0, to wypisz wynik „nieskończenie wiele rozwiązań”. STOP 4) Jeżeli W = 0 i Wx ≠ 0 lub Wy ≠ 0, to wypisz wynik „układ sprzeczny”. STOP Jeżeli W ≠ 0 i Wx ≠ 0 i Wy ≠ 0, to oblicz x := i y := 6) Wypisz wynik (x, y). STOP Złożoność obliczeniowa algorytmu: rzędu jedności.

15 Wczytaj współczynnikiSTART Układ równań liniowych Wczytaj współczynniki a1, b1, c1, a2, b2, c2 W := a1b2 – a2b1 Wx := c1b2 – c2b1 Wy := a1c2 – a2c1 T N W=0 Wx=0 Wy=0 x := Wx/W y := Wy/W T N Wypisz „nieskończenie wiele rozwiązań” Wypisz „układ równań sprzecznych” Wypisz x, y STOP