Do rozwiązywania problemów możemy wykorzystać komputery. Aby jednak mogły to zrobić, muszą być odpowiednio zaprogramowane.
Żeby maszyna rozwiązała problem, trzeba go najpierw rozpracować na najdrobniejsze szczegóły.
Opis słowny algorytmu wydawania reszty.
Dane: Kwota pieniędzy do wydania, nominały banknotów i bilonu uporządkowane malejąco
Wyniki: Ilość poszczególnych nominałów banknotów i bilonu
Krok 1: Ustalenie wartości początkowych
Krok 2: Sprawdzamy, ile razy najwyższy nominał mieści się w kwocie do wydania
Krok 3: Obliczamy resztę do wydania: poprzednia kwota - obliczona ilość * nominał
Krok 4: Przechodzimy do niższego nominału
Krok 5: Jeśli reszta do wydania = 0 [stop] w przeciwnym razie powtarzamy kroki 2 - 4
Algorytm wydawania reszty:
program wydawanie_reszty; uses crt; var reszta : longint;
begin
clrscr;
writeln('podaj kwote: '); readln(reszta); writeln;
writeln(reszta div 200, ' banknotow 200zl');
reszta:=reszta mod 200;
writeln(reszta div 100, ' banknotow 100zl');
reszta:=reszta mod 100;
writeln(reszta div 50, ' banknotow 50zl');
reszta:=reszta mod 50;
writeln(reszta div 20, ' banknotow 20zl');
reszta:=reszta mod 20;
writeln(reszta div 10, ' banknotow 10zl');
reszta:=reszta mod 10;
writeln(reszta div 5, ' monet 5zl');
reszta:=reszta mod 5;
writeln(reszta div 2, ' monet 2 zl');
reszta:=reszta mod 2;
writeln(reszta, ' monet 1 zl');
repeat until keypressed;
end.
Problem plecakowy:
Należy wybrać elementy z dostępnego zbioru tak, by ich sumaryczna wartość była jak największa i jednocześnie zmieściły się w plecaku. Niedozwolone jest dzielenie przedmiotów na części dla lepszego wykorzystania objętości plecaka.
Człowiek, który pakuje plecak kieruje się jedną z trzech strategii:
- najpierw wkłada do plecaka rzeczy największe i dokłada do nich coraz mniejsze,
- najpierw wybiera rzeczy najważniejsze dla niego, potem dokłada te mniej ważne,
- pakuje, szacując wartość kolejnych wkładanych przedmiotów z uwzględnieniem obu cech jednocześnie (lepiej zabrać rzecz dużą, ale bardzo dla nas ważną, niż małą, lecz nieistotną).
Pierwsza metoda jest mniej efektywna, ostatnia pozwala zmieścić w plecaku najwięcej rzeczy.
Cechy algorytmów:
- poprawność (daje dobre wyniki),
- jednoznaczność (daje takie same wyniki przy takich samych danych),
- skończoność (wykonuje się w skończonej ilości kroków),
- sprawność (czasowa i pamięciowa)
Rekurencja jest bardzo znanym i często nieświadomie stosowanym sposobem postępowania. Jest to sposób definiowania rzeczy, gdy w treści definicji używamy tego samego pojęcia, które definiujemy. Rekurencja skraca i upraszcza opis schematu postępowania.
Zadanie domowe
Zad. 1
a) Ziemia
Dane: masa ciała, przyspieszenie ziemskie = 10
m/s2
Wynik: ciężar ciała
Krok 1.: Ustalenie wartości początkowych.
Krok 2.: Zapisujemy wzór na ciężar ciała.
Krok 3.: Wstawiamy do wzoru masę ciała.
Krok 4.: Wstawiamy do wzoru wartość przyspieszenia, w tym przypadku 10
m/s2
Krok 5.: Obliczamy według wzoru:
Krok 6.: Otrzymujemy wynik.
b) Księżyc
Dane: masa ciała, przyspieszenie=
1,622 m/s²
Wynik: ciężar ciała
Krok 1.: Ustalenie wartości początkowych.
Krok 2.: Zapisujemy wzór na ciężar ciała.
Krok 3.: Wstawiamy do wzoru masę ciała.
Krok 4.: Wstawiamy do wzoru wartość przyspieszenia, w tym przypadku
.1,622 m/s²
Krok 5.: Obliczamy według wzoru:
Krok 6.: Otrzymujemy wynik.
c) Mars
Dane: masa ciała, przyspieszenie=
3,69 m/s2
Wynik: ciężar ciała
Krok 1.: Ustalenie wartości początkowych.
Krok 2.: Zapisujemy wzór na ciężar ciała.
Krok 3.: Wstawiamy do wzoru masę ciała.
Krok 4.: Wstawiamy do wzoru wartość przyspieszenia, w tym przypadku
3,69 m/s2.
Krok 5.: Obliczamy według wzoru:
Krok 6.: Otrzymujemy wynik.
d) Wenus
Dane: masa ciała, przyspieszenie=
8,87 m/s2
Wynik: ciężar ciała
Krok 1.: Ustalenie wartości początkowych.
Krok 2.: Zapisujemy wzór na ciężar ciała.
Krok 3.: Wstawiamy do wzoru masę ciała.
Krok 4.: Wstawiamy do wzoru wartość przyspieszenia, w tym przypadku
8,87 m/s2.
Krok 5.: Obliczamy według wzoru:
Krok 6.: Otrzymujemy wynik.
