Funkcja linijkowa dla pewnej liczby naturalnej n określa największą potęge liczby 2 przez którą dzieli się podwojona wartość liczby n.
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.
Pierwsze 10 wartości Funkcji Linijkowej to: 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, ..
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 ∞.
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:
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.
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.
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.
(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.
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.
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.