1 Warsztaty dla nauczycieli przedmiotów informatycznych

2 Definicja algorytmu Cybernetyczna: dokładny przepiswykonania w określonym porządku skończonej liczby operacji, pozwalający na rozwiązanie każdego zadania danego typu. Matematyczna: reguła przekształcania wyrażeń matematycznych przez powtarzanie tych samych działań na kolejno otrzymywanych wynikach działań poprzednich

3 Podział algorytmów Ze względu na budowę algorytmu:algorytm liniowy algorytm rozgałęziony algorytm iteracyjny algorytm proceduralny algorytm rekurencyjny Ze względu na opis algorytmu: Opis słowny Opis przy pomocy pseudojęzyka Schemat blokowy Zapis w języku programowania

4 Algorytm liniowy Algorytm w którym kolejne instrukcje tworzą sekwencję o ustalonej kolejności. start Wprowadzenie danych Operacje na danych Wyprowadzenie danych koniec

5 Wypłata kwoty przy użyciu jak najwyższych nominałówOpis algorytmu: 1. Wpisz wartości nominałów od najwyższego do najniższego 2. Wpisz wielkość kwoty 3. Oblicz krotność występowania pierwszego nominału 4. Zmniejsz kwotę o obliczone nominały w punkcie 3. 5. Przejdź do niższego nominału i wykonaj obliczenia z punktu 3. 200 zł 100 zł 50 zł 20 zł 10 zł 5 zł 2 zł 1 zł 50 gr 20 gr 10 gr 5 gr 2 gr 1 gr

6 Dalszy ciąg opisu algorytmu wypłaty kwot 3x200zł 1x100zł 1x20zł 1x5zł 1x2zł 1x50gr 1x10gr 1x5gr 2x2gr 6. Algorytm zakończ po osiągnięciu najniższego nominału Wejście: kwota Wyjście: zestawienie nominałów wraz z krotnościami

7 Prezentacja algorytmu wypłata kwot w arkuszu kalkulacyjnymPlik: bank.xls

8 Algorytm rozgałęzionyAlgorytm w którym niektóre instrukcje są wykonywane przy spełnieniu określonych warunków, a inne przy ich niespełnieniu start Wprowadzenie danych T N Warunek logiczny I wariant obliczeń II wariant obliczeń Wyprowadzenie danych koniec

9 Klasyfikacja trójkątów według długości bokówOpis algorytmu: Wprowadzić trzy liczby dodatnie (boki) Uporządkować je nie malejąco Sprawdzić czy istnieje trójkąt o takich bokach Dokonać klasyfikacji z wyborem na boki lub na kąty. Wejście: 7, 6, 7 [B] Wyjście: trójkąt istnieje, równoramienny a£b£c a+b>c [B]-boki [K]-kąty

10 Pliki: trojkat.rys, trojkat.pasPrezentacja algorytmu klasyfikacja trójkątów w postaci schematu blokowego w programie EI oraz programu w TPASCALU Pliki: trojkat.rys, trojkat.pas

11 Zamiana liczby dwubajtowej z postaci dziesiętnej na szesnastkowąOpis algorytmu: Wprowadzić liczbę dziesiętną (<216) Dokonać jej konwersji do postaci dwójko wej, zastosować metodę odejmowania kolejnych potęg liczby 2. Dokonać jej konwersji do postaci szesna- stkowej, zastosować metodę podziału liczby dwójkowej na półbajtowe części Wejście: 48485 Wyjście: , BD65 216= 65536 cyfry szesna stkowe: 0,1,2,3 4,5,6,7 8,9,A,B C,D,E,F

12 Prezentacja algorytmu liczby dwójkowe i szesnastkowe w arkuszu kalkulacyjnym ExcelPliki: 10na2na16.xls

13 Algorytm iteracyjny Cykl iteracyjny z warunkiem na końcuAlgorytm w którym część ins- trukcji jest wielokrot- nie wyko- nywana aż do spełnie nia określo nego wa- runku Cykl iteracyjny z warunkiem na końcu Ilość cykli nieokreślona start wart. poczat. instrukcje cyklu N warunek T dalszy ciąg algort.

