Informatyka MIMUW

Rozwiązania poniższych zadań to proste procedury operujące na liczbach całkowitych.
Dla każdej procedury rekurencyjnej podaj jej specyfikację, tj. warunek wstępny i końcowy,
oraz uzasadnij jej poprawność.
Poprawność procedur rekurencyjnych można pokazać przez indukcję.

1. Stopień parzystości liczby całkowitej $x$, to największa taka liczba naturalna $i$, że $x$ dzieli się przez $2^i$.
   Liczby nieparzyste mają stopień parzystości 0, liczby 2 i -6 mają stopień parzystości 1,
   a liczby 4 i 12 mają stopień parzystości 2.
   Przyjmujemy, że 0 ma stopień parzystości -1.

   Napisz procedurę parzystość wyznaczającą stopień parzystości danej liczby całkowitej.
   
   Rozwiązania

2. Napisz procedurę, która przekształca daną liczbę naturalną w taką, w której cyfry występują w odwrotnej kolejności,
   np. 1234 jest przekształcane na 4321.
   
   Rozwiązania
3. Sumy kolejnych liczb nieparzystych dają kwadraty kolejnych liczb naturalnych, zgodnie ze wzorem:
   $\sum_{i=1}^k (2 i - 1) = k^2$.
   Wykorzystaj ten fakt do napisania procedury sqrt obliczającej sqrt x $= \lfloor\sqrt{x}\rfloor$
   i nie korzystającej z mnożenia, ani dzielenia.
   
   Rozwiązania
4. Liczbę naturalną nazwiemy rzadką, jeżeli w jej zapisie binarnym żadne dwie jedynki nie stoją obok siebie.
   Napisz procedurę rzadkie : int → int, która dla danej liczby naturalnej $n$ zwróci najmniejszą rzadką liczbę naturalną większą od $n$. Na przykład, dla $n = 42 = 101010_2$ mamy $\mathtt{rzadkie}\ 42 = 1000000_2 = 64$.
   
   Rozwiązania
5. Liczbę naturalną nazwiemy rzadką, jeżeli w jej zapisie binarnym żadne dwie jedynki nie stoją obok siebie.
   Napisz procedurę rzadkie : int → int, która dla danej liczby naturalnej $n$ wyznaczy liczbę dodatnich liczb rzadkich, które nie przekraczają $n$.
   Na przykład, dla $n = 42 = 101010_2$ mamy rzadkie 42 = 20.
   
   Rozwiązania
6. Napisz procedurę, która sprawdza, czy dana liczba jest pierwsza.
   
   Rozwiązania
7. Zaimplementuj kodowanie par liczb naturalnych jako liczby naturalne.
   To znaczy, napisz procedurę dwuargumentową, która koduje dwie liczby dane jako argumenty w jednej liczbie naturalnej.
   Dodatkowo napisz dwie procedury, które wydobywają z zakodowanej pary odpowiednio pierwszą i drugą liczbę.
   
   Rozwiązania
8. Napisz procedurę, która dla danej liczby $n$ sprawdzi czy pierścień reszt modulo $n$ zawiera nietrywialne pierwiastki
   z 1 (tj. takie liczby $k$, $k \neq 1$, $k \neq n-1$, że $k^2 \equiv 1\ \mod\ n$).
   Nota bene, jeśli takie pierwiastki istnieją, to liczba $n$ nie jest pierwsza.
   Odwrotna implikacja jednak nie zachodzi --- np. dla $n=4$ nie ma nietrywialnych pierwiastków z 1.
   
   Rozwiązania