Maksimum tablicy
Znajdź maksimum [4, 9, 2].
- 1. Dane: tablica liczb.
- 2. Wynik: jedna liczba — największy element.
- 3. Założenie: tablica nie jest pusta.
Odpowiedź: Wynik: 9.
Nauka od podstaw · Informatyka · Klasa 7
Algorytmy — specyfikacja, wyszukiwanie i testowanie — wyjaśnienie krok po kroku
Nie zaczynaj od kodu. Najpierw określ problem, dane wejściowe i wynik, potem zapisz jednoznaczne kroki, prześledź je na małym przykładzie i dopiero na końcu myśl o implementacji. To samo rozumowanie działa w pseudokodzie i w różnych językach programowania.
Po tej lekcji
- ✓ zapisać specyfikację problemu jako dane wejściowe i oczekiwany wynik
- ✓ przedstawić algorytm jako jednoznaczną listę kroków
- ✓ prześledzić instrukcję warunkową, pętlę i zmiany wartości zmiennych
- ✓ wyjaśnić i zastosować wyszukiwanie liniowe w zbiorze nieuporządkowanym
- ✓ prześledzić sortowanie przez proste wybieranie
- ✓ dobierać testy, wykrywać przypadki brzegowe i proste błędy algorytmiczne
Najpierw specyfikacja: dane i wynik
Specyfikacja problemu odpowiada na dwa podstawowe pytania: jakie dane otrzymuje rozwiązanie oraz jaki wynik ma zwrócić. Bez tego nawet poprawnie napisany kod może rozwiązywać inne zadanie niż zamierzaliśmy.
Ważne są także założenia. Dla problemu „znajdź maksimum” trzeba wiedzieć, czy wejście może być puste, jakiego typu są elementy i w jakiej postaci ma zostać zwrócony wynik.
Reguły, które warto zapamiętać
- • Najpierw zdefiniuj wejście i wyjście.
- • Przypadki brzegowe są częścią specyfikacji, a nie dodatkiem po napisaniu programu.
Algorytm, pseudokod i śledzenie
Algorytm to skończony, jednoznaczny sposób rozwiązania problemu. Można go przedstawić językiem naturalnym, listą kroków, pseudokodem lub zaimplementować w języku programowania.
Śledzenie algorytmu polega na ręcznym wykonywaniu kolejnych instrukcji dla małych danych. Przy warunkach zapisuj, czy wyrażenie jest prawdziwe, a przy pętlach notuj wartości najważniejszych zmiennych po każdej iteracji.
Reguły, które warto zapamiętać
- • Nie zgaduj wyniku programu — wykonuj instrukcje po kolei.
- • Algorytm jest ideą rozwiązania; program jest konkretną implementacją tej idei.
Wyszukiwanie liniowe
Gdy zbiór jest nieuporządkowany, podstawową metodą wyszukiwania jest sprawdzanie elementów po kolei. Kończymy, gdy znajdziemy szukaną wartość albo gdy sprawdzimy wszystkie elementy.
Specyfikacja musi określić wynik także wtedy, gdy elementu nie ma. Może to być wartość logiczna, specjalna pozycja albo inna jednoznaczna informacja — ważne, aby użytkownik algorytmu wiedział, co oznacza wynik.
Reguły, które warto zapamiętać
- • Nieuporządkowanie oznacza, że w najgorszym przypadku trzeba sprawdzić cały zbiór.
- • Zaprojektuj jawnie przypadek „nie znaleziono”.
Szukamy 5
[7, 3, 11, 5, 9]
- 1. 7 ≠ 5
- 2. 3 ≠ 5
- 3. 11 ≠ 5
- 4. 5 = 5 — stop
Odpowiedź: Element znaleziony po 4 porównaniach.
Sortowanie przez proste wybieranie
W rosnącym sortowaniu przez wybieranie dzielimy tablicę na część już uporządkowaną i jeszcze nieuporządkowaną. W nieuporządkowanej części znajdujemy najmniejszy element i umieszczamy go na początku tej części.
Po każdym kroku uporządkowana część rośnie o jeden element. Metoda jest prosta do prześledzenia ręcznie i dobrze pokazuje, jak większy problem można rozbić na powtarzalne kroki.
Reguły, które warto zapamiętać
- • W każdym kroku szukaj minimum tylko w jeszcze nieuporządkowanej części.
- • Nie zmieniaj już ustalonego prefiksu tablicy bez powodu.
Pierwszy wybór
[6, 2, 5, 3]
- 1. Minimum całej części: 2.
- 2. Zamień 2 z pierwszym elementem 6.
Odpowiedź: [2, 6, 5, 3]
Warunki, pętle i debugowanie
Instrukcja warunkowa wybiera jedną z dróg wykonania na podstawie wartości logicznej. Pętla pozwala powtarzać instrukcje. Przy pętli warunkowej zawsze sprawdzaj, czy wykonywane instrukcje mogą kiedyś zmienić warunek zakończenia.
Debugowanie zaczyna się od odtworzenia stanu programu: jakie wartości mają zmienne przed instrukcją i po niej. Prosta tabela śledzenia często szybciej pokazuje błąd niż przypadkowe zmienianie kodu.
Reguły, które warto zapamiętać
- • Warunek musi dać się jednoznacznie ocenić jako prawda albo fałsz.
- • W pętli „dopóki” sprawdź, czy stan zbliża się do zakończenia.
Testowanie poprawności
Jedno poprawne uruchomienie nie dowodzi poprawności rozwiązania. Testuj przypadki typowe, najmniejsze dozwolone wejścia, dane z powtórzeniami, wartości ujemne, a także sytuacje, w których szukany element nie występuje — zależnie od specyfikacji.
Najpierw określ oczekiwany wynik testu, a dopiero potem uruchom algorytm. Jeśli wynik jest inny, śledź wykonanie krok po kroku i znajdź pierwsze miejsce, w którym stan przestaje odpowiadać oczekiwaniu.
Reguły, które warto zapamiętać
- • Test powinien mieć znany oczekiwany wynik.
- • Przypadki brzegowe wynikają ze specyfikacji problemu.
Test maksimum
Jak sprawdzić funkcję maksimum?
- 1. [5] → 5
- 2. [-8, -2, -10] → -2
- 3. [4, 9, 9, 1] → 9
Odpowiedź: Zestaw obejmuje jeden element, liczby ujemne i powtórzone maksimum.
Materiały i dalsza nauka
Linki są dobierane z opublikowanych materiałów na podstawie relacji tematu, a nie podobieństwa słów w tytule.
Materiały do tego tematu
Inne formy pracy nad dokładnie tym samym zagadnieniem.
Quiz diagnostyczny
Sprawdź, które elementy tematu już rozumiesz
Działa bez konta. Po odpowiedzi od razu zobaczysz jednoznaczny wynik i wyjaśnienie.
0/8
1. Co powinna zawierać podstawowa specyfikacja problemu?
2. Jaki jest podstawowy pomysł wyszukiwania liniowego w nieuporządkowanej tablicy?
3. Co robi rosnące sortowanie przez proste wybieranie?
4. Pętla „dopóki i <= 3” nie zmienia i. Jakie jest główne ryzyko?
5. Który test najlepiej sprawdza przypadek brzegowy funkcji maksimum dla niepustej tablicy?
6. Czym różni się algorytm od programu?
7. Po co ręcznie śledzić wartości zmiennych?
8. Co należy zrobić, jeśli „znajdź maksimum” dopuszcza pustą tablicę?
Następny krok
Przećwicz temat „Algorytmy — specyfikacja, wyszukiwanie i testowanie”
Jeżeli przygotowujesz się do sprawdzianu, wybierz dopasowany materiał dla tego tematu i klasy albo wygeneruj własny zestaw.