Od problemu do algorytmu - Zintegrowana Platforma Edukacyjna

Komputer jest urządzeniem, które działa na podstawie precyzyjnie określonych przepisów, znanych jako instrukcje programu. Te instrukcje, stworzone przez ludzi, pozwalają komputerowi na rozwiązywanie różnorodnych problemów i wykonywanie różnych zadań. Więcej o działaniu komputerów i ich roli dowiesz się w materiałach:

Komputery wokół nasD1NVKqZ8oKomputery wokół nas
Rola komputera w informatyceD14nDUj53Rola komputera w informatyce

Czy zdajesz sobie sprawę, że przepisy, które opisują rozwiązania problemów, towarzyszą nam również w życiu codziennym? Kiedy gotujesz, stosujesz przepisy kulinarne, które określają, jakich składników należy użyć i jakie kroki wykonać, aby przygotować smaczne danie. Podobnie, gdy budujesz mebel z zestawu, stosujesz instrukcje montażu, które krok po kroku wskazują, jak złożyć poszczególne elementy, aby uzyskać ostateczny produkt.

Przepisy, czy to w formie programów komputerowych, przepisów kulinarnych czy instrukcji montażu, to narzędzia, które pomagają nam rozwiązywać problemy i wykonywać zadania w sposób zorganizowany i efektywny. Dlatego zrozumienie, jak one działają i jak je tworzyć, może być kluczowym elementem w rozwijaniu naszych umiejętności w różnych dziedzinach życia.

Specyfikacja i algorytmy

Ścisły przepis rozwiązania problemu nazywamy algorytmemalgorytmalgorytmem, każdy algorytm powinien również mieć swoją specyfikację. Jest to precyzyjny opis problemu algorytmicznego, danych wejściowych (danych) oraz danych wyjściowych (wyników).

Mając określony cel i specyfikację, należy przejść do analizy postawionego przed nami problemu, pomyśleć nad najlepszymi znanymi nam sposobami jego rozwiązania i zastanowić się, czy będą one skuteczne. Po wyborze i opracowaniu rozwiązania, na przykład w postaci listy kroków, stworzony algorytm powinno się sprawdzić dla przykładowych danych zgodnych ze specyfikacją. Ostanim etapem jest przejście do jego realizacji, na przykład, w formie programu. W poniższych ćwiczeniach skupimy się na zdefiniowaniu problemu, zapisie jego specyfikacji i analizie. Następnie zapiszemy algorytm rozwiązania problemu w postaci listy kroków. Informacje o tym, jak tworzyć programy na podstawie napisanych wcześniej algorytmów znajdziesz w materiale Od algorytmu do programuD11xliCilOd algorytmu do programu.

Mając zdefiniowany problem, zapiszemy specyfikację. Zapoznaj się z przykładami przedstawionymi poniżej, a następnie wykonaj powiązane ćwiczenia.

Przykład 1

Polecenie:

Dane są trzy liczby naturalne dodatnie. Zapisz specyfikację problemu obliczania iloczynu tych liczb.

Specyfikacja:

Problem: Obliczanie iloczynu trzech liczb naturalnych dodatnich.

Dane:

$a$ – liczba naturalna dodatnia
$b$ – liczba naturalna dodatnia
$c$ – liczba naturalna dodatnia

Wynik:

$d$ – liczba naturalna, będąca iloczynem liczb naturalnych $a$ , $b$ , $c$

Ćwiczenie 1

Na podstawie przykładowej specyfikacji algorytmu, zapisz specyfikację obliczania średniej arytmetycznej pięciu liczb rzeczywistych.

Specyfikacja:

Problem: Obliczanie średniej arytmetycznej pięciu liczb rzeczywistych.

Dane:

$a$ – liczba rzeczywista
$b$ – liczba rzeczywista
$c$ – liczba rzeczywista
$d$ – liczba rzeczywista
$e$ – liczba rzeczywista

Wynik:

$ś r$ – liczba rzeczywista, będąca średnią arytmetyczną pięciu liczb rzeczywistych $a, b, c, d, e$

Ćwiczenie 2

Stwórz odpowiednią specyfikację dla problemu konstruowania trójkąta równobocznego o boku $x$ . Końcowy trójkąt równoboczny oznacz jako ABC.

Warunkiem jest, aby długość boku konstruowanego trójkąta równobocznego była liczbą naturalną (całkowitą dodatnią).

Specyfikacja:

Problem: Konstruowanie trójkąta równobocznego.

Dane:

