Projeto de algoritmos e resolução de problemas

O ciclo de vida do desenvolvimento de programas é o conjunto de etapas usadas para criar um programa. Existem quatro etapas.

Análise

Na análise você entende o problema. Duas habilidades-chave ajudam:

• abstração — manter apenas os detalhes importantes e ignorar o resto;
• decomposição — dividir um problema grande em partes menores e mais fáceis.

Projeto

No projeto, você planeja a solução, frequentemente usando decomposição. Pode mostrar as partes como sub-sistemas em um diagrama estrutural (um gráfico que divide um sistema em caixas menores).

Exemplo resolvido. Um estacionamento tem uma máquina de pagamento. O motorista digita a placa do carro, a máquina calcula quanto tempo o carro ficou estacionado e o valor a pagar, o motorista paga em dinheiro ou cartão, e um recibo é impresso. Desenhe um diagrama de estrutura.

O sistema inteiro fica na caixa superior. Cada caixa no nível seguinte representa uma tarefa realizada pelo sistema, e uma caixa pode ser dividida novamente (o pagamento divide-se em dinheiro e cartão). Leia cada nível da esquerda para a direita, na ordem em que as tarefas acontecem. Um diagrama de estrutura mostra as partes, não a ordem das decisões ou dos laços: para isso, usa-se um fluxograma ou pseudocódigo.

Codificação e testes

Na codificação, você escreve o código do programa. Usa testes iterativos — testa pequenas partes repetidamente à medida que as constrói. Nos testes, executa o programa inteiro com dados de teste para verificar se funciona.

Você pode planejar uma solução de três maneiras principais.

• um diagrama estrutural — mostra as partes de um sistema e como elas se encaixam;
• fluxograma — um diagrama usando caixas e setas para mostrar as etapas em ordem;
• pseudocódigo — passos escritos em inglês simples semelhante a código (não uma linguagem real).

Um algoritmo é um conjunto de etapas, na ordem correta, que resolve um problema. Todo algoritmo pode ser dividido em três partes:

• entrada — os dados que entram;
• processamento — o trabalho realizado sobre os dados;
• saída — o resultado que sai.

Isso se chama decomposição em entradas, processos e saídas. Por exemplo, para “calcular a média de três notas”: as entradas são as três notas; o processamento consiste em somá-las e dividir por 3; a saída é a média.

Quando os dados são inseridos, você os verifica para reduzir erros.

Validação verifica se os dados são razoáveis e seguem as regras. Não pode verificar se os dados são verdadeiros, apenas se são permitidos.

Verificação confirma que os dados foram copiados ou inseridos corretamente (sem erros de digitação). Dois métodos:

• verificação visual — uma pessoa compara os dados digitados com o original;
• entrada dupla — os dados são inseridos duas vezes e as duas cópias são comparadas.

Como escrever uma rotina de validação

Uma prova frequentemente pede que você escreva o código de uma verificação. Use um laço que solicite a entrada novamente até que ela seja aceitável e apresente uma mensagem ao usuário quando não for.

Exemplo resolvido. Escreva um pseudocódigo para receber uma nota de prova, que deve ser um número inteiro de 0 a 100 (uma verificação de intervalo), e continuar solicitando a entrada até que uma nota válida seja inserida.

DECLARE Mark : INTEGER
REPEAT
    OUTPUT "Enter a mark from 0 to 100"
    INPUT Mark
    IF Mark < 0 OR Mark > 100
      THEN
        OUTPUT "Invalid: the mark must be from 0 to 100"
    ENDIF
UNTIL Mark >= 0 AND Mark <= 100

A condição UNTIL é o intervalo aceito, e a condição IF é o seu oposto. Observe OR em IF: uma nota não pode ser menor que 0 e maior que 100 ao mesmo tempo, então AND nessa posição nunca seria verdadeiro.

Outras verificações seguem o mesmo padrão, com uma condição diferente:

Uma verificação de tipo geralmente é feita pela própria linguagem, por exemplo, quando uma entrada é armazenada em uma variável do tipo INTEGER.

Uma tabela de traçagem registra o valor de cada variável à medida que um algoritmo é executado, passo a passo. Ela ajuda você a:

• verificar se um algoritmo funciona corretamente;
• descobrir o que um algoritmo faz seguindo-o com dados fornecidos.

Exemplo: faça a traça deste algoritmo com a entrada 5.

INPUT N
Total ← 0
FOR I ← 1 TO N
    Total ← Total + I
NEXT I
OUTPUT Total

A traça mostra que o algoritmo soma de 1 até n. Com entrada 5, a saída é 15.

Worked example. Faça a traça deste algoritmo e dê a saída.

