1.3. Rekurencyjne wypisywanie numerów książek

ORYGINALNE POLECENIE CKE

Wprowadzenie

Adam przechowuje swoje książki w biblioteczce zbudowanej z półek ponumerowanych kolejno 0, 1, 2, … (zaczynając od półki położonej najwyżej). Półka o numerze i ma 2i przegródek, w których umieszczane są książki. W jednej przegródce można umieścić tylko jedną książkę. Przegródki na i-tej półce są ponumerowane od lewej do prawej kolejnymi liczbami 1, 2, 3, …, 2i. Jako B[i, j] oznaczamy j-tą przegródkę na i-tej półce.

Przykład 1. Szara komórka to przegródka B[3, 4]

Biblioteczka: pięć półek; szara przegródka B[3,4].

Każda książka ma swój numer identyfikacyjny. Adam ustawia książki na półkach, zawsze zaczynając od przegródki B[0,1]. Stosuje przy tym następującą, rekurencyjną regułę: Adam sprawdza, czy przegródka B[i, j] (i ≥ 0 oraz 1 ≤ j ≤ 2i) jest pusta. Jeśli tak, umieszcza książkę w tej przegródce. W przeciwnym przypadku porównuje numer wstawianej książki z numerem książki w przegródce. Jeśli numer wstawianej książki jest mniejszy od numeru książki stojącej w przegródce, próbuje umieścić książkę na kolejnej półce w przegródce B[i + 1, 2j – 1]. Jeśli numer wstawianej książki jest większy od numeru książki w przegródce, to próbuje umieścić książkę w przegródce B[i + 1, 2j].

Przykład 2. Poniżej przedstawiono zawartość biblioteczki po wstawieniu do niej książek kolejno o numerach: 10, 2, 15, 13, 1, 5, 25 (zakładamy, że przedtem biblioteczka była pusta).

Biblioteczka po wstawieniu książek 10, 2, 15, 13, 1, 5, 25: półka 0: 10; półka 1: 2, 15; półka 2: 1, 5, 13, 25.

Przykład 3. Poniżej przedstawiono zawartość biblioteczki po wstawieniu do niej książek kolejno o numerach: 1, 5, 10, 15, 2, 25, 13 (zakładamy, że przedtem biblioteczka była pusta).

Biblioteczka po wstawieniu książek 1, 5, 10, 15, 2, 25, 13: B[0,1]=1; B[1,2]=5; B[2,3]=2; B[2,4]=10; B[3,8]=15; B[4,15]=13; B[4,16]=25.

Polecenie

Kolega Adama, oglądający biblioteczkę, stwierdził, że aby wypisać wszystkie numery książek umieszczonych na półkach, można posłużyć się podanym poniżej rekurencyjnym algorytmem A, którego działanie rozpoczynamy od półki o numerze 0 i od przegródki o numerze 1. Zakładamy przy tym, że w biblioteczce jest co najmniej jedna książka.

A(i, j)
    wypisz numer książki z przegródki B[i, j]
    jeżeli przegródka B[i + 1, 2j – 1] nie jest pusta, to
        wykonaj A(i + 1, 2j – 1)
    jeżeli przegródka B[i + 1, 2j] nie jest pusta, to
        wykonaj A(i + 1, 2j)

Dla biblioteczki z siedmioma książkami z przykładu 2. algorytm A wypisze: 10, 2, 1, 5, 15, 13, 25.

Podaj ciągi liczb wypisane przez algorytm A dla podanych zawartości biblioteczki.

a)

Przypadek a: B[0,1]=9; B[1,1]=2; B[1,2]=12; B[2,3]=10; B[2,4]=14; B[3,7]=13; B[3,8]=15.

Odpowiedź: …, …, …, …, …, …, …

b)

Przypadek b: B[0,1]=10; B[1,1]=8; B[1,2]=15; B[2,1]=4; B[2,3]=12; B[3,2]=6; B[3,6]=13.

Odpowiedź: …, …, …, …, …, …, …

Pokaż odpowiedź i ocenianie CKE

Odpowiedź CKE

a) 9, 2, 12, 10, 14, 13, 15

b) 10, 8, 4, 6, 15, 12, 13

Zasady oceniania CKE

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

W zadaniach praktycznych wszystkie wyniki muszą być odzwierciedleniem komputerowej realizacji obliczeń.

2 pkt – odpowiedź poprawna.

1 pkt – odpowiedź poprawna dla jednego podpunktu.

0 pkt – odpowiedź niepoprawna albo brak odpowiedzi.

Źródło

Oryginalne zasady oceniania CKE — PDF, strona 4

Potrzebujesz pomocy w przygotowaniu do matury?

Zobacz korepetycje

TWÓJ NASTĘPNY KROK

Przygotuj się do matury z informatyki ze mną.

Igor Józefowicz — korepetycje z informatyki do matury

Na indywidualnych zajęciach online uporządkujemy trudne zagadnienia i przećwiczymy zadania maturalne. Wspólnie ustalimy plan przygotowań dopasowany do Twojego poziomu i celu.

TWÓJ PIERWSZY KROK

30 minut · online · bezpłatnie

Umów bezpłatną rozmowę