Atividade II

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 yuri.maluf@riobrancofac.edu.br.

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$.

   function func_fibonacci($n){
     round($n);
     $total =  $n!=1 ? ($n!=2 ? (func_fibonacci($n-1)+func_fibonacci($n-2)) : 1): 0 ;
     return $total;
    }

Algoritmo 1

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.

Figura 1: Calculadora Hp12c

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$.