Introdução à Programação B (2017/2018)

Aulas teóricas

Artur Miguel Dias



Teórica 07 (06/nov/2017)

Identificação das funções necessárias para a resolução dum problema de programação.
Técnicas de desenvolvimento de programas: top-down e bottom-up.
Busca dicotómica em vetores ordenados.
Ordenação de vetores.

Identificação das funções necessárias para a resolução dum problema de programação

Identificar quais são as funções que convém programar, é uma das partes mais difíceis da programação. As soluções mais simples e claras, nem sempre as conseguimos descobrir logo de início. Se o programa que estamos a escrever estiver a ficar demasiado complicado, pode valer a pena recomeçar e procurar uma solução mais simples.

Para exemplificar a procura duma solução simples e clara, vamos considerar o problema a seguir.

Problema do parque de estacionamento

Enunciado

Desenvolva um programa que calcule o preço a pagar no parque de estacionamento subterrâneo dos Restauradores, em Lisboa, a partir dos seguintes dados fornecidos pelo utilizador: Em Março de 1999, a tabela de preços (originalmente em Escudos, mas aqui já convertida para Cêntimos) era a seguinte: Mais informação: Procure fazer um programa claro e fácil de compreender. Para isso defina diversas funções pequenas, cada qual com uma tarefa bem determinada.

Este é um problema sobre números inteiros. Não use números reais. Além disso, repare que o programa fica mais simples de escrever se começar por converter para minutos todos os tempos (de entrada e saída).

NOTA - Problema adaptado de "Pedro Guerreiro, Pascal - Técnicas de Programação, Publicações Europa-América, 1988".

Discussão

Para começar, convém reconhecer que este é um problema que se resolve bem usando apenas números inteiros. Não usaremos números reais, pois isso seria complicar sem haver qualquer ganho. Os números reais são entidades mais complexas do que os números inteiros.

Outra questão que se levanta é: em que unidades vamos fazer as contas com tempos? Vamos trabalhar diretamente com tempos em horas e minutos, ou será que devemos converter previamente tudo para minutos? É esta questão de que vamos tratar agora.

Bem, se começarmos a programar uma função para calcular o tempo de permanência usando tempos em horas e minutos veremos que o código começa a ficar assustadoramente complicado e difícil de conceber. Calcular o tempo de permanência usando minutos fica muito mais simples.

Identificámos assim as nossas duas primeiras funções:

Mas neste parque só se pagam horas inteiras. Por isso temos de converter o número de minutos de presença para horas, arredondando para cima. Também é necessária uma função para calcular o valor a pagar com base no número inteiro de horas. Temos assim mais duas funções: Repare que temos estado a procurar escrever funções tão simples quanto possível, e essa simplicidade advém parcialmente dos argumentos das funções já virem no formato que dá "mais jeito" às funções. Repare também que cada uma das nossas funções tem uma tarefa única e bem definida, e que isso contribui para a clareza do programa.

Vamos agora escrever a função que resolve a parte principal do nosso problema, usando as funções anteriores como funções auxiliares. Leia o código e siga o raciocínio:

Repare como se usam variáveis suplementares para se guardarem os resultados produzidos por algumas funções. Os resultados ficam assim disponíveis para poderem ser usados um pouco mais à frente, como argumentos de outras funções.

Agora, complete você mesmo o programa e não se esqueça de escrever a função main.

Oferta:

Testes

Para nos convencermos de que o programa está correto, convém testá-lo bem. Eis um conjunto de testes que considera alguns casos normais e alguns casos de fronteira particulares:

Técnicas de desenvolvimento de programas: top-down e bottom-up

Vamos discutir brevemente duas formas diferentes do programador organizar as suas ideias por forma a conseguir programar problemas não triviais. Cada uma das duas técnicas pode ser usada isoladamente, embora muitas vezes sejam usadas misturadas, dependendo da vontade e da inspiração do programador:

Técnica top-down (técnica de refinamentos sucessivos)

Perante um problema com algum complexidade, podemos abordá-lo de forma controlada e organizada da seguinte forma:

Mesmo que o problema a programar seja complexo e mesmo que o programador tenha dificuldade em abarcar todos os detalhes ao mesmo tempo, este processo sistemático de escrita do programa orienta os esforços do programador que assim não precisa de ficar confuso.

Exemplo

Para exemplificar, vejamos como pode ser atacado o problema do parque de estacionamento usando a técnica top-down. Começamos por tentar escrever a função main. Repare que o código anterior, apesar de incompleto, compila sem erros porque tivémos o cuidado de escrever com corpo vazio a função parque.

Depois escrevemos a função parque, que deve ser expressa à custa de diversas funções mais simples.

Continuaríamos a atuar desta forma até o programa ficar completo. Em cada passo, inventamos novas funções que depois será necessário programar.

Técnica bottom-up (construção da base para o topo)

