aplikacja Matura google play app store

zadania z informatyki - Tworzenie algorytmów

Zadanie: 1 2 3 4 5 6 7 8 9 10
Zadanie 4.
Wiązka zadań Szybkie podnoszenie do potęgi

W algorytmach szybkiego potęgowania można wykorzystać binarną reprezentację wykładnika dla obliczenia wartości xk , gdzie k jest liczbą naturalną, k ≠ 0, zaś x jest liczbą rzeczywistą. Przyjmijmy, że binarnym rozwinięciem wykładnika k jest ciąg (݇knkn–1kn–2 ... k2k1k0)2.

Jedna z metod wyznaczania xk polega na obliczaniu potęg liczby x dla wykładników o binarnych reprezentacjach:
݇kn,
݇knkn–1,
knkn–1kn–2,
…,
knkn–1kn–2 …݇k1,
knkn–1kn–2 …݇k1k0,

Inaczej mówiąc, uwzględniamy coraz dłuższe fragmenty ciągu (݇knkn–1kn–2 ... k2k1k0)2. W pierwszym kroku przyjmujemy, że wynik jest równy x, gdyż kn = 1. Znając wartość x do potęgi o binarnym zapisie (݇knkn–1kn–2 ... ki)2, możemy łatwo wyliczyć x do potęgi o binarnym zapisie (݇knkn–1kn–2 ... kiki–1)2: podnosimy dotychczasowy wynik do kwadratu (do czego wystarczy jedno mnożenie). Jeśli ki–1 = 1, dodatkowo mnożymy uzyskany wynik przez x.

Przykład

Niech ݇ k = 13 = (1101)2. Kolejne wyznaczane w naszym algorytmie potęgi to:

x1, x3 = x2x, x6 = (x3)2, x13 = (x6)2x,

zaś liczba wykonanych mnożeń jest równa 5 (zauważ, że aby obliczyć x3, musisz najpierw obliczyć x2, a aby obliczyć x2, musisz wykonać jedno mnożenie: x2 = xx).
Zadanie 4.1.
Korzystając z przedstawienia wykładnika w postaci binarnej, podaj kolejne potęgi liczby x wyznaczane powyższą metodą przy obliczaniu x38.
Zadanie 4.2.
Uzupełnij tabelkę. Oblicz, ile mnożeń wykonywanych jest dla kolejnych wykładników.
k reprezentacja binarna k liczba mnożeń
4 100 2
5 101 3
6    
7    
8    
15    
16    
22    
32    
Zadanie 4.3.
W wybranej przez siebie notacji (lista kroków, pseudokod, język programowania) napisz algorytm, który dla zadanej binarnej reprezentacji liczby naturalnej k, k ≠ 0, oraz rzeczywistej liczby x oblicza wartość xk zgodnie z metodą opisaną na początku zadania.

Specyfikacja
Dane:
x — liczba rzeczywista,
n — liczba całkowita nieujemna,
݇knkn–1kn–2 ... k1k0 — ciąg tworzący binarną reprezentację wykładnika k,
Wynik:
liczba rzeczywista 
Poprzednia strona Następna strona

źródło: CKE
Polityka Prywatności