1-Pesquisa

Introdução

Vamos estudar algoritmos para resolver problemas com ordem, problemas como quem é mais caro, quem é mais barato. Qual o menor caminho? Qual é o melhor produto?

Todos esses problemas envolvem dizer "que um objeto é maior do que outro objeto". Qual é o hotel mais próximo? Qual é o cinema mais próximo? Qual o horário do próximo trem que irá sair? Tudo isto envolve uma comparação, uma pergunta do tipo "quem" ou "algo", que é "mais" ou "menos".

Envolve também a ordenação de objetos. A ordenação é importante porque é muito mais fácil encontrar algo em um conjunto ordenado. A ordenação se traduz em um esforço para colocar ordem na casa. Já parou para pensar em quantos sites ou aplicações estão disponíveis hoje e que fazem uso de algoritmos que respondem a estar perguntas?

Afinal de contas os computadores e a ciência da computação estão aqui para responder a estas perguntas. Imagine responder a perguntas dessa natureza trabalhando com informação em papel, em livros, pastas, etc.

Alguns exemplos do tipo de pergunta que estou falando:

Quem ganhou o jogo? Quem fez mais gols.

Quem ganhou o campeonato? Quem fez mais pontos.

Quem ganhou o campeonato e foi rebaixado? Quem fez menos pontos.

Pare para pensar: ao nosso redor, tudo tem uma questão de ordem. Se você quer ir para o trabalho, você quer o ônibus que vai chegar mais rápido, em menos tempo. Ou se você está em casa... Quer pegar o primeiro ônibus, que está mais próximo da saída. Tudo isso envolve ordenar um monte de coisas. Isso é o que faremos aqui: aprender a ordenar os maiores, os menores, os melhores.

Quando você consulta em um site por um apartamento você busca pelos mais baratos? pelos mais caros? Em qualquer caso, é uma questão de ordem.

Não importa... Vamos aprender a encontrar aquilo que procuramos, com uma ordem. O mais rápido,o melhor, o com maior nota, o com menor e maior tempo.

Um problema simples

Vamos começar o estudo de algoritmos avançados com um problema simples: Encontrar o carro mais barato!

Este é um problema comum no dia a dia. Pessoas procuram na internet sempre pelo produto mais barato. Pode ser um carro, um apartamento, uma vestido, um tênis. Nós vemos isso em sites e até no mundo real.

A partir de um conjunto de produtos, queremos encontrar o produto com preço menor.

Vamos considerar então que estamos buscando o menor valor para um carro em um conjunto de carros.

Para esse exemplo é fácil encontrar a resposta. Mas procurando na internet por exemplo é outra coisa.

Mesmo com serviços de comparação de preços. O que temos é sempre uma lista de preços encontrados nas diversas lojas.

Imagine uma busca em uma grande feira de automóveis usados. Neste caso, a busca não é tão simples.

Pensar no problema

Quando encontramos um problema comum no dia a dia, quase sempre pensamos de forma automática para encontrar a solução. É quase instantâneo, rápido como acender a luz de um escritório. Mas na verdade o processo mental tem vários passos. Na verdade construímos um algoritmo em nossa mente para resolver os problemas que encontramos na vida.

Quando pensamos em uma solução o processo parece automático mas não é. O ponto é que precisamos expressar a solução detalhadamente, passo a passo, para que possamos construir um algoritmo que possa ser convertido para um software.

Mas antes de partir para a escrita do algoritmo, ainda assim é importante, pensar no problema, estudá-lo, analisar as alternativas de solução e todos os pontos que precisam ser tratados. É preciso ter um entendimento claro do problema e uma visão geral do problema. Isso é necessário para que possamos ter uma solução completa para o problema, isto é, uma solução que considere todos os aspectos do problema.

Isto pode parecer óbvio, mas é muito comum até mesmo entre profissionais com experiência, não analisar o problema adequadamente e por isso construir soluções precipitadas e inadequadas.

Em nosso caso precisamos encontrar o menor valor e para isso precisamos considerar o preço de todos os carros da lista e comparar os preços a fim de determinar qual o menor valor, qual o menor preço, qual o mais barato.

Para isso comparamos o preço do carro atual da lista com o preço mais barato encontrado até o momento.

Tente fazer a simulação do algoritmo de encontrar o carro mais barato no papel! Anote na caixa atual a posição atual do carro que você está comparando, começando com a posição zero. Na caixa maisBarato coloque sempre a posição do carro mais barato, também começando com zero

Descrever a solução do problema com suas próprias palavras

Quando escrevemos a solução do problema estamos na verdade descrevendo o algoritmo de uma forma geral, sem entrar em muitos detalhes. Mas isso ajuda a registrar o entendimento e ao mesmo tempo a pensar nos detalhes.

Uma solução em termos gerais poderia ser:

1. ver o preço do primeiro carro

2. considerar o preço do primeiro carro como o menor carro

3. comparar com o preço do próximo carro

4. se o preço do carro anterior for maior do que o preço do próximo carro então o menor carro é o próximo carro

5. repetir o processo ate acabar os carros

Agora sim fica mais fácil Implementar o algoritmo

O algoritmo em pseudocódigo ficaria assim:

maisBarato= 0

atual = 0

para atual = 0 até 4 inclusive {

se precos[atual] < precos[maisBarato] {

maisBarato= precos[atual]

}

}

Refatorar o algoritmo

Precisamos sempre buscar melhorar a qualidade do software. A esta abordagem chama-se refatoração. No caso vamos refatorar o algoritmo para que use os conceitos da orientação a objetos. Para isso precisamos pensar em objetos.

Podemos rever o algoritmo e então analisar o que podemos expressar como objetos. No caso o carro pode ser expresso como um objeto e disso temos que criar uma classe para o carro.

Em todos os algoritmos que veremos vamos praticar a refatoração para usar a orientação a objetos.

Outro ponto que precisamos considerar na refatoração é a divisão de responsabilidades. No caso devemos buscar uma forma de dividir as responsabilidades dentro do algoritmo, criando uma função para cada tarefa. Cada função deve ter uma unica responsabilidade.

No caso do algoritmo de busca do menor podemos criar uma função para encontrar o menor valor de um conjunto de carros.

Uma pergunta com mais de uma resposta

Imagine agora se houver mais de um carro com o menor preço?

Como podemos tratar isso no algoritmo?

Qual o melhor algoritmo para responder a esta pergunta que tem mais de uma resposta?