Arquivo Discussoes de Programacao e Tecnologia Bom dia!
Galera prestei um concurso tempos atrás para desenvolvedor, tinha uma questão que me intrigou muito e até agora não consegui resolver, favor me ajudem neste problema abaixo:
Qual é o valor retornado pela função C apresentada a seguir, quando o parâmetro passado for o número 4(n=4)
int F (int n){
if (n == 1 || n == 2) return n;
else return F (n-1) + n * F (n-2);
}
A resposta correta que esta no gabarito é: 13
Mas não entendi a lógica do código???[i]
Você não sabe fazer um “teste de mesa”?
Faça uma tabelinha com os valores de F para n = 1, n = 2, n = 3 e n = 4.
n F(n)
1 1
2 2
3 F (n-1) + n * F (n-2) = F(2) + 3 * F(1) = 2 + 3 * 1 = 5
4 aqui é por sua conta.
Mas como assim, nunca ouvi falar neste de mesa?
como que é feito qual é a lógica que usa?
Amigo, você viu a linha 3 do meu exemplo? Faça a mesma coisa para a linha 4.
“Teste de mesa” é uma coisa que você provavelmente deveria ter aprendido na escola.
É o seguinte: você fazer a mesma coisa que o computador faz, passo a passo, e anotar os resultados intermediários no papel.
O grande lance desse Algoritimo é que vc trabalha com o que chamamos de Recursividade.
Isso, é quando dentro de um método, vc acaba chamando ele mesmo, o que acontece no seu Else.
Quando cai no else, o método é chamado novamente, dai ele é executada do inicio até retornar um valor para a chamada anterior, e assim por diante.
Para vc entender melhor e bom procurar algum material sobre recursividade.
Aqui tem uma explicação de como funciona recursividade: http://rafaelsakurai.blogspot.com/2008/05/recursividade-em-java.html
n F(n)
1 1
2 2
3 F (n-1) + n * F (n-2) = F(2) + 3 * F(1) = 2 + 3 * 1 = 5
4 F (n-1) + n * F (n-2) = F(3) + 4 * F(2) = 3 + 4 * 2 = 11
pq o resultado do gabarito eh 13?
4 F (n-1) + n * F (n-2) = F(3) + 4 * F(2) = 3 + 4 * 2 = 11pq o resultado do gabarito eh 13?
Porque F(3) é 5 e não 3.
5 + 4 * 2 = 13
ah sim
eh verdade
4 F (n-1) + n * F (n-2) = F(3) + 4 * F(2) = 3 + 4 * 2 = 11pq o resultado do gabarito eh 13?
Porque F(3) é 5 e não 3.
5 + 4 * 2 = 13
Como falei antes, é Recursividade. O método é chamado dentro dele mesmo.
Quando o N = 4, vamos para o ELSE. Lá dentro do else temos: F(n-1). Esse F(n-1) é a chamada do método. Aqui ele entra novamente no método, e vai continuar entrando até que o valor de N seja 1 ou 2.
entendi
meio pegadinha
F(4)
****
n=4
F(3) + 4*F(2)
**********************
F(3)
****
n=3
F(2) + 3*F(1)
**********************
F(2)
****
n=2
2
**********************
F(1)
****
n=1
1
**********************************************************************
F(3) + 4*F(2)
(F(2) + 3*F(1) )+ 4*F(2)
(2 + 3*1) + 4*2
13
Entendi o esquema. isso é pura matemátcia computacional.
Obrigado pessoal!