Algorytmy szeregowe, z rozgałęzieniami, zawierające pętle

Содержание

Слайд 2

Wprowadzenie do projektowania algorytmów Alagić S., Arbib M.A. - WNT 1982

Wprowadzenie do projektowania algorytmów

Alagić S., Arbib M.A. - WNT 1982
„Projektowanie programów

poprawnych i dobrze zbudowanych"
....polega na rozłożeniu zadania na ściśle określone podzadania, których poprawne rozwiązanie i właściwe ich połączenie da rozwiązanie całego problemu .

"Things should be as simple as possible but no simpler.” Albert Einstein

Слайд 3

Podstawowa wiedza o budowie algorytmów . Algorytmy mają budowę modularną. Moduł

Podstawowa wiedza o budowie algorytmów .

Algorytmy mają budowę modularną.
Moduł (algorytm

dla jednego podzadania):
jest oddzielną jednostką,
ma swoją nazwę – identyfikator,
może wywoływać inne moduły
ma tylko jedno wejście i jedno wyjście,
ma zapewniony powrót do modułu z którego jest wywołany,
powinien pełnić jedną i tylko jedną funkcję,
powinien być stosunkowo niewielki.
Слайд 4

Każdy dowolnie złożony algorytm można zbudować z trzech tylko konstrukcji podstawowych,

Każdy dowolnie złożony algorytm można zbudować z trzech
tylko konstrukcji podstawowych, nazywanych

strukturami,
są to :
struktura sekwencji
struktura wyboru
struktura pętli

Podstawowa wiedza o budowie algorytmów .

Слайд 5

Podstawowe Struktury Struktura sekwencji - wykonanie w kolejności zapisu jednej, dwóch

Podstawowe Struktury

Struktura sekwencji - wykonanie w kolejności zapisu
jednej, dwóch

lub więcej struktur składowych.

Struktura 1

Struktura 2

Struktura n

.........................

Слайд 6

Algorytmy szeregowe Algorytm nazywamy szeregowym, jeśli spełniona jest zależność gdzie n+1

Algorytmy szeregowe

Algorytm nazywamy szeregowym, jeśli spełniona jest zależność
gdzie
n+1 ilość operacji

w algorytmie
oi i-ta operacja
t(x) chwila czasu w której wykonywana jest operacja x
Instrukcje wykonywane są tu sekwencyjnie jedna po drugiej, według kolejności wyznaczonej przepływem sterowania.
Слайд 7

Podstawowe Struktury warunek Struktura wyboru –zapewnia wykonanie, według kryterium spełnienia lub

Podstawowe Struktury

warunek

Struktura wyboru –zapewnia wykonanie,
według kryterium spełnienia lub niespełnienia określonego

warunku,
jednej spośród dwóch albo wielu podanych struktur składowych

wykonaj Strukturę 1

wykonaj Strukturę 2

spełniony

niespełniony

Слайд 8

Przykład poszukiwania rozwiązań problemu Wyznaczanie NWD Szukany jest NWD (m,n) -

Przykład poszukiwania rozwiązań problemu Wyznaczanie NWD

Szukany jest NWD (m,n) -
największy

wspólny podzielnik liczb naturalnych m i n
Metoda 1: rozkład na czynniki pierwsze;
Ćwiczenie: Obliczyć:
NWD (13, 51)
NWD (46, 48)
NWD (14, 28)
Przedstawić w postaci algorytmu formalny zapis procesu wyznaczania NWD dwóch liczb naturalnych (n, m)
Слайд 9

Wyznaczania wspólnego podzielnika dwóch liczb naturalnych – algorytm Euklidesa Metoda 2

Wyznaczania wspólnego podzielnika dwóch liczb naturalnych – algorytm Euklidesa

Metoda 2
Przyjmijmy, że

n>m, wtedy n=q*m+r
Jeśli liczba naturalna k jest podzielnikiem n oraz m, to r = k* ( n/k –q* m/k)
k jest podzielnikiem n oraz m, czyli musi być też podzielnikiem r, zatem zachodzi równość:
NWD (m,n) = NWD (r, m)
Zauważmy, że :
r = n - q*m
gdzie: n, m, r, q ∈ N
m0Pierwszy element w parze (r, m) maleje; r→0 i nie przekroczy 0, bo r ∈ N,
szukanym NWD (r, m) jest m dla którego r=0, czyli gdy otrzymamy NWD (0, m)
Zatem algorytm Euklidesa jest skończony
Слайд 10

