Zadanie: Matura CKE Maj 2011 (Informatyka Rozszerzona)

Question

Zadanie 2. Potęgowanie (5 pkt)
Dana jest następująca specyfikacja oraz algorytm obliczania potęgi o wykładniku naturalnym:

Specyfikacja:
Dane: liczba rzeczywista $a$ oraz liczba naturalna $n$, $n 
eq 0$
Wynik: liczba rzeczywista $p = a^n = \underbrace{a \cdot a \cdot ... \cdot a}_{n 	ext{ razy}}$

Algorytm:
krok 1. $p := 1$, $b := a$
krok 2. dopóki $n > 0$ wykonuj:
$\quad$ a) jeśli $n \bmod 2 
eq 0$, to $p := p * b$
$\quad$ b) $b := b * b$
$\quad$ c) $n := n \operatorname{div} 2$

Uwaga: $n \operatorname{div} 2$ oznacza wynik dzielenia całkowitego $n$ przez $2$, a $n \bmod 2$ oznacza resztę z dzielenia całkowitego $n$ przez $2$. Pytanie 1: a) Przeanalizuj podany algorytm i uzupełnij tabelę wartościami zmiennych $p$, $b$ oraz $n$ po kolejnych wykonaniach kroku 2 dla dowolnej początkowej wartości $a$ oraz dla początkowej wartości zmiennej $n$ równej 12.

$p$$b$$n$
1$a$12
1$a^2$[odp_tab1]
[odp_tab2][odp_tab3][odp_tab4]
[odp_tab5][odp_tab6][odp_tab7]
[odp_tab8][odp_tab9][odp_tab10] Pytanie 2: b) Uzupełnij poniższą tabelę, wpisując liczby wszystkich mnożeń, wykonywanych przez powyższy algorytm dla podanych wartości $n$, tzn. liczby wykonanych instrukcji $p := p * b$ i $b := b * b$.

$n$liczba mnożeń
2[odp_tab1]
3[odp_tab2]
4[odp_tab3]
5[odp_tab4]
6[odp_tab5]
7[odp_tab6] Pytanie 3: c) Podkreśl funkcję, której wartość jest równa liczbie mnożeń wykonywanych przez powyższy algorytm dla wartości $n$ będącej potęgą dwójki:
[ABCD1]

Instytut Maturalny · Accepted Answer

Sprawdź pełne rozwiązanie na stronie Instytutu Maturalnego.

$p$	$b$	$n$
1	$a$	12
1	$a^2$	........
........	........	........
........	........	........
........	........	........

$n$	liczba mnożeń
2	........
3	........
4	........
5	........
6	........
7	........

Zobacz również podobne zadania

Chcesz zobaczyć więcej rozwiązań z przedmiotu Informatyka Rozszerzona?