Especificar um problema: entrada, saída e passos
Antes de escrever qualquer código, descreva o problema com exatidão. Isso é a especificação.
- Entrada: que dados recebemos, seu tipo e seus limites (por exemplo, "n números inteiros, 1 ≤ n ≤ 1000").
- Saída: o que devemos devolver (por exemplo, "o maior deles").
- Condições: o que é verdade antes (pré-condição) e depois (pós-condição).
Escrever os passos
Um algoritmo é uma lista finita de passos claros que transforma qualquer entrada válida na saída certa. Escreva-o como:
- linguagem natural: "Olhe cada número; se for maior que o melhor até agora, guarde-o."
- uma lista numerada de passos: 1. melhor ← primeiro número. 2. Para cada número seguinte x: se x > melhor, então melhor ← x. 3. Mostre melhor.
- pseudocódigo ou fluxograma, para mais precisão.
Teste à mão com entradas pequenas, inclusive as difíceis (todos iguais, números negativos, um único número).
Projeto top-down e bottom-up
Top-down (de cima para baixo, refinamento por etapas): comece com a tarefa inteira, divida-a em poucos passos grandes e divida cada passo de novo, até que cada parte seja fácil de programar. Exemplo: "Fazer um boletim" → ler as notas → calcular as médias → dar os conceitos → imprimir.
Bottom-up (de baixo para cima): construa e teste primeiro peças pequenas e reutilizáveis (uma função que acha o máximo, outra que ordena) e depois junte tudo no programa completo.
Projetos reais misturam os dois: planeje de cima para baixo, construa e teste de baixo para cima.
Dividir e conquistar e o método da divisão ao meio
Dividir e conquistar tem três movimentos: dividir o problema em partes menores do mesmo tipo, resolver cada parte (muitas vezes por recursão) e combinar as respostas.
- Busca binária (divisão ao meio): numa lista ordenada, compare com o elemento do meio e jogue metade fora. n itens precisam de cerca de log₂ n verificações: 16 → 4, 1 000 000 → 20.
- Merge sort: divida a lista em duas, ordene cada metade e junte as duas: O(n log n).
- Potência rápida: a⁸ = ((a²)²)²: 3 multiplicações em vez de 7.
- Achar uma raiz por bisseção: divida ao meio um intervalo em que a função muda de sinal.
Algoritmos gulosos
Um algoritmo guloso faz a escolha que parece melhor agora e nunca a muda.
- Dar troco com 50, 20, 10, 5, 2, 1: a maior moeda primeiro. É ótimo para esse tipo de sistema de moedas.
- Escolher o maior número de atividades num dia: pegue sempre a que termina mais cedo. É ótimo.
- Mochila fracionária: leve primeiro os itens com o melhor valor por kg. É ótimo.
Mas o guloso nem sempre acerta: com moedas 1, 3, 4, pagar 6 de forma gulosa dá 4 + 1 + 1 (3 moedas), enquanto 3 + 3 usa 2. Para confiar num método guloso, você precisa prová-lo ou testá-lo contra um método seguro.
Programação dinâmica e backtracking
Programação dinâmica (PD)
Quando os mesmos problemas menores se repetem, resolva cada um uma só vez e guarde a resposta numa tabela. Menor número de moedas para o valor a: best[a] = 1 + min(best[a - c]) sobre as moedas c ≤ a, começando com best[0] = 0. Para as moedas 1, 3, 4: best = 0, 1, 2, 1, 1, 2, 2. Preencher a tabela do pequeno para o grande é bottom-up; a recursão com memória é top-down (memoização). Veja a lição separada de Programação dinâmica para saber mais.
Backtracking
Monte uma solução uma escolha por vez. Se uma escolha quebra uma regra ou leva a um beco sem saída, desfaça-a e tente a próxima opção. É usado em labirintos, Sudoku, no problema das N rainhas e para listar todos os subconjuntos. É uma força bruta cuidadosa: pula ramos inteiros que não podem funcionar.
Força bruta
Teste todas as respostas possíveis. Está sempre correta, mas muitas vezes é lenta demais (2ⁿ subconjuntos, n! ordens).
Escolher uma técnica: correção, eficiência e estruturas de dados
| Técnica | Use quando | Exemplo | Tempo típico |
|---|---|---|---|
| Força bruta | a entrada é minúscula | testar todas as senhas de 3 dígitos | muitas vezes 2ⁿ ou n! |
| Dividir e conquistar | as partes são independentes | busca binária, merge sort | O(log n), O(n log n) |
| Guloso | uma boa escolha local é comprovadamente segura | seleção de atividades, troco | O(n log n) |
| Programação dinâmica | os subproblemas se repetem | troco, caminhos mais curtos | tamanho da tabela |
| Backtracking | busca com regras | labirinto, Sudoku | exponencial, mas com poda |
Justifique
Correção: mostre que o algoritmo sempre para e dá a saída certa (um invariante de laço, uma prova ou testes em casos extremos). Eficiência: conte os passos conforme n cresce (notação O) e compare com outros métodos.
As estruturas de dados ajudam
Vetores para tabelas (PD), pilhas para backtracking (lembrar para onde voltar), filas para busca nível por nível. Uma árvore binária guarda itens de modo que cada nó tem no máximo dois filhos; numa árvore binária de busca, as chaves menores vão para a esquerda e as maiores para a direita, então a busca corta o trabalho pela metade a cada nível, como na busca binária.
Experimente: moedas e um jogo de adivinhação
- Jogue o jogo de adivinhar de 1 a 100 com um amigo. Pergunte sempre pelo meio. Você sempre consegue ganhar em 7 perguntas? (2⁷ = 128.)
- Com as moedas 1, 3, 4, escreva no papel a tabela de PD para os valores de 0 a 10. Onde o guloso falha?
- Abra o último passo em 3D. Teste as moedas 1, 7, 10 e o valor 14. O guloso dá 10 + 1 + 1 + 1 + 1; a PD dá 7 + 7.
- Escreva uma lista de passos para "achar o menor número de uma lista" e teste com 5, 5, 5 e com um único número.
Fórmulas e definições principais
- Especificação = entrada + saída + condições
- Divisão ao meio: cerca de log₂ n passos (16 → 4, 1024 → 10)
- PD do troco: best[0] = 0; best[a] = 1 + min best[a - c]
- Dividir e conquistar = dividir + resolver + combinar
- O guloso é rápido, mas é preciso provar que é ótimo
Exemplos resolvidos
1. Escreva uma especificação e uma lista de passos para achar o maior de n números.
Entrada: n ≥ 1 números. Saída: o maior. Passos: 1. melhor ← primeiro número. 2. Para cada outro número x: se x > melhor, melhor ← x. 3. Mostre melhor. Para 4, 9, 2, 7, 12, 5, 10, 3 a saída é 12, depois de 7 comparações.
2. Quantas perguntas a divisão ao meio precisa para achar um número de 1 a 1000?
Cada pergunta divide o intervalo ao meio: 1000 → 500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1. São 10 perguntas (2¹⁰ = 1024 ≥ 1000).
3. Pague 87 de forma gulosa com as moedas 50, 20, 10, 5, 2, 1.
50 (restam 37), 20 (17), 10 (7), 5 (2), 2 (0): 50 + 20 + 10 + 5 + 2 = 5 moedas.
4. Preencha a tabela de PD para as moedas 1, 3, 4 até o valor 7.
best[0]=0, [1]=1, [2]=2, [3]=1, [4]=1, [5]=min(best4, best2, best1)+1=2, [6]=min(best5, best3, best2)+1=2, [7]=min(best6, best4, best3)+1=2 (3 + 4).
5. Atividades (início-fim): A 9-11, B 10-12, C 11-13, D 12-14, E 13-15. Escolha o maior número de atividades que não se sobrepõem.
Guloso pelo término mais cedo: A (termina às 11), depois C (começa às 11, termina às 13), depois E (começa às 13). 3 atividades: A, C, E.
6. Planeje de cima para baixo: um programa que diz à turma a nota média e o melhor aluno.
Nível 1: ler os dados → calcular → imprimir. Nível 2: ler nomes e notas em listas; calcular o total e a média; achar a maior nota e o nome dela; imprimir os dois. Depois cada parte é programada e testada de baixo para cima.
Erros comuns
- Começar a programar antes de dizer qual é a entrada e qual é a saída. Muitos "bugs" são, na verdade, uma especificação pouco clara.
- Achar que o guloso é sempre ótimo. Ele só funciona quando você consegue prová-lo (as moedas 1, 3, 4 o derrubam).
- Usar busca binária numa lista não ordenada. Dividir ao meio exige dados ordenados.
- Confundir PD com dividir e conquistar. A PD serve para subproblemas que se sobrepõem e são guardados; dividir e conquistar separa em partes independentes.