14 Obliczenie pierwiastka kwadratowego metodą HeronaAlgorytm oblicza pierwiastek kwadratowy dowolnej liczby z zdaną dokładnością Opis algorytmu: Pierwiastek z X jest równy bokowi kwadra- tu o polu X. Dowolną liczbę A>0 przyjmujemy za przy- bliżenie pierwiastka z X i jednocześnie za jeden z boków prostokąta o polu X Drugi bok wynosi wtedy X/A A X/A

15 Dalszy ciąg opisu metody HeronaJeżeli boki nie są równe budujemy następny prostokąt, którego jeden z boków jest śred- nią arytmetyczną boków poprzedniego, czyli B=(A+X/A)/2, a drugi X/B Jeżeli boki B i X/B nie są równe to budujemy wg tej reguły następny prostokąt Postępowanie to kontynuujemy tak długo, aż różnica pomiędzy bokami stanie się mniejsza od zadanej dokładności Wejście: X=72, A=8, E=0,001 Wyjście:  728,4852, J = ilość iteracji

16 Prezentacja algorytmu Herona w postaci:Schematu blokowego w programie Ei Ocena efektywności algorytmu w arkuszu kalkulacyjnym Excel pliki: heron.rys, heron.xls

17 Algorytm iteracyjny Cykl wyliczany z krokiem 1 liczba cykli określonaAlgorytm w którym część ins- trukcji jest wykonywana z góry określoną ilość razy start Cykl wyliczany z krokiem 1 liczba cykli określona i=1 n=? i>n instrukcje cyklu i=i+1 dalszy ciąg algorytmu

18 Szyfrowanie tekstu - Szyfr CezaraChr(65)- znak o kodzie65 Ord(‘A’)- kod zna- ku A funkcje po- mocne przy szyfrowa- niu. Opis algorytmu: Wprowadzić tekst stawiając na końcu znak #, który do tekstu nie należy. Pobierając kolejne znaki wyznaczyć długość tekstu i zapisać do zmiennej D W tekście przy szyfrowaniu przesuwamy kolejne znaki o jedno miejsce do przodu (tzn. A–>B, B–>C,....,Z–>A) Przy deszyfrowaniu o jedno miejsce do tyłu (tzn. A–>Z, B–>A,...,Z–>Y) np.. KOMPUTER szyfrujemy jako LPNQWUFS.

19 Prezentacja algorytmu szyfr Cezara w postaci:Schematu blokowego w programie Ei Programu w Visual Basicu pliki: szyfr.rys, szyfr.vbm

20 Metody Monte Carlo rnd(n) los() Randomprzykłady funkcji losowych w różnych progra- mach Generując bardzo dużo punktów losowych o określonych warunkach możemy rozwiązać wiele problemów np: wyznaczyć pierwiastek dowolnego równania znaleźć maksimum lub minimum funkcji obliczyć pole pod wykresem funkcji Taki sposób rozwiązywania problemów znany jest pod nazwą metod Monte Carlo.

21 Obliczenie pola pod wykresem funkcji metodą Monte CarloNapisać schemat blokowy programu obliczający pole pod wykresem paraboli y=x2 w przedziale <0,2> metodą Monte Carlo. generujemy punkty o losowych współrzędnych należące do prostokąta o wierzchołkach (0,0); (0,4); (2,4); (2,0) Dla każdego losowego punktu (x,y) sprawdzamy, czy leży on pod wykresem funkcji y=x2 tzn. czy prawdziwa jest nierówność y<=x2, jeśli tak, to należy on do pola S i program zalicza jedno "trafienie".

22 Ciąg dalszy algorytmu - pole pod wykresemJeśli liczba N wygenerowanych punktów jest dostatecznie duża to w przybliżeniu zachodzi równość: S N1 ———————— = ———— , pole prostokąta N gdzie N1 to ilość zaliczonych trafień. Stąd pole S jest równe: N S˙=˙˙pole prostokąta˙* ——— N

23 Prezentacja algorytmu pole pod wykresem w postaci:Programu w Turbo Pascalu Ocena dokładności obliczeń pliki: monte.pas

