Darmowe konto pozwoli wrócić do niego później.
Polecenie
Zapisz w wybranej przez siebie notacji (w postaci pseudokodu lub w wybranym języku programowania) algorytm, który gdy są dane liczby a, x i M, obliczy b = a^x mod M. Aby otrzymać maksymalną liczbę punktów, Twój algorytm powinien wykonywać O(log x) operacji arytmetycznych wymienionych w poniższej uwadze.
Uwaga: W zapisie algorytmu możesz wykorzystać tylko operacje arytmetyczne: dodawanie, odejmowanie, mnożenie, dzielenie, dzielenie całkowite, resztę z dzielenia, oraz porównywanie liczb; instrukcje sterujące i przypisania do zmiennych lub samodzielnie napisane funkcje zawierające wyżej wymienione operacje.
Specyfikacja:
Dane:
Darmowe konto pozwoli wrócić do niego później.
x − nieujemna liczba całkowita
M − liczba całkowita dodatnia
Wynik:
b − nieujemna liczba całkowita o wartości równej a^x mod M
Rozwiązanie 1 (rekursja):
funkcja potęga(a, x, M)
jeżeli x = 0
wynik 1
jeśli x mod 2 == 0:
w = potęga(a, x/2)
wynik w*w mod M
jeśli x mod 2 == 1:
w = potęga(a, (x-1)/2)
zwróć wynik a*w*w mod M
Rozwiązanie 2 (C++, iteracja):
int potega(int a, int x, int M) {
int w = 1;
int z = a;
while(x>0) {
if (x%2==1)
w = w*z%M;
z = z*z%M;
x = x/2;
}
return w;
}
za poprawny algorytm, w tym: 3 pkt – za poprawne obliczenie potęgi a^x (w tym 1 punkt za warunki początkowe oraz 2 punkty za poprawną konstrukcję pętli z uwzględnieniem parzystości x), 1 pkt – za zwrócenie poprawnego wyniku. 2 pkt – za poprawny algorytm o złożoności większej niż logarytmiczna.
Algorytm winien wykorzystywać metodę binarną (szybkie potęgowanie) do osiągnięcia złożoności O(log x). Proste mnożenie iteracyjne daje tylko 2 punkty.
Ocena według schematu punktowania CKE, zwykle w 15–30 s
Dowiedz się, ile punktów naprawdę zdobywasz. Zrób zdjęcie kartki albo wklej odpowiedź: Maturownik+ porówna ją ze schematem punktowania, policzy punkty i wytłumaczy, gdzie i dlaczego je tracisz.