Algorytm szukania modulo - wytłumaczenie zasady działania
: 1 lip 2020, o 21:43
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 }\)?
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 }\)?