1831. f91

Olá meus amigos nerds, hoje vamos brincar de estudar uma função recursiva, já que é isso que o problema 1831. f91 nos pede. Mais especificamente o problema nos fornece uma função recursiva e pede que computemos o resultado.

Solução

Você deve estar se perguntando o que tem de interessante nesse problema. Sim, esse é um problema razoavelmente fácil, mesmo assim tem alguns detalhes legais que podemos explorar. O problema define a seguinte função:

• Se N ≤ 100, então f91 (N) = f91 (f91 (N + 11));
• Se N ≥ 101, então f91 (N) = N - 10

Obviamente se implementarmos essa função já temos o problema resolvido:

f91(n)
    if n > 100 return N-10
    else return f91(f91(N+11))

Agora vamos tentar ser um pouco mais espertos e deduzir analiticamente o resultado dessa recursão. É ai que essa função fica divertida, pois ela sempre retorna 91 para todos os números menores ou iguais a 101. Desenvolvendo a função temos:

f91(n) = f91(f91(n+11)) = f91(f91(f91(f91(n+2*11)))) = f91(f91(f91(f91(f91(f91(n+3*11)))))) =...

Observe que n+11, n+2*11, n+3*11 é uma sequência extritamente crescente. Em algum momento, o valor dessa sequência ultrapassara 100 mas será menor ou igual a 111 (estamos somando 11). Nesse momento começaremos a subitrarir 10 e somar 11 a esse número, ou seja, duas chamadas consecutivas dessa função terão o efeito de somar 1 ao número (que ainda será menor que 100), exemplo:

f91(99) = f91(f91(99+11) = f91(f91(110)) = f91(100)

Ou seja, por indução f91(n) = f91(n+1) para todo n <= 90. Mas:

f91(100) = f91(f91(111)) = f91(101) = 91

logo f91(n) = 91 para todo n>=90. Para n < 90 temos:

f91(n) = f91(f91(n+11)) = f91(...f91(n+i*11)...)

e como n+i*11 é maior que 90 (basta tomar um i suficientemente grande):

f91(n) = f91(f91(n+11)) = f91(...f91(X > 90)...) = f91(...f91(91)...)

aplicando o fato de que f91(91) = 91 recursivamente temos: f(n) = f91(91) = 91.

Implementação

Agora que já entendemos como funciona a função f91, fica um desafio meu! Como seria definida a função f92? E a função f100000000?