2.2. Liczba rysowanych strzałek

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:

Polecenie