Algorytm Czemu 4

[eloelo]

Moje pytanie skąd ta 4 czyli jak to działa

Specyfikacja:
Dane: Liczba całkowita k ≥ 0.
Wynik: Reszta z dzielenia 2^k przez 10.
Algorytm
krok 1: jeżeli k = 0, to wynikiem jest 1
krok 2: w przeciwnym przypadku
krok 2.1: policz resztę z dzielenia k przez 4
krok 2.2: jeżeli reszta = 0, to wynikiem jest 6
krok 2.3: jeżeli reszta = 1, to wynikiem jest 2
krok 2.4: jeżeli reszta = 2, to wynikiem jest 4
krok 2.5: jeżeli reszta = 3, to wynikiem jest 8

Dzięki za jakieś info

[Baca48]

Zauważ, że wypisując kolejne potęgi liczby dwa, otrzymujesz ciąg liczb:

2,4,8,16,
32,64,128,256,
512,1024,2048 ...

Reszta z dzielenia pewnej liczby przez 10 to po prostu jej ostatnia cyfra. Jak widzimy powyżej, powtarza się sekwencja liczb (2,4,8,6) - jest ich cztery i stąd ta czwórka w algorytmie. Operacja "k modulo 4" służy do wychwycenia, która to liczba z kolei. Na początku algorytmu potrzeba jeszcze sprawdzić czy k=0, gdyż dla tej wartości k, wynikiem jest 1.

Pozdrawiam

[eloelo]

dzięki po mału do przodu
ale mam jeszcze jedno pytanie tzn jak wychwycić resztę z dzielenia przez 4 czy jakąkolwiek inną liczbę tak żeby to zrozumieć

[kadiii]

Zwyczajnie dzielisz k przez 4 - uzyskujesz jakąś liczbę. Bierzesz jej część całkowitą, czyli fizycznie odcinasz część po przecinku(jeśli oczywiście sie pojawiła). następnie mnożysz tak utworzoną liczbe przez 4 i odejmujesz od poczatkowej liczby. Otrzymany wynik to reszta z dzielenia k przez 4. Mówiąc inaczej, reszta z dzielenia określa nam tę liczbe , która nie zmieściła sie juz pełna jako wielokrotność w k.
Przykład:
\(\displaystyle{ k=213}\)
\(\displaystyle{ 213/4=53,25}\) odcinamy część ułamkową - mamy\(\displaystyle{ 53}\)
\(\displaystyle{ 53*4=212}\)
\(\displaystyle{ 213-212=1}\) - \(\displaystyle{ 213/4=53}\)reszty \(\displaystyle{ 1}\).
czyli uwzględniając całe zdanie: \(\displaystyle{ 2^{213}}\) ma ostatnią cyfrę, równą \(\displaystyle{ 2}\).