X ← 20
Count ← 0
WHILE X > 1
    X ← DIV(X, 2)
    Count ← Count + 1
ENDWHILE
OUTPUT Count

DIV retorna apenas a parte inteira de uma divisão. Faça uma linha por passagem: x torna-se 10 (count 1), depois 5 (count 2), depois 2 (count 3), depois 1 (count 4). Agora x > 1 é falso, então o loop para e a saída é 4. Dois hábitos protegem essas marcas: teste a condição antes de cada passagem em vez de depois, e escreva uma nova linha para cada passagem — tentar guardar os valores na cabeça é o que causa erros nas traces.

Como encontrar e corrigir erros

Uma questão comum apresenta um algoritmo com erros e pede que você os encontre e corrija. Leia-o linha por linha e pergunte: toda variável recebe um valor inicial? Cada laço tem a duração correta? Cada comparação está no sentido correto? A saída está no lugar certo?

Exemplo resolvido. Este algoritmo deve receber 10 números e apresentar o maior. Encontre os três erros e corrija-os.

Largest ← 1000
FOR Count ← 1 TO 9
    INPUT Number
    IF Number < Largest
      THEN
        Largest ← Number
    ENDIF
    OUTPUT Largest
NEXT Count

• Linha 1: Largest ← 1000 começa com um valor alto demais, então nenhum número o substituiria. Correção: Largest ← -1000 (ou receba o primeiro número e use-o como valor inicial).
• Linha 2: o laço é executado apenas 9 vezes. Correção: FOR Count ← 1 TO 10.
• Linha 4: < encontra o menor valor. Correção: IF Number > Largest.

Também há um problema com OUTPUT: dentro do laço, ele imprime o maior valor até aquele momento após cada entrada. Movê-lo para depois de NEXT Count faz com que apenas a resposta final seja impressa. Para cada erro, indique a linha, diga o que está errado e escreva a linha corrigida por completo.

Test data são dados usados para testar um programa. Existem quatro tipos que você deve saber.

Exemplo resolvido. Um programa aceita o número de pessoas que reservam uma mesa, de 1 a 12. Forneça dados de teste de cada tipo, com o resultado esperado.

Sempre forneça o resultado esperado com os dados: um teste só é útil se você souber o que deve acontecer. Um dado extremo é o próprio valor do limite; dados de limite formam um par, com um valor de cada lado do limite.

Você deve conhecer esses algoritmos comuns.

Busca linear

Uma busca linear compara cada item com o alvo, começando pelo início. Pare quando o valor for encontrado ou a lista terminar. A lista não precisa estar ordenada. O exemplo abaixo usa posições 1 a 4.

DECLARE List : ARRAY[1:4] OF INTEGER
DECLARE I, SearchValue : INTEGER
DECLARE Found : BOOLEAN
List[1] ← 8
List[2] ← 3
List[3] ← 5
List[4] ← 1
INPUT SearchValue
Found ← FALSE
I ← 1
WHILE I <= 4 AND NOT Found
    IF List[I] = SearchValue
      THEN
        Found ← TRUE
    ENDIF
    I ← I + 1
ENDWHILE
OUTPUT Found

Exemplo resolvido. Buscar 5 compara 8, 3 e depois 5: três comparações, com Found tornando-se TRUE. O quarto item não é verificado. Buscar 9 compara todos os quatro valores; Found permanece FALSE. Pare antes de tentar ler a posição 5, que está fora deste array.

Bubble sort (Ordenação por bolha)

Uma ordenação de bolha coloca uma lista em ordem. Compare valores vizinhos e troque-os se o valor da esquerda for maior. Uma única passagem geralmente não é suficiente. Esta versão completa repete passagens até que uma inteira não realize nenhuma troca.

DECLARE List : ARRAY[1:4] OF INTEGER
DECLARE I, Temp : INTEGER
DECLARE Swapped : BOOLEAN
List[1] ← 8
List[2] ← 3
List[3] ← 5
List[4] ← 1
REPEAT
    Swapped ← FALSE
    FOR I ← 1 TO 3
        IF List[I] > List[I + 1]
          THEN
            Temp ← List[I]
            List[I] ← List[I + 1]
            List[I + 1] ← Temp
            Swapped ← TRUE
        ENDIF
    NEXT I
UNTIL NOT Swapped
OUTPUT List[1], ", ", List[2], ", ", List[3], ", ", List[4]

