function func_fibonacci($n){
round($n);
$total = $n!=1 ? ($n!=2 ? (func_fibonacci($n-1)+func_fibonacci($n-2)) : 1): 0 ;
return $total;
}Atividade - Estrutura de Dados
Esta atividade é composta por duas questões. A questão de número 1 é de carácter mais teórico. Já a de número 2 tem cunho mais prático. As questões devem ser enviadas de forma separada, cada uma contendo um único arquivo. A primeira questão precisa apresentar todo o seu desenvolvimento para chegar na resposta. A segunda questão deve ser enviada por meio de um arquivo com extensão .php. O script php deve constar instruções claras de como utilizar e executar o algoritmo para obter a transcrição. Em caso de dúvida mande um email para [email protected].
Questão 1
Dado um número inteiro n positivo, o Algoritmo 1, descrito pela função func_fibonacci, fornece a sequência de Fibonacci até o n-ésimo elemento. Desta forma, determine o número de chamadas recursivas de func_fibonacci, sua complexidade e a sua ordem de crescimento \mathcal{O}(g(n)) em função de n.
Questão 2
Lançada em 1981 pela empresa de tecnologia Hewlett-Packard, a calculadora Hp12c se tornou a calculadora financeira mais famosa e também mais usada dentro dos meios financeiros. A calculadora Hp12c possui um sistema distinto das demais para realizar operações aritméticas. Isso se deve ao fato dela adotar a notação polonesa reversa, conhecida pelas siglas RPN (Reverse Polish Notation). A adoção desta formatação confere facilidades na implementação e maior performance nas rotinas numéricas.
Como ponto de partida, vamos assumir o sistema adotado nas calculadoras comuns, no qual para realizar a operação de dois números digitamos o primeiro, na sequência a operação matemática desejada seguida pelo segundo número. Por fim o resultado é exibido no display. Essa operação é similar a forma como escrevemos operação algébrica manualmente como:
2+5
10-2
12 x 3.
Na notação RPN a sequência de introdução dos dados muda. Primeiro digitamos os números e somente depois é que informamos a operação desejada. Seguindo o exemplo acima na notação RPN
2 5 +
10 2 -
12 3 x.
Para executar as rotinas de cálculo, a Hp12c dispõe de 4 slots de memória temporária.
\begin{split} \underbrace{D}_{X} \rightarrow \underbrace{C}_{Y}& \rightarrow \underbrace{B}_{Z} \rightarrow \underbrace{A}_{T}\,\,\,\, \text{ (Instante de tempo i)}\\ \underbrace{E}_{X} \rightarrow \underbrace{D}_{Y}& \rightarrow \underbrace{C}_{Z} \rightarrow \underbrace{B}_{T}\,\,\,\, \text{ (Instante de tempo ii)}\\ \underbrace{F}_{X} \rightarrow \underbrace{E}_{Y}& \rightarrow \underbrace{D}_{Z} \rightarrow \underbrace{C}_{T}\,\,\,\, \text{ (Instante de tempo iii)} \end{split} \tag{1}
No Diagrama 1, quando introduzimos o valor E na memória “deslocamos” (desloca o ponteiro) todos os slots, de forma que transitamos do instante i para o instante ii. Note que o valor A é retirado para ceder espaço para E. Isto é, a alocação de memória funciona em um esquema LIFO (Last In First Out). O processo segue todo tempo dessa forma. Os slots têm as seguintes nomenclaturas seguindo a ordem de entrada: X, Y, Z e T. As operações aritméticas são feitas apenas com o conteúdo armazenado na memoria X e Y.
Diante do exposto, construa um algoritmo para efetuar a conversão da notação tradicional com parenteses para a notação RPN. Ao fim, o algoritmo deve ser capaz de ler, como input, QUALQUER expressão aritmética tal como
K=-54: \left\{(-2+\sqrt{81})^2:(24-2\cdot7)-5\cdot[(1+(-5)^{3}):15] \right\} e gerar como output a sequência de botões que o usuário deverá apertar para chegar ao resultado final K.