Zadania maturalne

Zadanie 1.

Rozważmy następujący algorytm:

Specyfikacja problemu:

Dane:

• n – liczba całkowita dodatnia

Wynik:

• p – liczba całkowita dodatnia

p <- 1
q <- n
dopóki p < q wykonuj
	s <- (p + q) div 2
    jeżeli s * s * s < n wykonuj
    	p <- s + 1
    w przeciwnym wypadku
    	q <- s

Zadanie 1.1. (0$‐$3 pkt)

Treść polecenia

Podaj wynik działania algorytmu dla wskazanych w tabeli wartości n.

Rozwiązanie

W tym zadaniu należy przeanalizować algorytm zapisany za pomocą pseudokodu, a następnie podać wyniki w zależności od danych. Prześledźmy algorytm krok po kroku dla każdej z podanych wartości n.

Przygotowujemy tabelę, w której będziemy zapisywać kolejne wartości zmiennych p, q, s.

p = 1
q = 80

1 < 80	PRAWDA
	s =  (1+80) div 2 = 40
    40*40*40 < 80	FAŁSZ
    	q = 40

1 < 40	PRAWDA
	s = (1+40) div 2 = 20
    20*20*20 < 80	FAŁSZ
    	q = 20

1 < 20	PRAWDA
	s = (1+20) div 2 = 10
    10*10*10 < 80	FAŁSZ
    	q = 10

1 < 10	PRAWDA
	s = (1+10) div 2 = 5
    5*5*5 < 80		FAŁSZ
    	q = 5

1 < 5 	PRAWDA
	s = (1+5) div 2 = 3
    3*3*3 < 80		PRAWDA
    	p = 4

4 < 5	PRAWDA
	s = (4+5) div 2 = 4
    4*4*4 < 80		PRAWDA
    	p = 5

5 < 5	FAŁSZ
   

Schemat oceniania

Rozwiązywanie problemów i podejmowanie decyzji […], stosowanie podejścia algorytmicznego. Zdający:
11) opisuje podstawowe algorytmy i stosuje:
a) algorytmy na liczbach całkowitych;
16) opisuje własności algorytmów na podstawie ich analizy;
17) ocenia zgodność algorytmu ze specyfikacją problemu;
18) oblicza liczbę operacji wykonywanych przez algorytm.

Poprawna odpowiedź

3 pkt – za prawidłową odpowiedź w trzech wierszach.

2 pkt – za prawidłową odpowiedź w dwóch wierszach.

1 pkt – za prawidłową odpowiedź w jednym wierszu.

0 pkt – za podanie odpowiedzi błędnej albo brak odpowiedzi.

Zadanie 1.2. (0$‐$2 pkt)

Podaj najmniejszą oraz największą liczbę n, dla której wynikiem działania algorytmu będzie p = 10.

Rozwiązanie

W tym zadaniu należy dokładnie przeanalizować wyniki, jakie zwraca program w poprzednim podpunkcie. Zwróć uwagę, że zawsze sprawdzamy, czy dana wartość n jest większa od sIndeks górny 33.

Spójrzmy teraz na wyniki programu dla kolejnych wartości n.

Jeżeli wartość zmiennej s podniesionej do trzeciej potęgi była mniejsza od n,to zmiennej p przypisywaliśmy wartość inkrementowanejinkrementacjainkrementowanej zmiennej s.

Sprawdźmy teraz, ile wynoszą sześciany dla wartości p, które były odpowiedzią w poprzednim zadaniu i porównajmy je z wartościami sześcianu dla s mniejszego o 1 od p.

Jak możemy zaobserwować, między zmiennymi zachodzi następująca zależność:

Wynika stąd, że aby otrzymać wynik p = 10, wartość zmiennej n musiałaby należeć do przedziału:

Pamiętajmy też, że:

W konsekwencji, ponieważ n jest liczbą naturalną, to najmniejsza liczba wynosi 730, a największa 1000.

Schemat oceniania

Rozwiązywanie problemów i podejmowanie decyzji […], stosowanie podejścia algorytmicznego. Zdający:
11) opisuje podstawowe algorytmy i stosuje:
a) algorytmy na liczbach całkowitych;
16) opisuje własności algorytmów na podstawie ich analizy;
17) ocenia zgodność algorytmu ze specyfikacją problemu;
18) oblicza liczbę operacji wykonywanych przez algorytm.

Poprawna odpowiedź

730, 1000.

2 pkt – za prawidłową odpowiedź w dwóch wierszach.

1 pkt – za prawidłową odpowiedź w jednym wierszu.

0 pkt – za podanie odpowiedzi błędnej albo brak odpowiedzi.

Słownik