24 Algorytm proceduralnyAlgorytm w którym wyróżnio- ne części algorytmu (zwane procedurami) są logi cznie włą- czone w wykony- wanie róż- nych częś ci algoryt- mu start nadanie wartości parametrom wejście odwołanie się do procedury instrukcje procedury ciąg dalszy algort. powrót nadanie wartości parametrom i ew.odwołanie się doprocedury ciąg dalszy algort.

25 OD PROBLEMU DO PROGRAMUMetoda od ogółu do szczegółu Krok 1 - postawienie problemu Krok 2 - opis szczegółowy algorytmu Krok 3 - zapis algorytmu w kodzie pseudojęzyka Krok 4 - zapis algortmu w języku programowania

26 Krok 1 Postawienie problemuPRZY KŁAD METO DY OD OGÓ ŁU DO SZCZE GÓŁU Problem: Wyznaczyć wszystkie liczby pierwsze nie większe od zadanej liczby naturalnej. Zastosować algorytm znany pod nazwą sita Eratostenesa. Algorytm ten polega na wykreślaniu wielo- krotności kolejno znajdowanych liczb pier- wszych nie większych od zadanej liczby.

27 Krok 2 Opis szczegółowy algorytmuPRZY KŁAD METO DY OD OGÓ ŁU DO SZCZE GÓŁU Utworzyć listę liczb całkowitych od 1 do n. Zaczynając od liczby 2 usuń z listy wszystkie wielokrotności dwóch większe od 2. Znajdź pierwszą nieusuniętą liczbę (będzie to liczba 3) jest to liczba pierwsza Usuń wielokrotności trzech większe od 3 Znajdź pierwszą nieusuniętą liczbę (będzie to liczba 5) jest to liczba pierwsza

28 Ciąg dalszy opisu PRZY KŁAD METO DY OD OGÓ ŁU DO SZCZE GÓŁUUsuwaj w ten sposób wyznaczone wielo- krotności kolejnych znajdowanych liczb pierwszych, aż do przekroczenie połowy wartości liczby n Liczby, które pozostały są liczbami pierwszymi.

29 Krok 3 Zapis w kodzie pseudo językaLista zmiennych: n - parametr programu k,p - zmienne sterujące Ak - element tablicy liczb pierwszych znaj dujący się na miejscu k. Kod pseudo języka: czytaj n niech k :=0 dopóki k k:=k+1 Ak :=k

30 Ciąg dalszy kodu k:=k+1 Tu nale ży wsta wić proce durę „usun”niech k :=1 dopóki k<=n/2 wykonuj początek {wybierz następną liczbę Ak } jeżeli Ak <>0 to {usuń wielokrotności Ak większe od Ak } koniec Części opisowe umieszczone w nawiasach {...} zastępujemy odpowiednimi instrukcjami. k:=k+1 Tu nale ży wsta wić proce durę „usun”

31 Ciąg dalszy kodu Procedura USUNpoczątek p=2 dopóki k * p < n wykonuj początek A k * p = p=p koniec koniec

32 Krok 4 Zapis w języku programowaniaJęzyk Turbo Pascal program sito_eratostenesa; uses crt; const wymiar=2000; var A:array[1..wymiar] of integer; n,k:integer; procedure usun(p:integer); var kr:integer; begin kr:=2; while kr*p<=n do begin A[kr*p]:=0; kr:=kr+1; end;{koniec while...} end;{koniec usun...} Język QBasic CLS PRINT "**********************" PRINT "*PROGRAM WYZNACZA *" PRINT "*WSZYSTKIE; LICZBY *" PRINT "*PIERWSZE NIE WIEKSZE*" PRINT "*OD ZADANEJ LICZBY N *" DEFINT I, K, N INPUT "podaj liczbe N "; N DIM A(N) REM WYPELNIANIE TABLICY A(K) FOR K = 1 TO N LET A(K) = K NEXT K REM WYSZUKIWANIE LICZBY PIERWSZEJ LET K = 1

