Strefa wyzwań

Już wiesz

Jak działa algorytm iteracyjnego potęgowania liczb (algorytm naiwny i algorytm szybkiego potęgowania).
Jak zaimplementować algorytm szybkiego potęgowania liczb.
Czym charakteryzują się dwie techniki programowania - rekurencyjną i iteracyjną.

Teraz czas sprawdzić swoją wiedzę i umiejętności w praktyce.

Ćwiczenie 1

R1VLB5OHRD1ES

Ćwiczenie 2

RMJC99TLMAJ5J

Ćwiczenie 3

R14TUPGXUQK1C

Ćwiczenie 4

R9BK96KBJTCCR

Ćwiczenie 5

RRVN7S7Q3RND8

Uzupełnij wartości w działaniach kolejnych iteracji pętli w algorytmie szybkiego potęgowania trzy indeks górny, tysiąc jeden, koniec indeksu górnego. Wykładnik zapisany został w systemie dwójkowym. Wynik będzie przechowywany w zmiennej potega. Zmienna ta została już zainicjowana wartością jeden.

potega ← Tu uzupełnij razy, jeden, razy Tu uzupełnij
potega ← Tu uzupełnij razy Tu uzupełnij
potega ← Tu uzupełnij razy Tu uzupełnij
potega ← Tu uzupełnij razy Tu uzupełnij razy, trzy

potega ← Tu uzupełnij razy, jeden, razy Tu uzupełnij
potega ← Tu uzupełnij razy Tu uzupełnij
potega ← Tu uzupełnij razy Tu uzupełnij
potega ← Tu uzupełnij razy Tu uzupełnij razy, trzy

Ćwiczenie 6

Napisz pseudokod algorytmu wyświetlającego liczbę wszystkich możliwych kodów, które możemy ustawić, aby zabezpieczyć pewną kłódkę. Kod ten składa się z $n$ cyfr z zakresu $\langle 0,\ 9\rangle$ i z $m$ liter ze zbioru $\left\{ A,\ B,\ C,\ D\right\}$ .

Litery i cyfry w szyfrze mogą się powtarzać.

Przykład:

Jeżeli kod składa się z dwóch cyfr całkowitych z przedziału $\langle 0,\ 7\rangle$ i trzech liter ze zbioru $\left\{ A,\ B,\ C,\ D\right\}$ , to liczba możliwych kodów to $8 \cdot 8 \cdot 4 \cdot 4 \cdot 4$ . Ósemki w kodzie oznaczają liczbę kombinacji cyfr (od $0$ do $7$ mamy siedem cyfr). Są dwie, ponieważ kod składa się z dwóch cyfr. Analogicznie jest w przypadku liter – do wyboru mamy cztery litery ( $A$ , $B$ , $C$ lub $D$ ), każda z nich może pojawić się w jednym z czterech miejsc kodu.

Wykorzystaj algorytm potęgowania liczb według definicji.

Specyfikacja problemu:

Dane:

n – liczba naturalna; liczba cyfr zawartych w kodzie
m – liczba naturalna; liczba liter zawartych w kodzie

Wynik:

Algorytm wypisuje liczbę możliwych kodów zabezpieczających kłódkę.

R1L2LT898MVBU

Ćwiczenie 7

Okres połowicznego rozpadu jest to czas, po którym liczebność danej próbki maleje dwukrotnie. Na przykład po trzech okresach pozostanie $\frac{1}{8}$ początkowej ilości próbki. Ilość próbki $N_t$ pozostałej po danej liczbie okresów $t$ rozpadu początkowej próbki $N_0$ możemy wyrazić wzorem:

N_{t} = N_{0} \cdot \frac{1}{2^{t}}

Zapisz w postaci pseudokodu algorytm wyliczania ilości pozostałej próbki Nt po liczbie okresów t zapisanych w systemie dwójkowym. Wykorzystaj algorytm szybkiego potęgowania liczb w wersji iteracyjnej.

Specyfikacja problemu:

Dane:

– liczba okresów, liczba naturalna zapisana w systemie binarnym $t_{1} t_{2} t_{3} \dots t_{x}$ ; wykładnik potęgi
N0 – początkowa ilość próbki, liczba naturalna

Wynik:

Algorytm wypisuje ilość pozostałej próbki po liczbie okresów t:

R1KONLNZZAU2U

Ćwiczenie 8

Ile mnożeń wykonuje algorytm?

Napisz dwie funkcje w języku Python, które obliczają wartość $a^{n}$ :

Metodą naiwną – przez kolejne mnożenia (na podstawie definicji)
Metodą szybkiego potęgowania

Każda funkcja powinna:

zwracać wynik potęgowania,
zwracać liczbę wykonanych mnożeń. Możesz wykorzystać poniższy szablon

Linia 1. kratka znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości. Linia 2. kratka WERSJA NAIWNA. Linia 3. kratka znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości. Linia 5. def potega podkreślnik naiwna otwórz nawias okrągły a przecinek n zamknij nawias okrągły dwukropek. Linia 6. wynik znak równości 1. Linia 7. mnozenia znak równości 0. Linia 9. for podkreślnik in range otwórz nawias okrągły n zamknij nawias okrągły dwukropek. Linia 11. pass. Linia 13. return wynik przecinek mnozenia. Linia 16. kratka znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości. Linia 17. kratka SZYBKIE POTĘGOWANIE. Linia 18. kratka znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości znak równości. Linia 20. def szybkie podkreślnik potegowanie otwórz nawias okrągły a przecinek n zamknij nawias okrągły dwukropek. Linia 21. wynik znak równości 1. Linia 22. mnozenia znak równości 0. Linia 24. while n zamknij nawias ostrokątny 0 dwukropek. Linia 25. if n procent 2 znak równości znak równości 1 dwukropek. Linia 27. pass. Linia 29. return wynik przecinek mnozenia.

# =========================
# WERSJA NAIWNA
# =========================

def potega_naiwna(a, n):
    wynik = 1
    mnozenia = 0

    for _ in range(n):
        
        pass

    return wynik, mnozenia


# =========================
# SZYBKIE POTĘGOWANIE
# =========================

def szybkie_potegowanie(a, n):
    wynik = 1
    mnozenia = 0

    while n > 0:
        if n % 2 == 1:
           
        pass

    return wynik, mnozenia

Przykładowe rozwiązanie

def potega_naiwna(a, n):
    wynik = 1
    mnozenia = 0

    for _ in range(n):
        wynik *= a
        mnozenia += 1

    return wynik, mnozenia


def szybkie_potegowanie(a, n):
    wynik = 1
    mnozenia = 0

    while n > 0:
        if n % 2 == 1:
            wynik *= a
            mnozenia += 1

        a *= a
        mnozenia += 1
        n //= 2

    return wynik, mnozenia
print(potega_naiwna(2,10))
print(szybkie_potegowanie(2,10))

Plik z programem do pobrania:

R12GUCPPPMTKF

Plik zawiera rozwiązanie ćwiczenia w języku Python.

Plik TXT o rozmiarze 472.00 B w języku polskim

Potęgowanie oraz schemat Hornera – gra edukacyjna