Considere o algoritmo a seguir (bastante deselegante) para imprimir três números em ordem crescente.
Algoritmo 5.18 Imprimindo três números em ordem por força bruta.
Condições prévias:
.
Condições posteriores:Os elementos de
são impressos em ordem crescente.
se \(a<b\) então
「 se \(b<c\) então
imprimir \(a, b, c\)
senão
「 se \(a<c\) então
imprimir \(a, c, b\)
senão
\(\llcorner\quad\llcorner\quad\) imprimir \(c, a, b\)
senão
「 se \(a<c\) então
imprimir \(b, a, c\)
senão
「 se \(b<c\) então
imprimir \(b, c, a\)
senão
imprimir \(c, b, a\)
(a)Desenhe uma árvore de decisão para modelar as escolhas feitas por esse algoritmo.
(b)Esse algoritmo é ótimo com respeito ao número de comparações<?Explique.
Condições posteriores:Os elementos de
se \(a<b\) então
「 se \(b<c\) então
imprimir \(a, b, c\)
senão
「 se \(a<c\) então
imprimir \(a, c, b\)
senão
\(\llcorner\quad\llcorner\quad\) imprimir \(c, a, b\)
senão
「 se \(a<c\) então
imprimir \(b, a, c\)
senão
「 se \(b<c\) então
imprimir \(b, c, a\)
senão
imprimir \(c, b, a\)
(b)Esse algoritmo é ótimo com respeito ao número de comparações<?Explique.
Passo 1
O enunciado apresenta um algoritmo que, por força-bruta, compara
para imprimir esses três valores em ordem crescente.
Conteúdo: construção de árvore de decisão e análise de comparações em algoritmo de ordenação.
Conteúdo: construção de árvore de decisão e análise de comparações em algoritmo de ordenação.
Passo 2
A árvore de decisão (cada nó é um teste, cada ramo “sim” ou “não”) é:
Passo 3
Resposta
(a) Veja a árvore de decisão descrita no Passo
.
(b) Sim. O algoritmo faz no máximo comparações e o limite inferior para ordenar três elementos é
, logo ele é ótimo nesse sentido.
(b) Sim. O algoritmo faz no máximo