2. Gra w stawianie pionków

Matura pokazowa marzec 2022 - Matura z informatyki: arkusze krok po kroku (Python)

**Zadanie 2. Gra** (na kartce). Plansza ma pola 0, 1, ..., s, na początku pionek stoi tylko na polu 0. W k-tej turze procedura Tura(k) przechodzi pola od s w dół do A[k] i stawia pionek na polu i, jeśli pole i - A[k] jest zajęte, a pole i puste. Gra kończy się sukcesem, gdy na polu s stoi pionek. Pola przechodzone od końca sprawiają, że w jednej turze liczba A[k] dokłada się co najwyżej raz: pionek postawiony w tej turze na polu i nie zdąży już posłużyć do postawienia pionka na polu i + A[k]. Pionki stoją więc na polach, które są sumami różnych elementów tablicy (jak w problemie plecakowym). Program przepisuje rozgrywkę z arkusza na Pythona i sprawdza przykład z tabeli: A = [1, 2, 3], s = 5 daje TAK.

def game(A, s):
    board = [False] * (s + 1)  # board[i] = czy na polu i stoi pionek
    board[0] = True
    for a in A:  # Tura(k) dla a = A[k]
        for i in range(s, a - 1, -1):  # i = s, s - 1, ..., A[k]
            if board[i - a] and not board[i]:
                board[i] = True
    return board


board = game([1, 2, 3], 5)
print("pola z pionkami:", [i for i in range(len(board)) if board[i]])
print("sukces:", board[5])

Ł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.