2.1. Rysunek wywołań rekurencyjnych

2022 · Grudzień — matura próbna · Matura próbnaFormuła 2023Łatwe2 pkt

Wprowadzenie

Dla danej, dodatniej liczby całkowitej N, na kartce papieru rysujemy N różnych punktów i numerujemy je liczbami 1, 2, …, N. W tym zadaniu będziemy łączyć punkty ze sobą strzałkami – funkcja strzałka(x,y) rysuje strzałkę od punktu o numerze x do punktu o numerze y.

Wywołanie poniżej zapisanej funkcji rekurencyjnej rysuj(x) poskutkuje narysowaniem pewnej liczby strzałek. Jej jedynym argumentem jest pewna liczba całkowita x z przedziału [1, N]. Przeanalizuj funkcję i znajdź odpowiedzi dla podanych zadań.

funkcja rysuj(x)
    jeżeli 2*x ≤ N
        strzałka(x, 2*x)
        rysuj(2*x)
    jeżeli 2*x + 1 ≤ N
        strzałka(x, 2*x + 1)
        rysuj(2*x + 1)

Przykład: Oto przykładowy rysunek otrzymany w wyniku wywołania rysuj(1) dla N = 5 i danego układu punktów:

Przykładowy układ pięciu punktów i strzałek funkcji rysuj(1).

Polecenie

Dla N = 10 narysuj 10 punktów i ponumeruj je liczbami 1, 2, 3, …, 10, a następnie połącz strzałkami tak, żeby otrzymać rysunek, który dostalibyśmy w wyniku wywołania funkcji rysuj(1). Dobierz punkty tak, aby Twój rysunek był czytelny.

Pokaż odpowiedź i ocenianie CKE

Odpowiedź CKE

Przykładowe poprawne rozwiązanie CKE: drzewo dziesięciu punktów ze strzałkami skierowanymi od rodzica do dzieci.

Zasady oceniania CKE

2 pkt – odpowiedź poprawna.

1 pkt – z co najwyżej 1 niepoprawną strzałką lub brakiem jednej strzałki.

0 pkt – odpowiedź niepoprawna albo brak rozwiązania.

Uwaga: Akceptowane są wszystkie odpowiedzi merytorycznie poprawne i spełniające warunki zadania.

Źródło

Oryginalne zasady oceniania CKE — PDF, strona 4

Potrzebujesz pomocy w przygotowaniu do matury?

Zobacz korepetycje