Zadanie 1. Potęgowanie modulo

Rozważmy operację potęgowania modularnego, stosowaną np. w algorytmie RSA. Liczbę $a$ podnosimy do potęgi $x$, po czym bierzemy resztę z dzielenia otrzymanej liczby przez ustaloną liczbę $M$, dzięki czemu otrzymujemy wynik

gdzie $a$, $M$ – dodatnie liczby całkowite, $x$ – nieujemna liczba całkowita.

Mówimy wtedy, że $a^{x} \ \textrm{mod} \ M$ równa się $b$.

Zapisz w wybranej przez siebie notacji (w postaci pseudokodupseudokodpseudokodu, listy krokówlista krokówlisty kroków 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.

Specyfikacja problemu:

Dane:

• a – liczba całkowita dodatnia

• x – nieujemna liczba całkowita

• M – liczba całkowita dodatnia

Wynik:

• b – nieujemna liczba całkowita o wartości równej $a^x\ \text{mod}\ M$

Rozwiązanie

Pseudokod

Zauważmy, że ograniczenie liczby operacji ($O(\log{x})$) wyklucza podnoszenie do potęgi poprzez mnożenie podstawy tyle razy, ile wynosi wykładnik ($O(x)$). W związku z tym skorzystamy z algorytmu szybkiego potęgowania liczbPeGPO00R1algorytmu szybkiego potęgowania liczb.

Zapisujemy początkowe warunki funkcji:

funkcja potęga(a,x,M)
	wynik ← 1
	mnoznik ← a

W każdym przebiegu pętli będziemy podnosić mnożnik do kwadratu i wykonywać na nim działanie $\textrm{mod} \ b$ (zgodnie z przechodzeniem na wyższe bity z postaci binarnej) oraz pomniejszać wartość $x$ za pomocą dzielenia całkowitoliczbowego przez $2$. Jeśli bit na danej pozycji jest niezerowy, przemnażamy wynik przez mnożnik i wykonujemy operację $\textrm{mod} \ b$:

funkcja potęga(a,x,M)
	wynik ← 1
	mnoznik ← a
	dopóki x > 0 wykonuj:
		jeżeli x mod 2 = 1 wykonaj:
			wynik ← wynik * mnoznik mod M
		mnoznik ← mnoznik * mnoznik mod M
		x ← x div 2

Po zakończeniu pętli (czyli wymnożeniu dla wszystkich bitów z postaci binarnej
liczby $x$) zwracamy wynik:

funkcja potęga(a,x,M)
	wynik ← 1
	mnoznik ← a
	dopóki x > 0 wykonuj:
		jeżeli x mod 2 = 1 wykonaj:
			wynik ← wynik * mnoznik mod M
		mnoznik ← mnoznik * mnoznik mod M
		x ← x div 2
	zwróc wynik

Oto rozwiązania w innych notacjach:

Lista kroków

1. Zainicjuj wynik jako 1.

2. Zainicjuj mnożnik jako a.

3. Dopóki x > 0, wykonuj kroki 4 - 7.

4. Jeżeli x mod 2 = 1, wykonaj krok 5.

5. Wynik pomnóż przez mnoznik mod M.

6. Mnożnik pomnóż przez mnoznik mod M.

7. Podziel całkowicie wynik przez 2.

8. Zwróć wynik.

C++

int potega(int a, int x, int M) {
    int wynik = 1;
    int mnoznik = a;
    while (x > 0) {
        if (x % 2 == 1) {
            wynik = wynik * mnoznik % M;
        }
        mnoznik = mnoznik * mnoznik % M;
        x = x / 2;
    }
    return wynik;
}

Java

int potega(int a, int x, int M) {
    int wynik = 1;
    int mnoznik = a;
    while (x > 0) {
	       if (x % 2 == 1) {
           wynik = wynik * mnoznik % M;
	}
        mnoznik = mnoznik * mnoznik % M;
        x = x / 2;
    }
    return wynik;
}

Python

def potega(a, x, M):
    wynik = 1
    mnoznik = a
    while x > 0:
        if x % 2 == 1:
            wynik = wynik * mnoznik % M
        mnoznik = mnoznik * mnoznik % M
        x = x // 2
    return wynik

Schemat oceniania

• 4 pkt – za poprawny algorytm, w tym:

  • 3 pkt – za poprawne obliczenie potęgi $a^x$ (w tym 1 pkt za warunki początkowe oraz 2 pkt 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,

• 0 pkt – za odpowiedź niepoprawną lub niepełną albo za brak odpowiedzi.

Zadanie 2

W tym zadaniu zajmujemy się algorytmami działającymi na n‑elementowej tablicy liczb całkowitych A[1..n], gdzie n jest dodatnią liczbą całkowitą.

Poniżej zapisano rekurencyjną procedurę W, której parametrem jest liczba całkowita j z przedziału [1, n]:

procedura W(j):
	jeśli j > 1 to
		jeśli A[j-1] > A[j] to
			v ← A[j]
			A[j] ← A[j-1]
			A[j-1] ← v
			W(j-1)

Oto przykładowa, 10‑elementowa tablica A[1..10] o zawartości [2,4,6,8,10,9,7,5,3,1].

W wybranej przez siebie notacji zapisz nierekurencyjną wersję procedury W.

Rozwiązanie

Przedstawmy algorytm za pomocą dopuszczonych na egzaminie maturalnym notacji, czyli pseudokodu, listy kroków, a także języków programowania: C++, Java i Python.

Zauważmy, że procedura W ma pewne cechy wspólne z algorytmem sortowania bąbelkowegoPCfvfjgLksortowania bąbelkowego pojedynczego elementu. Jest on zamieniany miejscami z elementem o wcześniejszym indeksie dopóty, dopóki trafi na element mniejszy od siebie. Warunki początkowe procedury pozostają bez zmiany.

Weźmy pod uwagę przykładową tablicę podaną w treści zadania: A[1..10] o zawartości [2,4,6,8,10,9,7,5,3,1].

Jeżeli wywołamy dla niej procedurę W z parametrem 7, otrzymamy:

2 4 6 7 8 10 9 5 3 1

Widzimy, że element będący na siódmym miejscu w tablicy, czyli 7, był zamieniany z poprzednim elementem, aż trafił na wartość mniejszą od siebie, czyli 6.

Następnie wywołajmy procedurę z parametrem 9. Otrzymujemy następujący wynik:

2 3 4 6 7 8 10 9 5 1

Na dziewiątym miejscu znajdował się element 3. Widzimy, że był on zamieniany z poprzednim elementem, aż trafił na mniejszy od siebie, czyli 2.

Zapiszmy nierekurencyjną wersję procedury W. Tworzymy zmienną pomocniczą i. Dopóki indeks i jest większy od $1$, a elementy na poprzedzających indeksach większe od wartości v, dopóty przesuwamy je w prawo.

Następnie wstawiamy element v w miejsce o tym indeksie, na którym skończyliśmy pętlę.

procedura W(j)
	jeżeli j > 1:
    	v ← A[j]
        i ← j
        dopóki i > 1 oraz A[i - 1] > v wykonuj:
        	A[i] ← A[i - 1]
            i ← i - 1
        A[i] ← v

Rozwiązania zapisane za pomocą innych dopuszczonych na egzaminie maturalnym notacji wyglądają następująco:

Lista kroków

1. Jeżeli j > 1, wykonaj kroki 2‑6.

2. Zainicjuj v jako A[j].

3. Zainicjuj i jako j.

4. Dopóki i > 1 oraz A[i - 1] > v, wykonuj kroki 4 i 5.

5. Do A[i] przypisz A[i - 1].

6. Do i przypisz i - 1.

7. Do A[i] przypisz v.

C++

void W(int j) {
    if (j > 1) {
        int v = A[j];
        int i = j;
        while ((i > 1) && A[i - 1] > v) {
            A[i] = A[i - 1];
            i -= 1;
        }
        A[i] = v;
    }
}

Java

void W(int j) {
    if (j > 1) {
        int v = A[j];
        int i = j;
        while ((i > 1) && A[i - 1] > v) {
            A[i] = A[i - 1];
            i -= 1;
        }
        A[i] = v;
    }
}

Python

def W(j):
    if j > 1:
        v = A[j]
        i = j
        while i > 1 and A[i - 1] > v:
            A[i] = A[i - 1]
            i -= 1
        A[i] = v

Schemat oceniania

• 3 pkt – poprawny algorytm w tym:

  • 1 pkt – za poprawne inicjowanie zmiennych,

  • 1 pkt – za poprawną konstrukcję pętli,

  • 1 pkt – za poprawne instrukcje w pętli,

• 0 pkt – za niepoprawną odpowiedź albo brak odpowiedzi.

Słownik