Úloha 3.u4: Dělitelnost dlouhého čísla (2 b)

Zadáno v čísle 24.3.

Řešeno v čísle 24.5.

Zadání

Po drátě nám celý den přichází velmi dlouhé číslo zapsané ve dvojkové soustavě. Na konci dne máme rozhodnout, zda je toto číslo dělitelné třemi. Navrhněte algoritmus, který to bude umět vyřešit. Počítejte s tím, že se číslo nevejde do žádné paměti.

Řešení

Každé číslo ve dvojkové soustavě lze rozepsat jako součet jednotlivých cifer násobených mocninami dvojky, tedy jako

\[ a_ n\cdot 2^ n + a_{n-1}\cdot 2^{n-1} + \dots + a_2\cdot 2^2+a_1\cdot 2^1+a_0\cdot 2^0\hbox{,} \]

kde $a_ n, \ldots , a_0$ jsou jednotlivé dvojkové číslice. Protože mocniny násobíme vždy nulou nebo jedničkou, můžeme součet zkrátit na součet mocnin dvojky, které násobíme jedničkou.

Není složité si všimnout (např. rozepsáním každého čísla jako $an+b$), že platí1

\[ (m_1 + \dots + m_ k) \bmod n = (m_1 \bmod n + \dots + m_ k \bmod n) \bmod n\hbox{.} \]

Využijeme toho: stačí tedy sčítat jen zbytky jednotlivých mocnin po dělení třemi.

Nyní si všimneme, že zbytek po dělení třemi je u sudých mocnin dvojky jedna a u lichých dva: pro $2^0 = 1$ a $2^1 = 2$ to platí, při násobení čtyřmi se zbytek nezmění2:

\[ 4\cdot (3k+c) = 12k + (3+1)c = 12k + 3c + c \equiv c \pmod{3} \]

Stačí tedy si za jedničky na sudých pozicích vždy přičíst do nějaké proměnné jedničku a za jedničky na lichých pozicích dvojku. Kdykoliv bude hodnota proměnné větší nebo rovna třem, trojku odečteme, čímž získáme zbytek po dělení třemi. Pokud na konci dne bude v proměnné nula, bylo celé číslo dělitelné třemi.

Tohle řešení má na první pohled jeden háček: pokud číslice přichází od nejvyšších řádů („zleva“), nevíme, jestli začínáme na sudé nebo na liché pozici. Ovšem pokud se na začátku netrefíme a budeme přičítat u sudých pozic dvojky a u lichých jedničky, vyjde nám zbytek dvojnásobku původního čísla – jako kdybychom si na konec přimysleli ještě jednu nulu. Násobení celého čísla dvěma sice změní zbytek u čísla nedělitelného trojkou (z jedničky na dvojku a opačně, můžete si to zkusit dokázat), ale dělitelnost se násobením dvěma zachová. Stačí tedy opět zkontrolovat, zda jsme dostali na konci nulu či nikoliv. Je tedy jedno, jestli číslo má lichý nebo sudý počet cifer, stejně tak nezáleží na tom, jestli číslo přichází „zleva“ či „zprava“, protože se zbytky jednotlivých řádů pravidelně střídají.

Pavel


1) „$a \bmod b$“ značí zbytek $a$ po dělení číslem $b$, tato operaci se nazývá modulo

2) Zápis „$a\equiv b \pmod{n}$“ značí, že $a$ a $b$ mají stejný zbytek po dělení $n$, a většinou se čte „$a$ je kongruentní$b$ modulo $n$