". . . there is a huge difference between programs that merely work
and programs that are well-engineered,
just as there is a huge difference
between a log thrown over a river and a well-engineered bridge."
" . . . there is a huge difference between good
programs and working programs.
A good program not only works, but is easy to read and maintain."
—P. A. Darnell, Ph. E. Margolis,
Software Engineering in C
"Programs must be written for people to read,
and incidentally for machines to execute."
— H. Abelson, G. Sussman,
The Structure and Interpretation of Computer Programs
"Any fool can write code that a computer can understand.
Good programmers write code that humans can understand."
— R. Fowler,
Refactoring: Improving the Design of Existing Code
Suponha que v é um vetor (= array) de inteiros e que a parte relevante do vetor é v[0..n-1]. Nosso problema:
Verificar se um dado inteiro x está em v[0..n-1].
O problema faz sentido para qualquer n ≥ 0. Se n é 0, o vetor é vazio e portanto x não está em v[0..n-1].
| 0 | n-1 | |||||||||||
| 443 | 222 | 555 | 111 | 333 | 444 | 555 | 666 | 888 | 777 | 888 | 999 | |
| x | v | |||||||||||
Eis uma solução iterativa do problema:
/* A função devolve 1 se x está em v[0..n-1] e
* devolve 0 em caso contrário.
******************************/
int verifica (int x, int n, int v[])
{
int j;
j = 0;
while (j < n && v[j] != x)
j += 1;
if (j < n) return 1;
else return 0;
}
Êta solução elegante! Veja como ela funciona bem mesmo quando a parte relevante do vetor está vazia, ou seja, quando n é igual a 0. Eis uma implementação igualmente elegante:
int j;
for (j = 0; j < n; j += 1)
if (v[j] == x) return 1;
return 0;
Em contraste, eis um jeito muito popular mas muito deselegante de fazer a mesma coisa (usa uma variável a mais, sem necessidade):
int achou = 0, j = 0;
while (j < n && achou == 0) { /* deselegante */
if (v[j] == x) achou = 1;
else j += 1;
}
if (achou == 0) return 0;
else return 1;
Eis outra solução popular mas deselegante (o caso especial em que o vetor está vazio é tratado em separado, sem necessidade):
if (n == 0) return 0; /* deselegante */
else {
int j = 0;
while (j < n && v[j] != x)
j += 1;
if (j < n) return 1;
else return 0;
}
(Eu poderia trocar as duas últimas linhas por return (j < n) mas isso não tornaria as coisas melhores.) Mais uma solução muito popular mas deselegante e ineficiente (continua calculando mesmo depois de ter encontrado a resposta):
int j, achei = 0; for (j = 0; j < n; j++) /* ineficiente */ if (v[j] == x) achei = 1; /* deselegante */ return achei;
Também existem "soluções" que parecem razoáveis mas estão simplesmente erradas. No primeiro dos exemplos abaixo, a instrução if (v[j] == x) dá resultados imprevisíveis quando j ≥ n. No segundo exemplo, a ordem das comparações no while está errada: o certo é (j < n && v[j] != x). No terceiro exemplo, a lógica está errada.
int j = 0;
while (j < n && v[j] != x) j += 1;
if (v[j] == x) /* errado! */
return 1;
else return 0;
int j = 0;
while (v[j] != x && j < n) /* errado! */
j += 1;
if (j < n) return 1;
else return 0;
int achei;
for (j = 0; j < n; ++j) {
if (v[j] == x) achei = 1;
else achei = 0; /* errado! */
}
return achei;
Eis uma idéia mais refinada: que tal devolver o índice de uma ocorrência de x em v[0..n-1]? É preciso começar com uma decisão de projeto: que fazer se x não está no vetor? Nossa decisão: devolver -1 nesse caso. Para fazer isso, convém varrer o vetor "de trás pra frente":
/* A função devolve um índice i em 0..n-1 tal que
x == v[i]. Se tal i não existe, devolve -1. */
int onde (int x, int n, int v[])
{
int j;
j = n;
while (j > 0 && v[j-1] != x)
j -= 1;
return j - 1;
}
Que beleza! Curto e limpo! Em contraste, eis uma solução muito popular mas ineficiente e deselegante (usa uma variável a mais e complica a lógica sem necessidade):
int j, k = -1;
for (j = n-1; j >= 0; --j)
if (v[j] == x) k = j; /* deselegante */
return k;
Eis uma versão errada do código (esquece de comparar j com 0):
int j = n-1;
while (v[j] != x) /* errado! */
--j;
return j;
Podemos tomar uma decisão de projeto diferente: devolver n se x não estiver em v[0..n-1]. Nesse caso, faz mais sentido percorrer o vetor da esquerda para a direita:
int j = 0;
while (j < n && v[j] != x)
j += 1;
return j;
A função fica melhor ainda se usarmos uma sentinela para evitar o grande número de comparações de j com n. Para que isso funcione, v deve ter sido declarado com mais que n elementos.
int j = 0;
v[n] = x; /* sentinela */
while (v[j] != x)
j += 1;
return j;
Eis uma solução recursiva do nosso problema de busca:
/* Devolve 1 se x é igual a algum elemento de
v[0..n-1] e devolve 0 em caso contrário. */
int verifica1 (int x, int v[], int n)
{
if (n == 0) return 0;
if (x == v[n-1]) return 1;
return verifica1 (x, v, n-1);
}
Como a coisa funciona? O número de elementos relevantes de v é n. Se n é 0 então v[0..n-1] é vazio e portanto x não está em v[0..n-1]. Agora suponha que n > 0; nesse caso, x está em v[0..n-1] se e somente se
x é igual a v[n-1] ou x está em v[0..n-2].
Eis uma solução recursiva mais suja e deselegante que a anterior, pois coloca o caso n=1 na base da recursão. Ela só funciona se n ≥ 1:
int verifeio (int x, int v[], int n) {
if (n == 1) { /* deselegante */
if (x == v[0]) return 1; /* deselegante */
else return 0;
}
if (x == v[n-1]) return 1;
return verifeio (x, v, n-1);
}
A versão seguinte é ainda pior que a anterior (por que?):
int veripior (int x, int v[], int n) {
if (n == 0) return 0;
else {
int achei;
achei = veripior (x, v, n-1); /* ineficiente */
if (achei || x == v[n-1]) return 1;
else return 0;
}
}
int verifica (int x, int n, int v[]) {
if (v[n-1] == x) return 1;
else return verifica (x, n-1, v);
}
Eis um problema mais geral que o estudado acima. Suponha que queremos verificar se um vetor x[0..m-1] é um segmento de um vetor v[0..n-1]. Exemplo, com m igual a 3 e n igual a 7:
0,172,0 é segmento de 272,165,0,0,172,0,324
mas não é segmento de 272,165,0,0,172,324,0.
Vamos tomar a seguinte decisão de projeto: nossa função devolverá 1 se x é segmento de v e 0 em caso contrário. [Poderíamos ter adotado outras convenções. Por exemplo, devolver j tal que x[0..m-1] é igual a v[j..j+m-1] se tal j existe; caso contrário devolver n.] Eis uma bela solução:
/* Devolve 1 se x[0..m-1] é segmento de v[0..n-1]
* e devolve 0 em caso contrário.
*******************************/
int segmento (int m, int x[], int n, int v[])
{
int i, j;
for (j = 0; j <= n-m; ++j) {
i = 0;
while (i < m && x[i] == v[j+i])
i += 1;
if (i == m) return 1;
}
return 0;
}
Cada execução do while verifica se x[0..m-1] é igual a v[j..j+m-1]; isso é repetido para j = 0,1, . . . ,n-m.
Veja como a coisa funciona bem até mesmo quando m > n. Veja como funciona bem até mesmo quando n vale 0. Note a ordem em que as comparações são feitas no while: teria sido uma péssima idéia escrever while (x[i] == v[j+i] && i < m).
Eis outra versão muito boa. Ao contrário da anterior, ela só tem uma só malha e não duas malhas encaixadas. Veja como esta versão funciona bem até mesmo quando m > n ou n = 0.
int i = 0, j = 0;
while (i < m && j+i < n) {
if (x[i] == v[j+i]) i += 1;
else {
i = 0;
j += 1;
}
}
return i == m;
No início de cada repetição do while temos a seguinte situação: já sabemos que x[0..i-1] é igual a v[j..j+i-1]; se i for igual a m então já temos uma resposta afirmativa; senão, é preciso comparar x[i] com v[j+i].
Agora considere uma versão deselegante e torta. Vários casos especiais são tratados em separado sem necessidade:
int i, j; if (m > n) return 0; /* deselegante */ for (j = 0; j <= n-m; j++) if (x[0] == v[j]) { /* deselegante */ i = 1; while (i < m && x[i] == v[j+i]) i += 1; if (i == m) return 1; } return 0;
Para terminar, eis uma boa solução recursiva. A idéia é simples: se x[0..m-1] é segmento de v[0..n-1] então ou x[0..m-1] é igual a v[n-m..n-1] ou x[0..m-1] é segmento de v[0..n-2].
/* A função segmento1 devolve 1 se x[0..m-1] for
segmento de v[0..n-1] e devolve 0 em caso
contrário. */
int segmento1 (int m, int x[], int n, int v[])
{
if (m > n) return 0;
else {
int i = 0;
while (i < m && x[i] == v[n-m+i])
i += 1;
if (i == m) return 1;
return segmento1 (m, x, n-1, v);
}
}
Para entender uma função recursiva é essencial dizer, de maneira explícita e precisa, o que a função faz.
x[0] = v[s[0]], x[1] = v[s[1]], . . . , x[m-1] = v[s[m-1]]
para algum vetor s[0..m-1] tal que 0 ≤ s[0] < s[1] < . . . < s[m-1] ≤ n-1. Por exemplo, 12,13,10,3 é uma subseqüência de 11,12,13,11,10,9,7,3,3 mas não de 11,12,10,11,13,9,7,3,3.
x[p] == x[p+1] == ... == x[q].
O tamanho de um tal subvetor é q-p+1. Um segmento horizontal é máximo se não existe segmento horizontal de tamanho maior. Escreva uma função que receba um vetor crescente não vazio x[0..n-1] e devolva o tamanho de um segmento horizontal máximo no vetor. Procure escrever uma função simples e limpa.