Algorytm Euklidesa – lista kroków Dane: n, m ∈ N gdzie

Algorytm Euklidesa – lista kroków

Dane: n, m ∈ N gdzie mWynik: NWD

(m,n) ∈ N
Algorytm:
K1. Jeśli m=0 to NWD (m,n) = n
K2. r:= n mod m
n:=m
m:=r
wróć do K1
NWD (14,28) = NWD (0,14)
NWD (46,48) = NWD (2,46) =NWD (0,2)
Слайд 11

Algorytm Euklidesa obliczania NWD (m,n); m m=0 Stop Tak r:=n mod

Algorytm Euklidesa obliczania NWD (m,n); m

m=0

Stop

Tak

r:=n mod m;
n:=m;
m:=r

Nie

Czytaj m,n

Wypisz n

Слайд 12

Podstawowe Struktury Struktura powtórzenia ( pętli ) - cykliczne wielokrotne wykonanie

Podstawowe Struktury

Struktura powtórzenia ( pętli ) - cykliczne wielokrotne wykonanie określonej

struktury składowej (może być złożona), w zależności od spełnienia założonego warunku

Koniec

wykonaj

Tak

Nie

Слайд 13

Iteracja Iteracja – powtarzanie określonego ciągu operacji na pewnych elementach zbioru

Iteracja

Iteracja – powtarzanie określonego ciągu operacji na pewnych elementach zbioru danych;
Rodzaje

iteracji ( pętli)
Iteracja ograniczona - pętla typu for
Iteracja warunkowa dopóki - pętla typu while
Iteracja powtarzaj.. dokąd - pętla typu repeat..until
Слайд 14

Pętla for i i=1 tak instrukcje i=i+1 nie var i: Integer;

Pętla for

i

i=1

tak

instrukcje
i=i+1

nie

var i: Integer; begin for i:=1 to n do begin  

{Instrukcje}   end; end.
Слайд 15

Pętla while while Sum begin Sum:=Sum+Liczba; Licznik:=Licznik+1; end; i tak Inne instrukcje nie L:=L+1 S:=S+L

Pętla while

while Sum<=50 do
begin
Sum:=Sum+Liczba;
Licznik:=Licznik+1;
end;

i

tak

Inne instrukcje

nie

L:=L+1
S:=S+L

Слайд 16

Pętla Repeat Until suma:=0; i:=0; REPEAT i:=i+1; suma:=suma+i; UNTIL suma >=liczba;

Pętla Repeat Until

suma:=0;
i:=0;
REPEAT i:=i+1;
suma:=suma+i;
UNTIL suma >=liczba;

warunek

tak

Inne instrukcje

nie

Treść

pętli
Слайд 17

Przykłady problemów Przeszukiwanie, filtrowanie, sortowanie zbiorów danych; Statystyczna analiza danych; obliczanie

Przykłady problemów

Przeszukiwanie, filtrowanie, sortowanie zbiorów danych;
Statystyczna analiza danych; obliczanie

parametrów statystycznych : średnich (arytmetycznej, harmonicznej, ważonej ), wariancji , odchylenia standardowego, max, min, itp
Tablicowanie wartości funkcji
Działania na macierzach
Obliczenia wartości przybliżonych metodą iteracyjną
Слайд 18

Obliczanie wartości wielomianu Wn (x) dla określonej wartości wg schematu Hornera

Obliczanie wartości wielomianu Wn (x) dla określonej wartości wg schematu Hornera

Tradycyjny zapis

wielomianu
Wn(x) = aoxn+ a1xn-1....+ an-1x+ an
Ile operacji należy wykonać aby obliczyć Wn(x) ?
Przekształcamy ten wielomian w następujący sposób:
Wn(x) = (aoxn-1+ a1xn-2....+ an-1)x+ an
Schemat Hornera (1819r)
Wn(x) = (...((aox+ a1)x+. a2)x...+ an-1)x+ an
Ocenić pracochłonność algorytmu dla schematu Hornera
Ile operacji należy wykonać aby obliczyć Wn(x) ?
Слайд 19

Algorytm z pętlą for (i=0,...,n) w postaci schematu blokowego (schemat Hornera)