$x$ – długość boku trójkąta równobocznego, liczba naturalna

Wynik:

ABC – trójkąt równoboczny o długości boku $x$

Jeśli lubisz bawić się klockami Lego lub sklejać różne modele (np. samolotu lub samochodu), to wraz z klockami lub elementami modelu do sklejania znajdziesz książkę (specyfikację) z listą wszystkich klocków oraz instrukcję, opisującą krok po kroku, które klocki (elementy) i w jakiej kolejności należy składać (sklejać), aby otrzymać określony model.

Zapis algorytmu (przepisu) w postaci kolejnych kroków nazywamy listą kroków. Lista kroków jest listą numerowaną, w której każdy krok algorytmu ma swój numer. Algorytm zawsze jest realizowany w skończonej liczbie kroków.

Każdy algorytm powinien posiadać następujące cechy:

Poprawność – dla danych zgodnych ze specyfikacją zostanie zwrócony poprawny wynik.
Jednoznaczność – te same dane, dają ten sam wynik.
Uniwersalność – algorytm ma służyć do rozwiązania pewniej grupy zadań, a nie pojedynczego przypadku.
Efektywność – powinien prowadzić do rozwiązania w jak najmniejszej liczbie kroków.
Skończoność – algorytm powinien zakończyć działanie po skończonym czasie lub liczbie kroków.

Jak już zostało wspomniane, postawiony problem nie zawsze musi być matematyczny, a dotyczyć może prostych czynności z życia codziennego, tak, jak w poniższym przykładzie.

Przykład 2

Polecenie:

Zapisz w postaci listy kroków sposób wiązania sznurówek metodą z uszami króliczka, która polega na tworzeniu pętelek na sznurówkach i związywaniu ich ze sobą.

Specyfikacja:

Problem: wiązanie sznurówek metodą z uszami króliczka.

Dane: Sznurówka na bucie.

Wynik: Zasznurowane buty.

Lista kroków:

Skrzyżuj sznurówki, tak aby powstała litera X.
Jedną ze sznurówek owiń wokół drugiej, przekładając ją pod literką X.
Pociągnij za sznurówki, aby zacieśnić wiązanie - w ten sposób powstaje pierwszy supełek.
Na każdej części sznurówki utwórz pętelkę, tzw. uszy króliczka.
Skrzyżuj dwie pętelki ze sobą, po czym jedną z nich owiń wokół drugiej tak, aby powstał kolejny supełek.
Pociągnij za uszy króliczka, aby zaciągnąć supełek i zabezpieczyć wiązanie.

Ćwiczenie 3

Przeanalizuj problem, a następnie opisz proces konstruowania trójkąta równobocznego o boku długości $p$ . Na podstawie powyżej przedstawionej przykładowej listy kroków, podaj przepis, który pozwoli osiągnąć zamierzony cel. Opis powinien być na tyle szczegółowy, aby osoba nieobeznana z tematem bez problemu mogła go zrozumieć i powtórzyć czynność.

R1TdIGXeuNAAV

Notes.

Źródło: GroMar, licencja: CC BY 3.0.

Przykładem może być instrukcja konstruowania pięciokąta foremnego pokazana na animacji. W tej animacji pokazane są kolejne kroki, które należy wykonać, aby odtworzyć tę figurę.

Re01FzizdQx75

Prezentacja przedstawiająca konstrukcję pięciokąta foremnego.

Źródło: A.Koludo, K.Koludo-Durkiewicz, licencja: CC BY 3.0.

Przykładowy przepis na narysowanie pięciokąta foremnego

