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 grande problema em partes menores e mais fáceis.

Projeto

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

Codificação e testes

Na codificação você escreve o código do programa. Você usa testes iterativos 迭代测试 — testa pequenas partes repetidamente à medida que as constrói. Nos testes você executa todo o programa 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;
• um fluxograma 流程图 — um diagrama usando caixas e setas para mostrar os passos em ordem;
• pseudocódigo 伪代码 — passos escritos em inglês simples, similar a código (não uma linguagem real).

Um algoritmo 算法 é um conjunto de passos, 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 nos dados;
• saída 输出 — o resultado que sai.

Isso é chamado de decomposição em entradas, processos e saídas. Por exemplo, para "encontrar a média de três notas": as entradas são as três notas; o processamento é 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. Ela não pode verificar se os dados são verdadeiros, apenas se são permitidos.

Verification 核实 verifica que os dados foram copiados ou inseridos corretamente (sem erros ao digitar). Dois métodos:

• visual check 目视检查 — uma pessoa compara os dados digitados com o original;
• double entry 双重输入 — os dados são inseridos duas vezes e as duas cópias são comparadas.

Uma trace table 追踪表 registra o valor de cada variável conforme 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.

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

Você deve conhecer esses algoritmos comuns.

Busca linear

Uma busca linear 线性查找 verifica cada item de uma lista, um por um, até encontrar o valor desejado ou chegar ao final.

Found ← FALSE
FOR I ← 0 TO 9
    IF List[I] = SearchValue
      THEN
        Found ← TRUE
    ENDIF
NEXT I
OUTPUT Found

Bubble sort (Ordenação por bolha)

Um bubble sort 冒泡排序 coloca uma lista em ordem. Ele compara cada par de itens adjacentes e os troca se estiverem na ordem errada. Isso se repete até que nenhuma mais troca seja necessária.

FOR I ← 0 TO 8
    IF List[I] > List[I + 1]
      THEN
        Temp ← List[I]
        List[I] ← List[I + 1]
        List[I + 1] ← Temp
    ENDIF
NEXT I

Somatório e contagem

• totalling 求和 — continuar somando valores a um total acumulado (Total ← Total + Value).
• counting 计数 — adicionar 1 a um contador cada vez que algo acontece (Count ← Count + 1).

Maximum, minimum and average

• para encontrar o maximum 最大值: manter o maior valor visto até agora.
• para encontrar o minimum 最小值: manter o menor valor visto até agora.
• para encontrar o average 平均值: dividir o total pela quantidade de valores.

Total ← 0
FOR I ← 0 TO 9
    Total ← Total + List[I]
NEXT I
Average ← Total / 10
OUTPUT Average

• Aprenda as quatro etapas do ciclo de vida: análise → design → codificação → teste. Abstraction mantém apenas os detalhes importantes; decomposition divide um problema em partes menores.
• Validação 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), abnormal (rejeitado), extreme (os maiores/menores ainda permitidos), boundary (os valores de ambos os lados de um limite).
• Para descobrir o que um algoritmo faz, preencha uma trace table — anote o valor de cada variável em cada etapa.
• Conheça os algoritmos padrão: busca linear (verifique cada item em sequência) e bubble sort (troque pares adjacentes até que nenhuma troca seja necessária).