Algorytm z pętlą for (i=0,...,n) w postaci schematu blokowego (schemat Hornera)

i=n

z:=x
i:= 0
y:=a0

Stop

Tak

i:=i+1
y:=y*z

+ai

Nie

Współczynnik przy najwyższej potędze jest wartością początkową

Struktura powtarzania
pętli

Iteracja

Слайд 20

Pętla z warunkiem Zadanie: Obliczyć bok kwadratu o polu a Metoda:

Pętla z warunkiem

Zadanie: Obliczyć bok kwadratu o polu a
Metoda: wzór Herona
wymagana dokładność

obliczeń | xi+1 - xi| < eps
Слайд 21

Algorytm obliczania pierwiastka kwadratowego z danej liczby wg wzoru Herona Dane:

Algorytm obliczania pierwiastka kwadratowego z danej liczby wg wzoru Herona

Dane:
Liczba

pierwiastkowana: a
Pierwsze przybliżenie pierwiastka kwadratowego z danej liczby: p
dokładność obliczeniowa eps
Wynik:
Liczba x (spełniająca warunek x2≈a, z dokładnością eps)
Algorytm ( lista kroków)
K1 p := x0;
K2 x:= (p + a/p) / 2;
K3 Jeśli | x – p | < eps, to x jest szukaną liczbą , zakończ;
K4 Przyjmij p:= x wróć do K2
Слайд 22

Algorytm Newtona Raphsona Dane: Liczba pierwiastkowana: a Pierwsze przybliżenie pierwiastka kwadratowego

Algorytm Newtona Raphsona

Dane:
Liczba pierwiastkowana: a
Pierwsze przybliżenie pierwiastka kwadratowego z danej

