algorytmy_10.pdf

Rozwiązywanie problemów z uŜyciem komputera:

1. Zdefiniowanie i opis problemu

2. Znalezienie rozwiązania

3. Napisanie algorytmu

4. Napisanie programu (zakodowanie algorytmu)

5. Uruchomienie programu

6. Testowanie programu

II PWr

Algorytm - definicje

Własności algorytmów:

1) poprawność – algorytm musi być poprawny

Algorytm – skończony system reguł określających kolejność działań

wykonywanych na określonych obiektach (danych) w celu uzyskania rozwiązania

problemu.

2) skończoność – algorytm musi umoŜliwić rozwiązanie problemu w

skończonym czasie

Algorytm – ściśle określona procedura obliczeniowa, która dla właściwych

danych wejściowych wytworzy Ŝądane dane wyjściowe zwane wynikiem

działania algorytmu.

3) złoŜoność – mierzy się czasem wykonania i zajętością pamięci odniesionych

do wielkości danych

4) uniwersalność – nie powinien być zawęŜany do wąskiego problemu

ALGORYTM

Dane wej.

Dane wyj.

Pochodzenie wyrazu: od nazwiska matematyka arabskiego „Al-Khowarizmi”

z IX w. Na łacinę zostało przetłumaczone jako Algorismus.

II PWr

6. Testowanie programu

ALGORYTM

Przykłady problemów algorytmicznych

Algorytm – sposoby zapisu

• Zbadanie czy dana liczba naturalna jest pierwsza

• Znalezienie największego wspólnego dzielnika dwóch liczb

• Rozkład liczby na czynniki pierwsze

1) opis słowny

Musi być zrozumiały i jednoznaczny.

2) opis w postaci listy kroków

Poszczególne kroki zawierają opis operacji, które mają być wykonane przez

algorytm. Mogą równieŜ wystąpić polecenia zmiany kolejności wykonywania

kroków.

3) schemat blokowy

• Uporządkowanie (posortowanie) ciągu liczb od najmniejszej do największej

• Rozwiązanie układu równań liniowych

• Przydział pracowników do zadań

• Optymalizacja gospodarki materiałowej

• Zagadnienia transportowe

4) program komputerowy

Jest najbardziej ścisłym zapisem algorytmu.

II PWr

Algorytm - przykłady

Algorytm Euklidesa – znajdowanie największego wspólnego podzielnika 2 liczb.

Dane są dwie liczby naturalne a, b (a > b).

NWD(a,b):

Dopóki(a != b) Wykonaj

JeŜeli (a>b)

a = a – b

NWD(a,b):

1. JeŜeli b = 0

2. to Wynik = a

a = a – b

JeŜeli (b>a)

b = b – a

Wynik = a

3. w przeciwnym razie Wynik = NWD(b, a mod b)

NWD(30,21) =

NWD(21, 30 mod 21) = NWD(21,9) =

NWD(9, 21 mod 9) = NWD(9, 3) =

NWD(3, 9 mod 3) = NWD(3, 0) = 3

NWD(30,21) = NWD(9,21) = NWD(9,12) = NWD(9,3)= NWD(6,3) =NWD(3,3) = 3

II PWr

Algorytm - przykłady

1. Algorytm rozwiązania równania liniowego ax + b = 0

2. Algorytm obliczania n!

n! = 1*2*3* ... *n

1. Wprowadź wartości a, b;

2. JeŜeli a<>0 to x=-b/a; Wyprowadź x;

W przeciwnym razie Wyprowadź „Złe dane”;

3! = 1*2*3 = 6 4! = 1*2*3*4 = 3!*4 =

Czytaj n

3. Koniec;

n! = (n-1)!*n

silnia=1

Czytaj a, b

1. Czytaj n;

i=2

2. silnia =1;

3. Dla i = 2 do n wykonaj

a<>0

x= -b/a

i<=n

Wypisz: Złe dane

Wypisz x

silnia = silnia*i;

4. Wyprowadź silnia;

5. Koniec;

Wyświetl silnia

silnia=silnia*i

i = i+1

II PWr

Algorytm - przykłady

Obliczyć sumę ciągu n liczb:

a 1 , a 2 , a 3 , ..., a n

Obliczyć sumę liczb czytanych z klawiatury.

Czytanie kończy liczba 0.

Czytaj dane

Suma=0

Suma = 0;

Dla i = 1 Do n Wykonaj

Suma = Suma +a i

i=1

Suma = 0;

Czytaj a

Czytaj a:

Suma = Suma +a i

Drukuj Suma;

Koniec

i<=n

Dopóki a<>0 Wykonaj

Suma = Suma + a;

a<>0

Drukuj: Suma

Suma=Suma+a i

Czytaj a;

Drukuj Suma;

Drukuj Suma

Suma=Suma+a

i=i+1

Czytaj a

II PWr

Algorytm – rozwiązanie równania kwadratowego

ax 2 + bx +c = 0

Wprowadź

a,b,c

1. Czytaj a, b, c

2. JeŜeli a = 0 to

JeŜeli b = 0 to Wyprowadź „Złe dane”

a=0

delta=b 2 -4ac

b= 0

W przeciwnym razie x = -c/b; Wyprowadź x

W przeciwnym razie

x=-c/b

Złe dane

delta>=0

x=-c/b

Złe dane

delta = b 2 – 4ac

JeŜeli delta >= 0 to

Brak

pierwiastków

−

DELTA

Wyprowadź x

−

DELTA

−

DELTA

−

DELTA

Wyprowadź x 1 , x 2

W przeciwnym razie Wyprowadź „Brak pierwiastków”

Wyprowadź

x 1 , x 2

3. Koniec

II PWr

Algorytm – schemat blokowy

Algorytm – sekwencja czynności

Konwencje dotyczące schematów blokowych

początek/koniec

Czynność 1

operacja we/wy

Czynność 2

blok wykonawczy

blok warunkowy

Czynność 3

blok złoŜony

II PWr

Algorytm – warunek „jeŜeli”

Algorytm – wybór czynności

Wej

JeŜeli <warunek> To

Czynność

Warunek

Czynność

Przełącznik

Czynność1

Czynność2

Czynność3

Czynność4

JeŜeli <warunek> To

Czynność1

W przeciwnym razie

Czynność2

Warunek

Czynność2

Czynność1

Wyj

II PWr

Algorytm – iteracje „dopóki” i „powtarzaj”

Algorytm – iteracje „dla”

Dopóki <warunek> Wykonaj

Czynność

Warunek

Dla i=1 Do n Wykonaj

Czynność

i=1

Czynność

i<=n

Czynność

Powtarzaj

Czynność

AŜ <warunek>

i=i+1

Czynność

Warunek

II PWr

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: