3.4 Najdłuższy ciąg w pliku przykładowym

Matura maj 2023 - Matura z informatyki: arkusze krok po kroku (Python)

Zadanie 3.4 (2 pkt): najdłuższy ciąg rosnąco-malejący z kolejnych cyfr i pozycja jego początku. Sprawdzanie wszystkich fragmentów od każdej pozycji byłoby długie, ale ciąg rosnąco-malejący z cyfr ma najwyżej 20 wyrazów (cyfry rosną najwyżej od 0 do 9). Dla pliku przykładowego: pozycja 77, ciąg 0899862.

def rise_fall(seq):
    n = len(seq)
    if n < 4:
        return False
    up = 1  # długość rosnącego początku ciągu
    while up < n and seq[up - 1] < seq[up]:
        up = up + 1
    down = 1  # długość malejącego końca ciągu
    while down < n and seq[n - down - 1] > seq[n - down]:
        down = down + 1
    # część rosnąca ma k wyrazów, malejąca n - k: obie co najmniej 2, rosnąca mieści się
    # w rosnącym początku, a malejąca w malejącym końcu
    return max(2, n - down) <= min(up, n - 2)


with open("pi_przyklad.txt") as f:
    digits = [int(line) for line in f]  # jedna cyfra w każdym wierszu

# 3.4 cyfry rosną najwyżej 10 razy z rzędu (0-9) i tyle samo maleją, więc ciąg
# rosnąco-malejący ma najwyżej 20 cyfr: wystarczą fragmenty długości od 4 do 20
best_start, best_length = 0, 0
for i in range(len(digits)):
    for length in range(4, 21):
        if i + length <= len(digits) and length > best_length and rise_fall(digits[i:i + length]):
            best_start, best_length = i, length
longest = "".join(str(d) for d in digits[best_start:best_start + best_length])

print("3.4")
print(best_start + 1)
print(longest)

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Matura z informatyki: arkusze krok po kroku·Zaloguj się, aby zapisać postęp na koncie.