Rysujemy prostą $k$ i zaznaczamy na niej punkt $A$ .
Kreślimy okrąg o środku w punkcie $A$ i promieniu $p$ .
Wyznaczamy punkty przecięcia okręgu z prostą i nazywamy je $B$ oraz $C$ .
Wyznaczamy prostą prostopadłą do prostej $k$ . W tym celu z punktów $B$ oraz $C$ kreślimy łuk o promieniu $r$ , który równy jest średnicy wcześniej narysowanego okręgu. Wyznaczamy punkty przecięcia łuków $D$ oraz $E$ , a następnie rysujemy przechodzącą przez nie prostą $l$ .
Z punktu $C$ kreślimy łuk o promieniu $p$ . W miejscach ich przecięcia z okręgiem wyznaczamy punkty $E$ oraz $F$ , następnie łączymy je odcinkiem $EF$ .
W miejscu przecięcia odcinka $EF$ z prostą $k$ wyznaczamy punkt $G$ . Mierzymy jego odległość od punktu $D$ , będzie to promień $s$ .
Z punktu $G$ kreślimy łuk o promieniu $s$ . W jego punkcie styku z prostą $k$ wyznaczamy punkty $H$ (wewnątrz okręgu) oraz $I$ (na zewnątrz okręgu).
Mierzymy odległość odcinka $HD$ , będzie to promień $t$ . Z punktu $D$ kreślimy łuk o promieniu $t$ . W jego punktach styku z okręgiem wyznaczamy punkty $J$ oraz $K$ .
Mierzymy odległość odcinka $DI$ , będzie to promień $u$ .
Z punktu $D$ kreślimy łuk o promieniu $u$ ; w jego punktach styku z okręgiem wyznaczamy punkty $L$ oraz $M$ .
Punkty: $D$ , $J$ , $L$ , $M$ oraz $K$ to wierzchołki pięciokąta foremnego.
Łączymy wierzchołek $J$ z wierzchołkiem $D$ .
Łączymy wierzchołek $D$ z wierzchołkiem $K$ .
Łączymy wierzchołek $J$ z wierzchołkiem $L$ .
Łączymy wierzchołek $L$ z wierzchołkiem $M$ .
Łączymy wierzchołek $M$ z wierzchołkiem $K$ – w ten sposób skończyliśmy konstrukcję pięciokąta foremnego.

Jest to również wskazówka, jaką metodą można spróbować narysować trójkąt równoboczny za pomocą cyrkla i linijki.

Przykładowa analiza konstruowania trójkąta równobocznego:

Jak narysować trójkąt równoboczny, czyli taki, który ma wszystkie boki tej samej długości, korzystając z cyrkla i linijki? Okrąg to figura geometryczna, która składa się ze wszystkich punktów leżących w tej samej odległości od środka. Chcemy znaleźć trzy punkty, które będą wierzchołkami trójkąta równobocznego. Jeśli narysujemy okrąg o zadanym promieniu, a następnie za środek drugiego okręgu o tym samym promieniu weźmiemy dowolny punkt na pierwszym okręgu, dostaniemy punkty przecięcia okręgów, które możemy potraktować jako wierzchołki trójkąta równobocznego. Wystarczy połączyć punkt przecięcia okręgu ze środkami narysowanych okręgów.

Przykładowy przepis na narysowanie trójkąta równobocznego

Rysujemy prostą $k$ i zaznaczamy na niej punkt $A$ .
Kreślimy okrąg o środku w punkcie $A$ i promieniu $p$ .
Wyznaczamy punkt przecięcia okręgu z prostą i nazywamy go $B$ .
Kreślimy okrąg o środku w $B$ i promieniu $p$ .
Wyznaczamy punkty przecięcia okręgów i nazywamy jeden z nich $C$ .
Kreślimy trójkąt równoboczny $ABC$ .

Przykład 3

Na matematyce uczysz się o działaniach arytmetycznych na liczbach naturalnych. Może znasz metodę mnożenia dowolnej liczby od $1$ do $10$ przez $9$ z wykorzystaniem palców obu rąk?

R9lwcjbr68nKZ

Rysunek przedstawia dwie dłonie, skierowane kciukami na zewnątrz. Na każdym z palców (licząc od lewej strony) znajdują się liczby od jeden do dziesięciu. — Mnożenie w pamięci liczby od 1 do 10 przez 9 na palcach
Źródło: Janusz Wierzbicki, Maciej Borowiecki, licencja: CC BY 3.0.

Ćwiczenie 4

Zapisz algorytm mnożenia w pamięci dowolnej liczby od $1$ do $10$ (nazwijmy ją x) przez $9$ wraz ze specyfikacją. Algorytm zapisz w postaci listy kroków, a następnie przetestuj go podstawiając pod x wybrane przez siebie liczby.

RexUMRkOPqbTh

Notes.

Źródło: GroMar, licencja: CC BY 3.0.

Ćwiczenie można zrealizować na różne sposoby. Jedną z możliwości jest wykorzystanie swoich palców. Aby pomnożyć liczbę od $1$ do $10$ przez $9$ , wyprostuj swoje dłonie i zegnij palec odpowiadający danej liczbie (od lewej strony) - miejsce zgięcia podzieli palce na dwie grupy. Teraz wystarczy pomnożyć liczbę palców w odpowiedniej grupie przez $10$ i dodać do liczby palców w drugiej grupie.

