Strona główna » Algorytmy » Teoria Liczb » Funkcja Linijkowa
 

Funkcja Linijkowa

Definicja

Funkcja linijkowa dla pewnej liczby naturalnej n określa największą potęge liczby 2 przez którą dzieli się podwojona wartość liczby n.

Przykład

Oznaczmy funkcję linijkową poprzez F(n). Wtedy F(5) = 1, ponieważ 10 / 2 = 5 i wynik jest liczbą nieparzystą. Z kolei dla F(8) = 3, ponieważ 8 / 2 = 4, 4 / 2 = 2, 2 / 2 = 1 czyli podsumowując 8 / 23.

Ciąg

Pierwsze 10 wartości Funkcji Linijkowej to: 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, ..

Uwagi

Może się pojawic pytanie o wartość funkcji linijkowej dla wartości 0. Ze względu na to, że 0 można podzielić przez dowolną wartość to odpowiedzią jest .

Implementacja

Rozwiązanie arytmetyczne

Pisząc funkcję Linijkową wystarczy wyliczyć wartość 2n, a następnie sprawdzić ile można ją podzielić przez 2. Zadanie to realizuje poniższy kod:

C++
C#
  1. static int funkcjaLinijkowa(int n) {
  2.   int wartosc = 2 * n;
  3.   int ile = 0;
  4.   while (wartosc % 2 == 0) {
  5.     ile++;
  6.     wartosc /= 2;
  7.   }
  8.   return ile;
  9. }

W powyższym kodzie najpierw (2.) wyliczamy wartość oraz (3.) inicjalizujemy licznik, a potem (4. - 7.) zliczamy ile razy udało się podzielić wyliczoną wartość przez 2. Na koniec (8.) zwracamy zmienną ile.

Optymalne rozwiązanie arytmetyczne

Przedstawione rozwiązanie można w bardzo prosty sposób zoptymalizować. Mianowicie na początku wprowadzona wartość n jest mnożona przez 2. W kodzie można to pominąć i od razu ustawić wartość zmiennej ile na 1. W ten sposób zaoszczędzane jest jedno dzielenie przez 2 oraz nie istnieje problem związany z przepełnieniem zmiennej, a więc zwiększa się zakres obsługiwanych wartości funkcji.

C++
C#
  1. static int funkcjaLinijkowa(int n) {
  2.   int ile = 1;
  3.   while (n % 2 == 0) {
  4.     ile++;
  5.     n /= 2;
  6.   }
  7.   return ile;
  8. }

Operacje binarne

W zapisie binarnym kolejne jedynki w zapisie oznaczają kolejne potęgi 2. Jeśli na najmniej znaczącej pozycji stoi 1 w zapisie binarnym to liczba nie jest podzielna przez 2, ale jeśli stoi 0 to jest. Analizując ten przypadek oraz dla kolejnych potęg 2 łatwo się przekonać, że daną liczbę można podzielić przez 2 tyle razy ile zer na początku.

Przykładowo rozważmy ponownie przypadki z początku artykułu. Liczba 2·510 = 10102 czyli jest podzielna tylko raz. Z kolei 2·810 = 102·1002 = 10002. Licząc zera od prawej strony do najbliższej linijki otrzymujemy 3.

C++
C#
  1. static int funkcjaLinijkowa(int n) {
  2.   int ile = 1;
  3.   while ((n & 1) == 0) {
  4.     ile++;
  5.     n >>= 1;
  6.   }
  7.   return ile;
  8. }

(2.) Ponownie pomijamy przypadek mnożenia przez dwa i uwzględniamy to w wartości licznika. (3.) Sprawdzamy czy najmniej znacząc pozycja to 0. Jeśli tak to (4.) zwiększamy licznik i (5.) przesuwamy wartość binarną o 1 w prawo (tj. dzielimy przez 2). Powtarzamy ten proces dopóki nie na trafimy na 1. (7.) Na koniec zwracamy wartość zmiennej ile.

Testowanie funkcji

Poniższy kod pozwoli przetestować każdą implementacją funkcji przedstawioną w artykule. W ramach testu wypisywane jest k pierwszych wartości funkcji, gdzie wartość k jest wczytywana od użytkownika.

Zadania

Zadanie 1

Napisz rekurencyjną wersję kodu do szukania wartości Funkcji Linijkowej. Funkcja powinna przyjmować jedynie jeden argument n tj. argument funkcji. Przetestuj program wypisując k pierwszych wyrazów.