Rozwiązanie
Zadanie 1.2 – matura 2018, maj

Zadanie 1.2 (0-2)

Analiza algorytmu
Analiza algorytmu
Rozważamy następujący algorytm:
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 wykonaj
    p ← s+1
  w przeciwnym wypadku
    q ← s

Uwaga: zapis div oznacza dzielenie całkowite. Podaj najmniejszą oraz największą liczbę n, dla której wynikiem działania algorytmu będzie p = 10
Jak można zauważyć rozwiązując poprzednie zadanie (1.1., patrz poprzednie zadanie), dla n równego zarówno 28 jak i 64: p, jak i q równa się 4.
Jeśli rozwiązałeś przykład z n=80, otrzymany wynik p powinien wynosić 5. Możemy więc wysnuć hipotezę, że wraz z rosnącym n, p będzie się zwiększać.
Dlaczego tak się dzieje? 🤔
Decydują o tym dwa czynniki:
a) p ostatecznie zawsze będzie równało się q. Wynika to zarówno z warunku pętli (p= n. Jest to klucz do rozwiązania zadania: udowodniliśmy już, że ostatecznie p=q, a więc teraz musimy ustalić, jakie n będzie potrzebne, aby uzyskać wynik q=10.
Rozwijając myśl z podpunktu a):
- s w najgorszym przypadku będzie równe (1+q) div 2, ponieważ początkowo p=1; np.: p=3, q=11: s=(3+11) div 2 = 7: wartość mniejsza niż q
- s w najlepszym przypadku będzie równa (q+q-1) div 2, co pokazaliśmy wyżej; np.: p=3, q=4: s=(3+4) div 2 = 3: wartość mniejsza niż q

Oznacza to, że q będzie malało, aż warunek s^3= n, a w innym wypadku to p będzie dążyło do q.

A więc, aby przewidzieć, jakie n potrzebujemy, żeby q było równe określonej liczbie (w przypadku tego zadania 10), musimy podnieść tą liczbę do potęgi 3 - voilà! otrzymaliśmy naszą górną granicę, aby uzyskać pożądaną liczbę: dla p=q=10 będzie to 1000! 😃
Dolną granicę możemy wyliczyć, bazując na górnej. Otóż - jeśli dla maksymalnie 1000 uzyskamy p równe 10, oznacza to, że 1001 da nam już inną liczbę - 11. A więc pierwsza liczba, dla której p wyjdzie równe 11, będzie miała zapis 10^3+1 - za dziesiątkę możemy wstawić jakąkolwiek liczbę, ważne jest to, że stanowi ona liczbę, którą chcemy uzyskać w p^3+1. (użycie p czy q jest zamienne, co udowodniliśmy w podpunkcie a.)

Podsumowując:
- dolna granica=(p-1)^3+1, dla 10: (10-1)^3+1=9^3+1=730
- górna granica=p^3, dla 10: 10^3=100

i oto nasz wynik! 😄
Wyszukaj więcej zadań z tego arkusza...