Passagens exemplificadas. Comece com 8, 3, 5, 1. Na primeira passagem, a lista torna-se 3, 8, 5, 1, depois 3, 5, 8, 1, então 3, 5, 1, 8. Isso posiciona o maior valor no final, mas deixa o restante desordenado. A segunda passagem termina em 3, 1, 5, 8; a terceira em 1, 3, 5, 8. A quarta não realiza trocas e confirma que esta versão pode parar. Reinitialize Swapped para FALSE no início de cada passagem; defina-o como TRUE em qualquer troca.

Totalling and counting

Somatório adiciona cada valor necessário a um total acumulado: Total ← Total + Value. Contagem adiciona 1 para cada item necessário: Count ← Count + 1. Inicialize ambos como zero antes de processar os valores.

Exemplo resolvido. Quatro tentativas de entrada são −20, 4, 50 e 6. Aceite um valor apenas se for maior que −20 e menor que 50. Este exemplo processa quatro tentativas, não quatro valores aceitos.

DECLARE I, Count : INTEGER
DECLARE Value, Total : REAL
Total ← 0
Count ← 0
FOR I ← 1 TO 4
    INPUT Value
    IF Value > -20 AND Value < 50
      THEN
        Total ← Total + Value
        Count ← Count + 1
    ENDIF
NEXT I
IF Count > 0
  THEN
    OUTPUT Total, ", ", Count, ", ", Total / Count
  ELSE
    OUTPUT "No accepted values"
ENDIF

Os limites estritos rejeitam −20 e 50. Ambas as atualizações pertencem ao teste de aceitação, portanto tentativas rejeitadas não alteram nem o total nem o contador. A média dos valores aceitos é:

Não divida por quatro: apenas dois valores foram adicionados. Se nenhum valor for aceito, o contador será zero e uma média não pode ser calculada; exiba uma mensagem em vez de dividir por zero.

Transferir para um número fixo de valores aceitos. Se a tarefa solicitar 50 valores aceitos, em vez de quatro tentativas, substitua o loop fixo FOR por WHILE Count < 50 e feche-o com ENDWHILE. Mantenha a mesma entrada e teste de aceitação dentro dele. Entradas rejeitadas mantêm Count inalterado, solicitando outra entrada. Ao completar, Count será 50, embora o número de tentativas possa ser maior. Exiba o total e calcule a média como Total / Count.

Maximum, minimum and average

O máximo é o maior valor e o mínimo é o menor. A média é o total dividido pelo número de valores. Para uma lista não vazia, inicialize ambos a partir do primeiro item. Para cada item restante, substitua o máximo se o novo valor for maior, e substitua o mínimo se for menor.

Exemplo resolvido. A lista é −8, −3, −12, −5. Iniciar o máximo em zero falharia: nenhum item da lista é maior que zero, então o algoritmo exibiria um número que não está na lista. Iniciar de −8 funciona sem assumir que os dados são positivos.

DECLARE List : ARRAY[1:4] OF INTEGER
DECLARE I, Maximum, Minimum, Total : INTEGER
List[1] ← -8
List[2] ← -3
List[3] ← -12
List[4] ← -5
Maximum ← List[1]
Minimum ← List[1]
Total ← List[1]
FOR I ← 2 TO 4
    IF List[I] > Maximum
      THEN
        Maximum ← List[I]
    ENDIF
    IF List[I] < Minimum
      THEN
        Minimum ← List[I]
    ENDIF
    Total ← Total + List[I]
NEXT I
OUTPUT Maximum, ", ", Minimum, ", ", Total / 4

O máximo é −3 e o mínimo é −12. A média usa todos os quatro valores:

A média fica entre o mínimo e o máximo; esta é uma verificação útil, não prova de que o cálculo está correto. Inicializar a partir do primeiro item exige uma lista não vazia. Trate uma lista vazia separadamente antes de tentar ler esse item.

• As quatro etapas do ciclo de vida: análise → projeto → codificação → teste. Abstração mantém apenas o essencial; decomposição divide um problema em partes.
• Validation verifica se os dados são sensatos (verificações de faixa, comprimento, tipo, presença, formato); verification verifica se foram copiados corretamente (uma verificação visual ou entrada dupla).
• Aprenda os quatro tipos de dados de teste: normal (aceito), anormal (rejeitado), extremo (o maior/menor ainda permitido), limite (ambos os lados de um limite).
• Uma tabela de traçagem (valor de cada variável em cada etapa) mostra o que um algoritmo faz.
• Para escrever uma rotina de validação, coloque a entrada em um laço REPEAT … UNTIL cuja condição UNTIL corresponda aos dados válidos.
• Ao corrigir um erro, cite a linha e escreva toda a linha corrigida.
• Conheça os algoritmos padrão: linear search (verifique cada item em sequência) e bubble sort (troque pares adjacentes até que nenhuma troca seja necessária).