Strona główna » Algorytmy » Artykuły » Nieznana Funkcja
f( )x
 

Nieznana Funkcja

Zagadka

Pewna funkcja przekształca dowolną liczbę w inną. Zasada działania funkcji jest tajna, ale wiadomo, że poniższe równości są prawdziwe.

Ile wyniesie f(2018)? Według jakiej zasady następuje przekształcenie?

Rozwiązanie

Odpowiedź

Funkcja dla 2018 przyjmuje wartość 7.

Wyjaśnienie

Liczby można zapisywać w różnych reprezentacjach. Wszystkie operacje w codziennym życiu wykonujemy w systemie dziesiątkowym. Takie liczby akceptuje funkcja, ale patrzy na ich reprezentację w systemie binarnym i sumuje cyfry. Z tego powodu f(7) = f(1112) = 3, a f(36) = f(1001002) = 2.

Znając zasadę działania funkcji wystarczy przeliczyć, że f(2018) = f(111111000102) = 7.

Implementacja

W celu policzenia cyfr 1 w rozwinięciu pewnej liczby można skorzystać z operatorów logicznych, albo arytmetycznych. Poniżej zostało przedstawione rozwiązanie arytmetyczne, które korzysta z operacji modulo, aby sumować kolejne cyfry. Warunkiem stopu w tym przypadku jest osiągnięcie przez liczby wartości 0 co będzie oznaczać, że nie pozostała już do zsumowania żadna cyfra.

  1. int policzBity(int a) {
  2.   int bitow = 0;
  3.   while (a > 0) {
  4.     bitow += a % 2;
  5.     a /= 2;
  6.   }
  7.   return bitow;
  8. }

Funkcja policzBity() przyjmuje jeden argument a, dla którego wykonywana jest następująca pętla: dodaj obecnę resztę z dzielenia przez 2, a następnie pozbądź się ostatniego bita (poprzez dzielenie całkowitoliczbowe przez 2).

Testowanie funkcji

Poniższy fragment kodu służy do wczytania danych od użytkownika, a następnie wypisania sumy bitów.

  1. int main () {
  2.   int a;
  3.   cout << "Podaj liczbe\n a = ";
  4.   cin >> a;
  5.   cout << "f(" << a << ") = " << policzBity(a);
  6.   system("pause");
  7.   return 0;
  8. }