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
Algorytm Czemu 4
-
- Użytkownik
- Posty: 195
- Rejestracja: 1 sty 2008, o 13:37
- Płeć: Mężczyzna
- Lokalizacja: Wielkopolska
- Podziękował: 4 razy
- Pomógł: 56 razy
Algorytm Czemu 4
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
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
Algorytm Czemu 4
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ć
ale mam jeszcze jedno pytanie tzn jak wychwycić resztę z dzielenia przez 4 czy jakąkolwiek inną liczbę tak żeby to zrozumieć
- kadiii
- Użytkownik
- Posty: 642
- Rejestracja: 20 gru 2005, o 21:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Pomógł: 130 razy
Algorytm Czemu 4
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}\).
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}\).