Ćwiczenia 2: Procedury operujące na liczbach

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.

  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.
  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.
  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\).
  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.
  6. Napisz procedure, która sprawdza, czy dana liczba jest pierwsza.
  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ę.
  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.