Próbuję rozwiązać ostatni arkusz z informatyki w ramach przygotowania do tegorocznej matury i zaciąłem się na poniższym zadaniu.
Mam taką funkcję rekurencyjną:
licz(x)
jeżeli x = 1
podaj wynik 1
w przeciwnym przypadku
w <- licz(x div 2)
jeżeli x mod 2 = 1
podaj wynik w+1
w przeciwnym przypadku
podaj wynik w-1
div - dzielenie całkowite, mod - reszta z dzielenia
Do tego kodu muszę wykonać takie zadanie:
Podaj najmniejszą liczbę całkowitą x większą od 100, dla której wynikiem wywołania licz(x) będzie 0.
Doszedłem do tego, że żeby otrzymać ostateczny wynik zero, jedna z rekurencji musi mi zwrócić wynik w=-1 lub w=1.
w=-1
x%2=1
x=0
w=1
x%2=0
x=0
Wówczas to zero spowoduje, że każde kolejne wykonanie wywoła zero, co da mi ostatecznie licz(x)=0, lecz nie jestem w stanie wydedukować, jaka najniższa wartość wejściowa pozwoli mi to osiągnąć.
Proszę o pomoc w znalezieniu sposobu na rozwiązanie tego zadania.
JEST TO CZĘŚĆ TEORETYCZNA, NA KARTCE.