liczby: p
dokładność obliczeniowa eps
maksymalna liczba iteracji Maxi
Wynik:
Liczba x (spełniająca warunek x2≈a, z dokładnością eps
albo obliczona po nie więcej niż Maxi operacjach
Algorytm ( lista kroków)
K1 i := 0;
K2 x:= (p + a/p) / 2; i:= i+1:
K3 Jeśli | x – p | < eps, lub i=imax to x jest szukaną liczbą , zakończ;
K4 Przyjmij p:= x wróć do K2
Algorytm ten posiada zabezpieczenie na wypadek gdyby dla uzyskania zakładanej dokładności czas obliczeń był zdecydowanie za długi
Слайд 23

Iteracja kończąca się i iteracja nieskończona Kryteria zakończenia obliczeń (działań) w

Iteracja kończąca się i iteracja nieskończona

Kryteria
zakończenia obliczeń (działań) w algorytmie

iteracyjnym:
wykonanie podanej liczby iteracji (powtórzeń)
uzyskanie żądanej dokładności obliczeń np. | xi+1 - xi| < eps
Dla zabezpieczenia przed niekończącymi się pętlami przy działaniach na zbiorach danych warto;
ustalić moc zbioru danych (liczbę elementów)
gdy liczność zbioru danych nie jest znana po ostatnim elemencie powinien być postawiony wartownik oznaczający koniec zbioru
Слайд 24

Zadania Opracować algorytmy na : obliczanie sumy i wartości średniej n

Zadania

Opracować algorytmy na :
obliczanie sumy i wartości średniej n danych liczb
obliczanie

iloczynu n danych liczb
obliczanie sumy, wartości średniej wyników pomiarów wykonywanych przez urządzenie automatyczne i przesyłanych do komputera, liczba pomiarów nie jest znana.
Wyznaczyć wszystkie liczby pierwsze w zbiorze liczb naturalnych dwucyfrowych
Слайд 25

Rekurencja Przykłady definicji rekurencyjnych w matematyce Rekurencja jest szczególnie silnym narzędziem

Rekurencja Przykłady definicji rekurencyjnych w matematyce

Rekurencja jest szczególnie silnym narzędziem w

matematyce, przykłady:
Liczby naturalne:
1 jest liczbą naturalną, następnik liczby naturalnej jest liczbą naturalną
Silnia
0!=1;
n!=n*(n-1)! dla n>0
Postęp arytmetyczny Postęp geometryczny
a0 c0
an+1=an + r cn+1=cn* q
Слайд 26

Przykład problemów związanych ze stosowaniem algorytmów rekurencyjnych Rekurencyjny wzór wielomianu Wn(x)

Przykład problemów związanych ze stosowaniem algorytmów rekurencyjnych

Rekurencyjny wzór wielomianu Wn(x)
Wn(x)=ao dla n=0
Wn(x)

= Wn-1(x) *x + an dla n>0
Zapis rekurencyjny, chociaż w istocie bardziej elegancki, prowadzi do zmniejszenia efektywności obliczeń np. w porównaniu do schematu Hornera.
Слайд 27

Realizacja rekurencji dla n=3 W3(x) = W2 (x) *x + a3

Realizacja rekurencji dla n=3

W3(x) = W2 (x) *x + a3 y=y*x+

a3
W2(x) = W1 (x) *x + a2 y=y*x+ a2
W1(x) = W0 (x) *x + a1 y=y*x+ a1
W0(x) = a0 y= W0(x)

Procedura rozwinięcia rekurencyjnego

Warunek stopu, tj zakończenia rekurencji

Procedura obliczania wartości wielomianu. Najszybciej według schematu Hornera (A. Borodin -1971r.)

Слайд 28

Zadanie Zadanie: obliczyć liczbę królików po k miesiącach gdy: Na początku

Zadanie

Zadanie: obliczyć liczbę królików po k miesiącach gdy:
Na początku mam

jedną parę młodych królików
Króliki osiągają dojrzałość po jednym miesiącu
Para dorosłych królików rodzi co miesiąc jedną parę królików
Króliki nie umierają
Przedstawić graficznie interpretację procesu rozmnażania się królików w ciągu 6 miesięcy, uwzględniając podział na pary młode i pary dojrzałe ( liczby par )
Слайд 29

Ciąg Fibonacciego W 1202 roku Leonard z Pizy zwany Fibonaccim (synem

Ciąg Fibonacciego

W 1202 roku Leonard z Pizy zwany Fibonaccim (synem Bonacciego)

w dziele Liber abaci podał rozwiązanie problemu rozmnażania królików:
Rozwiązania tego problemu tworzą tzw ciąg Fibonacciego – ciąg liczb naturalnych określony rekurencyjnie w sposób następujący:.
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)
wyrazy tego ciągu nazywamy liczbami Fibonacciego. Kwestia, czy zaliczać zero do ciągu Fibonacciego, jest dyskusyjna. Część autorów rozpoczyna ciąg od 0
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
Nazwę "ciąg Fibonacciego" spopularyzował w XIX w. Édouard Lucas
Слайд 30

Problemy z rekurencją: występowanie dublujących się obliczeń Obliczanie parametrów ciągu rekurencyjnego

Problemy z rekurencją: występowanie dublujących się obliczeń

Obliczanie parametrów ciągu rekurencyjnego wykonane

bezpośrednio na podstawie wzoru matematycznego, może powodować problemy w postaci zbyt wielu dublujących się obliczeń.
Na rysunku zaprezentowano schemat wywołań rekurencyjnych funkcji FIB, realizującej obliczenia ściśle według podanej definicji, na którym zaznaczono kolorem gałęzie wykonujące się dwa razy. Zupełnie niepotrzebnie.
W sumie, wywołanie funkcji FIB dla większych parametrów n, spowoduje że wykonane zostanie w przybliżeniu 2n obliczeń, co jest z oczywistych powodów nieefektywne.
Dlatego należy pamiętać, że nie jest dobrą metodą programowanie rekurencyjne tam, gdzie wystarczą proste funkcje iteracyjne

funkcja FIB jest zdefiniowana rekurencyjnie
FIB(0) =0
FIB(1) = 1
FIB (n) = FIB(n-1) + FIB(n-2)

Слайд 31

Jawna postać liczb Fibonacciego Jawny wzór na n - ty wyraz

Jawna postać liczb Fibonacciego

Jawny wzór na n - ty wyraz

ciągu Fibonacciego, zwany wzorem Bineta, ma postać:

Zadanie:
Przygotować algorytmy iteracyjne na obliczanie liczb Fibonacciego korzystając z różnych form ich prezentowania np.:
z wzoru Bineta
z definicji rekurencyjnej (przekształconej w algorytmie do postaci iteracyjnej)
i oszacować ich pracochłonność.

Слайд 32

Ciekawostki zamiast podsumowania Zastosowania liczb Fibonacciego – złota liczba Złota liczba

Ciekawostki zamiast podsumowania Zastosowania liczb Fibonacciego – złota liczba

Złota liczba
granica ciągu F(n+1)/F(n)
czyli

ilorazów sąsiadujących ze sobą wyrazów ciągu Fibonacciego to tzw. złota liczba lub złota proporcja definiowana jako dodatnie rozwiązanie równania :
x:1=1:(x-1)
Jeśli będziemy dzielić kolejne liczby w sekwencji przez liczby występujące przed nimi okazuje się, że za każdym razem otrzymamy wynik oscylujący wokół niewymiernej wartość 1,61803398875….. np. 21 podzielone przez 13 daje w przybliżeniu 1,618.
Dzielenie liczb z ciągu przez liczbę następną daje nam wartość 0,618…, czyli 13 podzielone przez 21 da mam w przybliżeniu 0,618. 0,618 jest więc odwrotnością 1,618.
Współczynnik 1,618033…. w średniowieczu został nazwany boską proporcją.
Współcześnie spotyka się głównie dwie nazwy: złoty podział lub złoty środek.
W algebrze oznacza się go grecką literą phi ɸ = 1,618.
Слайд 33

Liczby z ciągu Fibonacciego wkomponowane w rozrost kwiatu kichawca. Źródło: H.E.

Liczby z ciągu Fibonacciego
wkomponowane w rozrost kwiatu kichawca.
Źródło: H.E.

Huntley, The Divie Proportion, Dover Publications 1970. [3]

Logo firmy Apple zbudowane z kół o promieniach,
których wartości to kolejne liczby z ciągu Fibonacciego.
Źródło: http://www.banskt.com/blog/golden-ratio-in-logo-designs

Слайд 34

Złoty podział i liczby Fibonacciego Złoty podział - podział harmoniczny, dla

Złoty podział i liczby Fibonacciego

Złoty podział - podział harmoniczny, dla liczby

a, jest to przedstawienie tej liczby w postaci sumy b + c dwu składowych b, c takich, że a:b=b:c
Np. dla odcinka jest to podział wewnętrzny tego odcinka w stosunku - jest to tzw. złota liczba (liczba ɸ ).
W wyniku złotego podziału odcinka otrzymuje się dwa odcinki o tej własności, że stosunek długości dłuższego z nich do długości krótszego jest równy stosunkowi długości dzielonego odcinka do długości dłuższego odcinka.
punkt przecięcia przekątnych pięciokąta foremnego wyznacza ich złoty podział.
bok dziesięciokąta foremnego ma długość równą długości dłuższego z odcinków wyznaczonych przez złoty podział promienia okręgu opisanego na tym dziesięciokącie.
Слайд 35

Schemat złotego podziału prostokąta Złota spirala Zdjęcie rentgenowskie muszli łodzika. Źródło:

Schemat złotego podziału prostokąta
Złota spirala

Zdjęcie rentgenowskie muszli łodzika.
Źródło: H.E. Huntley,

The Divine Proportion,
Dover Publications 1970
- Предыдущая
Партнёр Делис Архив рассылка
Следующая -
Государственный бюджет

Похожие презентации

ПономаренкоГалль4.06
Технология машиностроения
Презентація
20151216_urok_no15_formirovanie_srednevekovyh_gorodov
Газета №6. I love english
диагностика 4-5 лет
Машинные швы
Инструкция по диагностике проблем мотора вентилятора отопителя
Реализация приоритетного проекта Формирование комфортной городской среды на территории МО Уемское на 2018 год
Доклад директора ГБУ Жилищник района Котловка
Архитектура
Работы нулевого цикла
Конструирование и моделирование швейных изделий (7 класс)
Управление денежными потоками организации
BAE Systems, Inc. Sectors at a Glance
“Discovery Investigation Agency ”
Электрические приборы в доме
Проф. требования. Методы конструирования
Колаж книжкові виставки
Первые работы Фобс
20180109_orlovskaya_oblast-80_let
220722 Маркетинг ивент_фотозона
Стали и серые чугуны
Понятие о резьбе
Знакообразование
Светлая память всем, кого с нами нет
Вопросы для обсуждения комедии А.В.Сухово-Кобылина Свадьба Кречинского в постановке Театра им. Моссовета
Аналоговые перемножетели напряжений
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть