Algoritmos e Estruturas de Dados I
– Refinamentos Sucessivos
Profa. Mercedes Gonzales
Márquez
Refinamento sucessivos


Um algoritmo é considerado completo se os
seus comandos forem do entendimento do seu
destinatário.
Um comando que não for do entendimento do
usuário terá de ser desdobrado em novos
comandos, que constituirão um refinamento do
comando inicial.
Refinamento sucessivos


Exemplo 1 (bem simples): O algoritmo para
calcular a média aritmética de dois números
pode ser desdobrado da seguinte forma:
Algoritmo CALCULA_MÉDIA
1.
Receba os dois números
2.
Calcule a média dos dois números
3.
Exiba o resultado
Refinamento sucessivos


Podemos desdobrar o comando “Calcule a
média dos dois números” em:

Soma os dois números

Divida o resultado por 2
Após esse refinamento, o algoritmo pode ser
considerado completo, a menos que o
destinatário não saiba fazer as operações de
adição e divisão, ou não seja capaz de
entender diretamente algum comando
Refinamento sucessivos


O algoritmo estando completo, podemos
reescrevê-lo, inserindo o refinamento na
posição do comando que foi refinado. Assim:
Algoritmo (“visão global”)
1. Receba os dois números
2. Soma os dois números
3. Divida o resultado por 2
4. Exiba o resultado
Refinamento sucessivos

À medida que um algoritmo se torna maior e
mais complexo, a sua “visão global” torna-se
menos clara e, neste caso, um algoritmo
apresentado com os refinamentos sucessivos
separados torna-se uma melhor abordagem
para quem precisar entendê-lo.
Refinamento sucessivos


Exemplo 2: O algoritmo para escrever os
termos de Fibonacci inferiores a L poderia ser
desdobrado em:
Algoritmo
1. Receba o valor L
2. Processe os dois primeiros termos
3. Processe os termos restantes
Refinamento sucessivos
1. Receba o valor L
Leia (L)
2. Processe os dois primeiros termos
Se L>1
T1 ← 1 (*)
T2 ← 1
Escreva T1,T2
* Veremos nas próximas aulas que o símbolo ← será usado na
representação de PseudoCódigo para representar atribuição de
dados.
Refinamento sucessivos
3. Processe os termos restantes
Fib ← T1+T2
Enquanto Fib<L então
Escreva Fib
T1 ← T2
T2 ← Fib
Fib ← T1+T2
Fim enquanto
Refinamento sucessivos
Juntando os refinamentos temos a visão global do algoritmo completo.
Leia L
T1 ← 1
T2 ← 1
Se T1<L então
Escreva T1,T2
Fib ← T1+T2
Enquanto Fib<L então
Escreva Fib
T1 ← T2
T2 ← Fib
Fib ← T1+T2
Fim enquanto
Refinamento sucessivos

Exemplo 3: Leia três valores inteiros, determine
e imprima o menor deles.
Algoritmo
1. Leia os números
2. Determine o menor número
3. Escreva o menor número
Refinamento sucessivos
1. Leia os números
Leia A,B,C
2. Determine o menor número
Se A<B e A<C então
Menor ← A
Senão
Determine o menor dentre B e C
Fim se
Refinamento sucessivos
3. Determine o menor dentre B e C
Se B<C então
Menor ← B
Senão
Menor ← C
Fim se
4. Escreva o menor número
Escreva Menor
Refinamento sucessivos
Juntando os refinamentos temos a visão global do algoritmo
completo
Leia
A,B,C
Se A<B e A<C então
Menor ← A
Senão
Se B<C então
Menor ← B
Senão
Menor ← C
Fim se
Fim se
Escreva Menor