33 Zapis w języku programowaniabegin clrscr; writeln('********************************'); writeln('*PROGRAM WYZNACZA *'); writeln('*WSZYSTKIE LICZBY PIERWSZE*’); writeln('*NIE WIEKSZE OD ZADANEJ*'); writeln('*LICZBY N METODA SITA*'); writeln('*ERATOSTENESA *'); writeln('***************************'); writeln; write('podaj liczbe naturalna N '); read(n); for k:=1 to n do A[k]:=k; k:=1; FOR K = 2 TO INT(N / 2) IF A(K) <> 0 THEN GOSUB USUN DALEJ: NEXT K REM DRUKOWANIE CLS PRINT "oto liczby pierwsze < "; N PRINT " " PRINT FOR K = 2 TO N IF A(K) <> 0 THEN PRINT USING "#####"; A(K); NEXT K END REM USUWANIE WIELOKROTNOSCI USUN: I = 2 WHILE I * K <= N A(I * K) = 0 I = I + 1 WEND RETURN DALEJ

34 Zapis w języku programowaniarepeat k:=k+1; if A[k]<>0 then usun(k); until k>trunc(n/2); {drukowanie} clrscr; writeln('oto liczby pierwsze < ',n); writeln(' '); for k:=2 to n do if A[k]<>0 then write(A[k]:6); repeat until keypressed end.

35 Prezentacja algorytmu sito Eratostenesa w postaci:Programu w Turbo Pascalu pliki: monte.pas

36 Algorytm rekurencyjnyAlgorytm w którego definicji występuje odwołanie się do siebie samego. Algorytm ten musi zawierać warunek zakończenia kolejnego odwołania początek procedury N T Ocena algorytmu: złożoność pamięciowa złożoność czasowa warunek zakończenia blok instrukcji koniec rekurencji

37 Rekurencyjne obliczanie potęgpotega(a,n) wynik:= a•potega(a, n-1) podstawienie rekurencyjne w procedurze potega(a,n) Napisz procedury rekurencyjne obliczające potęgę an przy pomocy poniższych wzorów: Obliczyć potęgę 1, , ocenić złożoność pamięciową i czasową.

38 Prezentacja algorytmu potęgi w postaci:Programu w Turbo Pascalu Ocena złożoności pamięciowej i czasowej pliki: pot1.pas, pot2.pas, pot3.pas

39 (metoda bisekcji, podziału połówkowego)Równanie nieliniowe (metoda bisekcji, podziału połówkowego)

40 Obliczanie pierwiastków równania nieliniowego - metodą bisekcjiWłasność Darbeaux: Jeżeli funkcja ciągła przyjmuje róż ne wartości w końcach przedziału to przyjmuje w tym przedzia- le wszystkie wartości po- średnie. Opis metody: Zakłada się że znany jest przedział i dokładność E , na końcach którego funkcja f(x) ma wartości przeciwnego znaku tzn. f(A)*f(B)<0 co oznacza, że w przedziale znajduje się przynajmniej jedno miejsce zerowe. W kolejnych krokach zawęża się ten przedział przyjmując: A=(A+B)/ jeżeli f(A)*f((A+B)/2)>0 lub B=(A+B)/ w przeciwnym przypadku

41 Dalszy ciąg opisu Kolejne zawężania należy przerwać po spełnieniu warunku: (B-A)< 2*E Program powinien również wyznaczać ilość iteracji (zawężeń przedziału). Zadanie. Do studni wrzucono dwa patyki, o długości AB=4 m, CD=3 m Punkt E zetknięcia się patyków znaj- duje się na wysokości EF=1 m nad dnem studni. Obliczyć szerokość studni. B D E A F C

42 Rozwiązanie zadania Stosując Twierdzenia Talesa i Pitagorasa dla AEF i ACB oraz dla CEF i ACD otrzymamy równanie: równanie to można rozwiązać metodą bisekcji, zastosowanej do przedziału <0,3>

43 Prezentacja algorytmu, metoda bisekcji w postaci:Schematu blokowego Programu w Turbo Pascalu Programu w Visual Basicu pliki: bisekcja.rys, bisekcja.pas, bisekcja.vbp

44 Pełną wersję prezentacji wraz z programami można pobrać ze strony: