Jak rozwiązać te zadania? rozszerzona matura z informatyki 2017

Question

Witam, w następnym roku planuje zdawać rozszerzoną informatykę, patrząc na część 1 z aktualnego roku mam problem z 2 zadaniami, mianowicie:

Jest oto taki kod:

 int licz(int x)
        {
            if (x == 1)
                return 1;
            else
            {
                int w = licz(x / 2);
                if (x % 2 == 1)
                    return w + 1;
                else
                    return w - 1;
            }
        }

A oto treść zadania

Nie mam pojęcia jak nawet zacząć zadanie 2.2, a 2.3 no ok wydaje się proste wystarczy kolejno od 101 rozpisać wartości, pewnie wystarczy z 5 razy... ale okazuje się, że dopiero dla x równego 135 wartość funkcji wynosi 0, to jakim sposobem to zrobić?

Dzięki za pomoc

Answer 1

Pierwsze zadanie tak naprawdę jest pytaniem o to, który z podanych wzorów łączy ilość wywołań z liczbą x. Niestety na razie nie ogarniam rekurencji, więc tego nie policzę, ale od razu można odrzucić odpowiedzi A i D. Dla nich x wychodzi większe od 13, więc nie powinno się wywołać 4 razy, co jest sprzeczne z podanym przykładem. Obstawiam też, że dla C i x=5 funkcja wywoła się 2-3 razy. Pozostaje B?

Comments

Nom, ta funkcja sprowadza się do logarytmu o podstawie 2 zaokrąglanej wartości, więc tak od razu można skojarzyć, że wynikiem będzie coś o podstawie potęgi równej 2. Wartość k = 4 będzie obejmowała zakres zmiennej x od 8 do 15, z czego najmniejsza jest 8, co jest wynikiem 2^3, czyli 2^(k-1).

---

To ma sens, dzięki. Jakbyście wpadli na jakiś pomysł z zadaniem drugim to chętnie posłucham :D