Specyfikacja algorytmu:

Problem: Mnożenie w pamięci dowolnej liczby od $1$ do $10$ przez $9$ .

Dane:

x - wybrana liczba naturalna z przedziału od $1$ do $10$

Wynik:

W - liczba naturalna, wynik operacji mnożenia liczby x przez $9$

Przykładowa lista kroków:

Ustaw dłonie spodem do twarzy, tak jak na poniższym rysunku;
R9lwcjbr68nKZ
Mnożenie w pamięci liczby od 1 do 10 przez 9 na palcach
Źródło: Janusz Wierzbicki, Maciej Borowiecki, licencja: CC BY 3.0.
Zegnij palec na miejscu x (zgodny z liczbą, przez którą mnożysz $9$ ), licząc od kciuka lewej dłoni;
Pomnóż liczbę wyprostowanych palców po lewej stronie (od kciuka lewej dłoni do zgiętego palca) przez $10$ ;
Dodaj do wyniku liczbę wyprostowanych palców po prawej stronie (od zgiętego palca do kciuka prawej dłoni);
Przedstaw wynik W.

Ważne!

Zwróć uwagę, że kolega lub koleżanka może podać inny algorytm na obliczenie wyniku mnożenia liczby od $1$ do $10$ przez $9$ , np. z wykorzystaniem tradycyjnej tabliczki mnożenia lub kilkukrotnie dodając do siebie liczbę $9$ .

Ćwiczenie 5

Przeanalizuj problem, podaj specyfikację i zapisz w postaci listy kroków algorytm na rysowanie kwadratu o długości boku równej x.

Ćwiczenie 6

Przeanalizuj problem, podaj specyfikację i zapisz w postaci listy kroków co najmniej dwa różne algorytmy rysowania poniższej figury. Bok mniejszego kwadratu określ jako x, a otrzymaną figurę oznacz jako Fx.

R11NpmdTGibT9

Ilustracja przedstawia kwadrat wewnątrz, zbudowany z czerech mniejszych kwadratów. — Kwadrat się z mniejszych kwadratów.
Źródło: Janusz Wierzbicki, Maciej Borowiecki, licencja: CC BY 3.0.

Specyfikacja algorytmu:

Problem: Narysowanie kwadratu zbudowanego z czterech mniejszych kwadratów o boku x.

Dane:

x - długość boku mniejszego kwadratu

Wynik:

Fx - figura zbudowana z kwadratów o boku x

Przykładowy algorytm:

Sposób pierwszy - Rysowanie krzyża w środku i zewnętrznego kwadratu:

Przyłóż pisak.
Powtórz 4 razy:
2.1. Przesuń o x kroków;
2.2. Przesuń o x kroków wstecz;
2.3. Obróć w prawo o 90 stopni;
Zamień pozycję o x kroków w lewo oraz x kroków do góry i obróć w prawo o 90 stopni;
Powtórz 4 razy:
4.1. Przesuń o 2 $\times$ x kroków;
4.2. Obróć w prawo o 90 stopni;
Zamień pozycję o x kroków w prawo, obróć o 90 stopni prawo i przesuń x kroków do dołu (warto zakończyć algorytm w tym samym miejscu, w którym rozpoczęto rysowanie);

RoWin7gF8bn9n

Animacja przedstawia skorupę żółwia, który krok po kroku rysuję figurę złożoną z czterech kwadratów. Kwadraty znajdują się na sobie, dwa na górze, dwa na dole. Razem tworzą większy kwadrat z liniami w środku większego kwadratu. — Skorupa żółwia rysuje figurę składającą się z czterech kwadratów według podanego algorytmu.
Źródło: GroMar, licencja: CC BY 3.0.

Sposób drugi - Rysowanie 4 kwadratów:

Przyłóż pisak;
Powtórz 4 razy:
2.1. Powtórz 4 razy:
⠀ 2.1.1. Przesuń o x kroków;
⠀ 2.1.2. Obróć w prawo o 90 stopni;
2.2. Obróć w prawo o 90 stopni;

RZrYH4nwZUoow

Animacja przedstawia żółwia, który krok po kroku rysuję figurę złożoną z czterech kwadratów. Kwadraty znajdują się na sobie, dwa na górze, dwa na dole. Razem tworzą większy kwadrat z liniami w środku większego kwadratu. — Żółw rysuje figurę złożoną z czterech kwadratów według podanego algorytmu.
Źródło: GroMar, licencja: CC BY 3.0.

algorytm