Perante um problema com algum complexidade, podemos abordá-lo de forma controlada e organizada, usando a estratégia contrária da que foi discutida na secção anterior:

Mesmo que o problema a programar seja complexo e caso o programador tenha dificuldade em abarcar todos os detalhes ao mesmo tempo, este processo sistemático de escrita do programa orienta os esforços do programador que assim não precisa de ficar confuso.

Exemplo

O problema do Parque de Estacionamento foi resolvido no início desta aula usando a estratégia bottom-up. Primeiro foram identificadas as operações mais básicas, e só depois destas estarem decididas (e talvez também testadas) é que se avançou para as funções do nível seguinte.


Reutilização e legibilidade

Como se disse logo no início, muitas vezes estas duas técnicas são usadas misturadas.

Há geralmente a tendência para dar preferência à técnica top-down e não há mal nenhum nisso. Mas convém conhecer uma das principais vantagens da técnica bottom-up:

Assim, quem programa usando a técnica top-down deve tentar compensar e procurar deliberadamente escrever, quando possível, função mais gerais, reutilizáveis noutros programas, portanto funções que não estejam demasiadamente presas ao contexto do programa concreto que se está a escrever.

Um outro detalhe importante. Essas funções gerais e reutilizáveis são geralmente mais legíveis, i.e. mais fáceis de perceber. Funções que não sejam gerais são demasiado específicas e só se percebem levando em conta um complexo contexto de utilização.

O exemplo de programação top-down que foi apresentado no inicio atrás já leva em conta tudo o que se diz aqui. Nesse exemplo houve a preocupação de escrever funções gerais, reutilizáveis e legíveis. Nesse exemplo seguiu-se ainda o nosso conhecido princípio de "escrever uma função diferente para cada problema, e nunca escrever uma função que tente resolver dois problemas ao mesmo tempo".



Busca dicotómica em vetores ordenados

Quem já consultou uma lista telefónica sabe que se consegue encontrar muito mais rapidamente o que se procura tirando partido da ordenação dos elementos. (É assim, um pouco, como a diferença entre 1 minuto ou 15 dias, especialmente se estiver em causa a lista telefónica duma cidade grande como Lisboa.)

A técnica de busca dicotómica permite fazer buscas extremamente rápidas em vetores ordenados. Usa-se um ciclo e, em cada iteração, faz-se o seguinte:

Vamos discutir a operação de busca dicotómica continuando a usar o exemplo da lista telefónica. Para representar uma entrada na lista telefónica vamos usar as seguintes constantes, mais o seguinte tipo:

Busca dicotómica sobre vetores

A seguinte função implementa a operação de busca dicotómica sobre vetores. A função recebe um vetor de entradas lista, o número de entradas n_lista, e o nome a procurar procurar. O resultado da função é o índice da componente do vetor que correspondente ao nome procurado. Se o nome procurado não ocorrer no vetor, então a função retorna o valor -1.

Discussão

A busca dicotómica só funciona com vetores ordenados. Se um vetor não estiver ordenado, a única busca possível é a busca sequencial.

A busca dicotómica é muito mais rápida do que a busca sequencial. Se tivermos uma lista telefónica com 1 milhão de entradas:



Ordenação de vetores

Há mais do que uma razão para se querer ordenar vetores:

A ordenação de vetores foi um tópico muito estudado nos anos 1960 e 1970. Existem diversas estratégias de ordenação conhecidas, mas aqui vamos limitar-nos a uma das estratégias mais populares: a estratégia do bubblesort. Esta é uma das estratégia mais simples de implementar (e de lembrar sempre que é preciso): basta usar dois ciclos for encaixados cujo corpo consiste num if e numa troca de valores.

Critérios de ordenação

Podem ser usados diversos critérios de ordenação, sempre com base nos valores guardados nos vetores. A parte dos valores que é usada nas comparações chama-se chave de ordenação. A ordenação pode ser crescente ou decrescente.

Usando o exemplo da lista telefónica, se quisermos ordenar a lista com base no nome das entradas, esse nome é considerado a chave de ordenação. Se quisermos ordenar a lista com base no número de telefone, esse número de telefone é considerado a chave de ordenação. Qualquer que seja a chave usada na ordenação, a ordenação pode ser crescente ou decrescente.

Técnica Bubblesort

Na estratégia Bubblesort, procede-se da seguinte forma para ordenar um vetor por ordem crescente:

Repare que, a pouco e pouco, os valores maiores vão sendo deslocados para a parte final do vetor, o que faz lembrar bolhas de ar a subir num líquido. É daí que vem o nome desta técnica de ordenação.

Eis um exemplo que apresenta os vários passos da ordenação duma sequência de 5 valores inteiros. A negrito mostra-se a parte da sequência já ordenada.

Ordenação de vetores

Eis uma função de ordenação que ordena uma lista telefónica por ordem crescente de nome:

Animações de variantes do algoritmo Bubblesort



#70