Solução por Anita Ramos
Para este problema utilizaremos uma nova função que irá calcular qual o número da sequência de Fibonacci de posição $$a$$ e o número de chamadas feitas. Tudo isso fora da $$int$$ $$main()$$. Esse recurso facilita na produção de um programa mais compacto, organizado e eficiente.
Iniciando a programação então, após adicionar a biblioteca, declaramos a variável $$cont$$ para que ela possa ser utilizada em toda a programação. Depois, temos a função $$int$$ $$fib()$$, responsável por toda a lógica, que irá receber um valor e retornar o número de chamadas (a partir da $$cont$$, que soma 1 sempre que essa função é acionada) e o número de posição $$a$$ na sequência de Fibonacci (a partir da “chamada” repetidamente da função $$fib()$$). Assim, tomando como exemplo o valor recebido como 4, temos:
fib(4) $$=$$ fib(3) $$+$$ fib(2) $$<=>$$
fib(4) $$=$$ [fib(2) $$+$$ fib(1)] $$+$$ [fib(1) $$+$$ fib(0)] $$<=>$$
fib(4) $$=$$ [(fib(1) $$+$$ fib(0)) $$+$$ fib(1)] $$+$$ [fib(1) $$+$$ fib(0)] $$=$$ 1 $$+$$ 0 $$+$$ 1 $$+$$ 1 $$+$$ 0 $$=$$ 3
Em seguida, o programa executa apenas a $$int$$ $$main()$$ que irá ler as linhas de entrada e imprimir, a cada caso de teste, o resultado obtido na função $$fib()$$ do número recebido e o número de chamadas feitas de acordo com a forma de impressão requisitada.
Segue o código comentado para melhor compreensão da solução:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include<bits/stdc++.h> //biblioteca utilizada | |
| int cont=0; //declara 'cont' como 0 para ser válida dentro de fora da 'int main' | |
| int fib(int a) //função 'fib' que realiza a "lógica" de fibonacci | |
| { | |
| cont++; //soma-se 1 a cont | |
| if(a==0 || a==1)return a; //se 'a' for 0 ou for 1, retorna o próprio valor de 'a' (0 ou 1) | |
| return fib(a-1)+fib(a-2); //se não, retorna a soma do fibonacci anterior + o fibonacci anterior do anterior | |
| } | |
| int main() | |
| { | |
| int N,i; //declara 'N' e 'i' | |
| long int a; //declara 'a' como uma long int | |
| scanf("%d", &N); //lê a primeira linha de entrada | |
| for(i=0; i<N; i++) //loop para executar todos os casos de teste | |
| { | |
| cont=0; //'cont' zera | |
| scanf("%ld", &a); //lê o valor da posição da sequência desejada | |
| printf("fib(%ld) = %d calls = %ld\n", a, cont-1, fib(a)); //imprimi a saída de acordo com os critérios | |
| } | |
| return 0; //retorna a 0 | |
| } |