Podciągi o zadanych własnościach

Wiele zadań maturalnych pyta o fragment ciągu z jakąś własnością: najdłuższy niemalejący, o największej sumie, o stałej różnicy. Sprawdzanie wszystkich fragmentów zajmuje około n² kroków. Wystarczy jednak jedno przejście pętli: algorytm pamięta, co wie o fragmencie kończącym się na bieżącym wyrazie, i najlepszy wynik do tej pory.

Każdy przykład przejdziesz krok po kroku w kursie Algorytmy: zakres rozszerzony: w przeglądarce, bez instalowania niczego i bez konta.

Przejdź najdłuższy podciąg niemalejący krok po kroku

Najdłuższy spójny podciąg niemalejący

Licznik length mówi, ile wyrazów ma niemalejący fragment kończący się na bieżącym wyrazie. Gdy wyraz jest mniejszy od poprzedniego, fragment zaczyna się od nowa:

values = [1, 2, 2, 1, 3, 4, 5, 0]
length = best = 1
for i in range(1, len(values)):
    if values[i] >= values[i - 1]:
        length += 1
    else:
        length = 1
    best = max(best, length)
print(best)

4

Najdłuższy fragment to 1, 3, 4, 5. Zmiana warunku na > daje fragment rosnący, a na values[i] - values[i - 1] == values[i - 1] - values[i - 2] fragment o stałej różnicy.

Maksymalna suma spójnego podciągu

Algorytm Kadane pamięta current: największą sumę fragmentu kończącego się na bieżącym wyrazie. Albo przedłuża poprzedni fragment, albo zaczyna nowy, gdy poprzednia suma tylko by przeszkadzała:

values = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
current = best = values[0]
for x in values[1:]:
    current = max(current + x, x)
    best = max(best, current)
print(best)

6

Najlepszy fragment to 4, -1, 2, 1. Gdy wszystkie liczby są ujemne, wynikiem jest największa z nich, bo fragment musi mieć co najmniej jeden wyraz.

Lista kroków, pseudokod i schemat blokowy

Podstawa programowa wymaga, żeby uczeń opisywał problem specyfikacją (dane i wynik) i zapisywał algorytm listą kroków albo pseudokodem, a w szkole rysuje się też schematy blokowe. Pseudokod jest w stylu arkuszy maturalnych: ← to przypisanie, div i mod to iloraz i reszta z dzielenia całkowitego, a elementy tablic i znaki napisów są numerowane od 1 (w Pythonie od 0). Te same zapisy są w kursie przy lekcjach tematu, pod przyciskiem Algorytm.

Najdłuższy spójny podciąg niemalejący

Specyfikacja. Dane: ciąg T[1..n], n ≥ 1. Wynik: długość najdłuższego fragmentu kolejnych wyrazów, w którym każdy wyraz jest nie mniejszy od poprzedniego.

Lista kroków:

1. Wczytaj n i ciąg T[1..n]. Ustaw długość bieżącego fragmentu d = 1 i najlepszą długość naj = 1.
2. Dla i = 2, 3, …, n wykonaj kroki 3-4.
3. Jeśli T[i] ≥ T[i - 1], fragment trwa dalej: zwiększ d o 1. W przeciwnym razie zaczyna się nowy fragment: d = 1.
4. Jeśli d > naj, zastąp naj liczbą d.
5. Wypisz naj.

Pseudokod:

wczytaj n, T
d ← 1
naj ← 1
dla i = 2, 3, ..., n wykonuj
  jeżeli T[i] ≥ T[i - 1] to
    d ← d + 1
  w przeciwnym razie
    d ← 1
  jeżeli d > naj to
    naj ← d
wypisz naj

Schemat blokowy:

Maksymalna suma spójnego podciągu

Specyfikacja. Dane: ciąg liczb całkowitych T[1..n], n ≥ 1. Wynik: największa suma fragmentu kolejnych wyrazów (co najmniej jednego).

Lista kroków:

1. Wczytaj n i ciąg T[1..n]. Ustaw s = T[1] (najlepsza suma fragmentu kończącego się na bieżącym wyrazie) i naj = T[1].
2. Dla i = 2, 3, …, n wykonaj kroki 3-4.
3. Zastąp s większą z liczb s + T[i] (przedłuż fragment) i T[i] (zacznij nowy fragment od T[i]).
4. Zastąp naj większą z liczb naj i s.
5. Wypisz naj.

Pseudokod:

wczytaj n, T
s ← T[1]
naj ← T[1]
dla i = 2, 3, ..., n wykonuj
  s ← max(s + T[i], T[i])
  naj ← max(naj, s)
wypisz naj

Schemat blokowy:

Najczęstsze błędy

• Wynik sprawdzany tylko przy przerwaniu fragmentu. Jeśli najlepszy fragment kończy się na ostatnim wyrazie, przerwania już nie będzie. Porównuj z najlepszym wynikiem w każdym obrocie pętli.
• Start od zera w algorytmie Kadane. best = 0 daje zły wynik dla samych liczb ujemnych. Zacznij od pierwszego wyrazu.
• Pomylone warunki. Niemalejący to >=, rosnący to >. Przeczytaj treść zadania dwa razy.
• Wyjście poza listę. Porównanie z poprzednim wyrazem zaczyna się od indeksu 1, nie 0.

Ćwicz w przeglądarce

W temacie o podciągach kursu Algorytmy: zakres rozszerzony:

• maksymalna suma spójnego podciągu,
• najdłuższa seria wzrostów temperatury,
• najlepszy okres zysków,
• najdłuższy fragment ze stałą różnicą.

Przycisk Algorytm przy tych lekcjach pokazuje listę kroków, pseudokod i schemat blokowy. Pełna lista: algorytmy.

Dla nauczycieli

Zadania o podciągach dobrze ćwiczy się na tabeli przebiegu: uczniowie wpisują wartości licznika i najlepszego wyniku po każdym wyrazie, a krokowanie pozwala to sprawdzić. W BitWizards przydzielasz kurs klasie i widzisz przebieg pisania kodu każdego ucznia. Platforma jest darmowa dla szkół - jak zacząć.