Arkusz egzaminacyjny https://cke.gov.pl/images/_EGZAMIN_MATURALNY_OD_2023/materialy_dodatkowe/pokazowe/Informatyka/MINP-R0-100-2203.pdf
Załącznik Dane_2203.zip;
Zasady oceniania rozwiązań zadań
Przykładowe rozwiązanie Zadania 3.2.
Wersja iteracyjna
https://plotkarka.eu/jscpp/Zadanie3.Potegowaniemodulo1.htmlWersja rekurencyjna
https://plotkarka.eu/jscpp/Zadanie3.Potegowaniemodulo2.html
Przykładowe rozwiązania
Wersja rekurencyjna (pseudokod po licznych poprawkach)
funkcja potega(a, x, M)
jeżeli x = 0
zwróć 1
jeśli x mod 2 = 0
w ← potega(a, x div 2, M)
zwróć w * w mod M
jeśli x mod 2 = 1
w ← potega(a, (x - 1) div 2, M)
zwróć a * w * w mod M
wypisz potega(2, 5, 7)
Wersja iteracyjna
funkcja potega(a, x, M)
w ← 1
z ← a
dopóki x > 0 wykonuj
jeżeli x mod 2 = 1
w ← (w * z) mod M
z ← (z * z) mod M
x ← x div 2
zwróć w
w C++
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;
}
w Python
def potega(a, x, M):
w = 1
z = a
while x > 0:
if x % 2 == 1:
w = (w * z) % M
z = (z * z) % M
x = x // 2
return w