Cześć,
Załóżmy, że chcemy wyznaczyć \(\displaystyle{ 12345\pmod{100}}\).
Skorzystamy z następującego algorytmu:
\(\displaystyle{ \begin{array}{l}
reszta = 1\pmod{100} \\
reszta = (reszta*10 + 2)\pmod{100}\\
reszta = (reszta*10 + 3)\pmod{100} \\
reszta =(reszta*10 + 4)\pmod{100}\\
reszta= (reszta*10 + 5)\pmod{100}\\
reszta = 45\\
\end{array}}\)
Sama idea jest jasna: bierzemy pierwszą cyfrę i z niej resztę z dzielenia przez sto. W kolejnym kroku otrzymaną wcześniej resztę mnożymy przez dziesięć , dodajemy kolejną cyfrę i wyznaczamy resztę z dzielenia przez sto, itd.
W jaki sposób ten algorytm działa? Dlaczego na początku bierzemy pojedynczą cyfrę \(\displaystyle{ 1}\), mimo to, że jest to cyfra dziesiątek tysięcy i wyznaczamy jej resztę, a nie startujemy na przykład od \(\displaystyle{ 5 }\)?
Algorytm szukania modulo - wytłumaczenie zasady działania
-
- Użytkownik
- Posty: 77
- Rejestracja: 8 sie 2010, o 15:18
- Płeć: Mężczyzna
- Lokalizacja: Łódź
- Podziękował: 11 razy