Kwalifikacje w Zawodzie - Testy zawodowe online | Egzaminy Zawodowe

KWALIFIKACJA INF2 + INF3 - CZERWIEC 2012



PYTANIE NR 24.
Algorytm wczytuje n oraz x1…xn, ustawia m := x1, im := 1, i := 2. Następnie dla kolejnych elementów: jeśli m > xi, to m := xi oraz im := i; po każdej iteracji wykonuje i := i + 1; na końcu wyprowadza m i im. Co wyznacza ten algorytm?
A.
B.
C.
D.
Wyjaśnienie poprawnej odpowiedzi:
Algorytm przechodzi po wszystkich elementach ciągu, startując od m := x1. Gdy znajdzie element mniejszy (warunek m > x_i), aktualizuje m oraz zapamiętuje jego pozycję im. Inkrementacja i := i + 1 zapewnia przejście przez cały ciąg, więc wynikiem jest minimum.

Pełne wyjaśnienie:

Opisany algorytm jest klasycznym algorytmem znajdowania minimum w nieuporządkowanym ciągu o złożoności czasowej O(n), ponieważ wykonuje jedno przejście po danych i porównuje kolejne elementy z bieżącym minimum.

Kluczowe kroki:

  • Inicjalizacja: m := x1 zakłada, że pierwsza wartość jest na start najlepszym (najmniejszym) kandydatem. im := 1 zapamiętuje jej indeks.
  • Iteracja: i := 2 oznacza, że porównania zaczynają się od drugiego elementu.
  • Porównanie: warunek m > xi sprawdza, czy znaleziono wartość mniejszą od dotychczasowego minimum. Jeśli tak, to aktualizacja m := xi ustawia nowe minimum, a im := i zapisuje jego pozycję.
  • Inkrementacja licznika: i := i + 1 jest konieczna, aby przejść do następnego elementu i zakończyć pętlę po sprawdzeniu wszystkich danych.
  • Wyjście: na końcu wyprowadzane są m (wartość minimalna) i im (jej indeks).

Dlaczego pozostałe odpowiedzi są niepoprawne?

  • "najmniejszej wspólnej wielokrotności dwóch liczb" nie pasuje, bo algorytm nie operuje na dwóch liczbach, nie wykonuje dzielenia ani wielokrotności, tylko przegląda listę i porównuje elementy.
  • "liczby maksymalnej w ciągu nieuporządkowanym" byłaby prawdziwa, gdyby warunek był odwrócony (np. m < xi) i aktualizował m przy większych wartościach. Tutaj aktualizacja następuje przy znalezieniu mniejszego elementu.
  • "największego wspólnego dzielnika dwóch liczb" zwykle opiera się na algorytmie Euklidesa (operacje modulo/odejmowania). W tym algorytmie nie ma takich działań ani struktury typowej dla NWD.

Wskazówka egzaminacyjna: aby szybko rozpoznać algorytm, zwróć uwagę na inicjalizację wyniku pierwszym elementem oraz na to, czy aktualizacja wyniku następuje dla wartości mniejszej czy większej.

Dodatkowe pytania

Dodatkowe pytania (FAQ):
Co to jest algorytm znajdowania minimum w ciągu?
To algorytm, który w jednym przebiegu po elementach porównuje kolejne wartości z aktualnym minimum. Startuje zwykle od pierwszego elementu jako kandydata, a gdy znajdzie mniejszy element, aktualizuje wynik. Działa w czasie O(n).
Jak działa warunek m > x_i w takim algorytmie?
Warunek m > x_i sprawdza, czy bieżące minimum m jest większe od aktualnie oglądanego elementu. Jeśli tak, oznacza to znalezienie mniejszej wartości, więc należy ustawić m := x_i i (opcjonalnie) zapamiętać indeks tej wartości.
Dlaczego trzeba wykonać i := i + 1 w pętli?
Inkrementacja licznika przesuwa algorytm do następnego elementu danych. Bez kroku i := i + 1 algorytm wciąż porównywałby ten sam element, nie kończąc pracy. To jeden z najczęstszych błędów w schematach blokowych i pseudokodzie.
Co oznacza zmienna im w algorytmie minimum?
Zmienna im przechowuje indeks (pozycję) elementu, który jest aktualnym minimum. Gdy algorytm znajdzie mniejszą wartość i zaktualizuje m, powinien równocześnie ustawić im := i, aby pamiętać, gdzie to minimum wystąpiło.
Jak odróżnić algorytm minimum od algorytmu maksimum?
Sprawdź kierunek nierówności w porównaniu. Dla minimum typowe jest "jeśli m > x_i, to aktualizuj m", bo szukamy mniejszej wartości. Dla maksimum byłoby odwrotnie: "jeśli m < x_i, to aktualizuj m".
Czy algorytm minimum zawsze ma złożoność O(n)?
Dla przeglądu nieuporządkowanego ciągu tak: trzeba obejrzeć każdy element co najmniej raz, aby mieć pewność, że znaleziono minimum. Dlatego czas rośnie liniowo wraz z liczbą elementów n, czyli O(n).
Jakie błędy najczęściej pojawiają się w schematach blokowych takich algorytmów?
Najczęstsze są: brak inkrementacji licznika pętli (powoduje zapętlenie), odwrócony warunek porównania (daje maksimum zamiast minimum), błędna inicjalizacja (np. m := 0), oraz pomylenie operacji wyjścia z wejściem danych.
Czy w algorytmie minimum trzeba obsługiwać pusty ciąg?
W praktycznych programach tak, bo dla n = 0 nie ma sensu ustawiać m := x1. Na egzaminach często zakłada się, że n ≥ 1, ale warto umieć wskazać, że przypadek pustych danych wymaga osobnej obsługi (np. komunikatu o braku danych).
Gdzie w aplikacjach internetowych wykorzystuje się wyszukiwanie minimum?
W webaplikacjach minimum może oznaczać np. najniższą cenę w wynikach wyszukiwania, minimalny czas odpowiedzi serwera w logach, najmniejszą wartość pomiaru z czujnika IoT, czy wybór najtańszego wariantu w koszyku/porównywarce.
Jak przećwiczyć rozpoznawanie algorytmu z opisu lub schematu?
Weź krótką listę liczb (np. 5 elementów) i przejdź algorytm "ręcznie", zapisując m, im i i po każdym kroku. Zwróć uwagę, kiedy następuje aktualizacja m oraz czy i się zmienia. To najszybszy sposób na uniknięcie pomyłek na teście.
info

To pytanie poprawnie rozwiązuje 64% zdających egzamin. średnie

Eksperci podkreślają: "Algorytm przechodzi po wszystkich elementach ciągu, startując od m := x1."

Źródła:

  • Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., "Introduction to Algorithms", 3rd edition, rozdz. 2 (analiza algorytmów) oraz przykłady algorytmów liniowych, 2009.
  • https://pl.wikipedia.org/wiki/Minimum - dostęp: 2026-04-02
  • https://en.wikipedia.org/wiki/Selection_algorithm - dostęp: 2026-04-02

Materiały:

  • Cormen, Leiserson, Rivest, Stein: "Wprowadzenie do algorytmów" (rozdziały o podstawach analizy i prostych algorytmach liniowych)
  • Materiały dydaktyczne z podstaw programowania: pętle, zmienne sterujące, schematy blokowe
  • Ćwiczenia: ręczne przejście algorytmu minimum/maksimum dla przykładowych danych
Zobacz też:

Aktualizacja pytania: 03.04.2026



Aktualizacja pytania: 03.04.2026
📡 Brak połączenia internetowego