Esta página é um resumo de
Um elemento máximo de um vetor numérico v[0 .. n-1] é um número x tal que
x = v[i]
para algum i no intervalo 0..n-1 e
x ≥ v[j]
para todo j no intervalo 0..n-1.
Portanto, v[0..n-1] tem um elemento máximo desde que não seja vazio, ou seja, desde que n ≥ 1. É muito fácil calcular um elemento máximo:
// A função max devolve um elemento máximo
// de v[0..n-1]. Ela supõe que n >= 1.
//
int max (int v[], int n) {
int j, x = v[0];
for (j = 1; j < n; ++j)
if (x < v[j])
x = v[j];
return x;
}
Agora examine esta solução recursiva (exercício 5.16 do livro de Sedgewick):
// A função maxr devolve um elemento máximo
// de v[0..n-1]. Ela supõe que n >= 1.
//
int maxr (int v[], int n) {
if (n == 1) return v[0];
else {
int x;
x = maxr(v, n-1);
if (x > v[n-1]) return x;
else return v[n-1];
}
}
Eis uma receita básica para escrever um algoritmo recusivo:
Veja outra maneira recursiva de determinar um elemento
máximo de v[0..n-1].
A função maxr2 é apenas uma embalagem
:
o trabalho pesado é feito pela função recursiva auxiliar:
int maxr2 (int v[], int n) {
return auxiliar(v, 0, n-1);
}
// Recebe v e índices p e r tais que p <= r.
// Devolve um elemento máximo do vetor v[p..r].
//
int auxiliar (int v[], int p, int r) {
if (p == r) return v[p];
else {
int x;
x = auxiliar(v, p + 1, r);
if (v[p] < x) return x;
else return v[p];
}
}
Veja mais uma versão,
desta vez sem função-embalagem
:
// A função maxr3 devolve um elemento máximo
// de v[0..n-1]. Ela supõe que n >= 1.
//
int maxr3 (int *v, int n) {
if (n == 1) return v[0];
else {
int x;
x = maxr3(v + 1, n - 1);
if (v[0] < x) return x;
else return v[0];
}
}
O programa 5.6 de Sedgewick mostra mais uma maneira recursiva de encontrar um máximo de um vetor. Esta solução usa a estratégia da divisão-e-conquista:
// A função maxr4 devolve um elemento máximo
// do vetor v[p..r]. Ela supõe que p <= r.
//
int maxr4 (int v[], int p, int r) {
int u, v;
int m = (p + r)/2;
if (p == r) return v[p];
u = maxr4(v, p, m);
v = maxr4(v, m+1, r);
if (u > v) return u;
else return v;
}
int maximoO (int v[], int p, int r) {
int j, x = INT_MIN;
for (j = p; j <= r; ++j)
if (x < v[j]) x = v[j];
return x; }
int maximo3 (int v[], int p, int r) {
int x;
if (p == r) return v[p];
x = maximo3 (v, p+1, r);
return (x > v[p]) ? x : v[p]; }
int X (int n) {
if (n == 1 || n == 2) return n;
else return X(n-1) + n * X(n-2); }
ao contrário, ou seja, primeiro v[n-1], depois v[n-2] e assim por diante. Para que valores de n o problema faz sentido?
int SeqAditiva (int n, int t0, int t1) {
if (n == 0) return t0;
return SeqAditiva(n-1, t1, t0 + t1); }
Suponha que uma lista encadeada termina com NULL e tem nós do tipo node:
typedef struct node *link;
struct node {
int item;
link next;
};
Eis algumas funções recursivas de manipulação da lista. Duas delas aplicam uma função Visit a cada nó da lista; não importa o que essa função faz, desde que não altere o campo next do nó. Essas funções são uma versão simplificada do Programa 5.5 do livro do Sedgewick.
// A função count devolve o número de nós
// da lista encadeada x. A lista termina
// com NULL.
//
int count(link x) {
if (x == NULL) return 0;
return 1 + count(x->next);
}
// A função traverse percorre a lista
// encadeada h, que termina com NULL. Ela
// aplica a função Visit a cada nó da lista:
// primeiro ao primeiro nó, depois ao
// segundo, etc.
//
void traverse(link h) {
if (h == NULL) return;
Visit(h);
traverse(h->next);
}
// A função traverse percorre a lista
// encadeada h, que termina com NULL. Ela
// aplica a função Visit a cada nó da lista
// EM ORDEM INVERSA: primeiro ao último nó,
// depois ao penúltimo etc.
//
void traverseR(link h) {
if (h == NULL) return;
traverseR(h->next);
Visit(h);
}
// A função delete remove da lista
// encadeada x, que termina com NULL,
// o primeiro nó que tiver item == val.
//
link delete(link x, int val) {
if (x == NULL) return NULL;
if (x->item == val) {
link t = x->next;
free(x);
return t;
}
x->next = delete(x->next, val);
return x;
}
conteúdoda lista. Os nós da lista são definidos por
typedef struct node *link;
struct node {int item; link next;};
Um palíndrome é uma palavra que coincide com sua inversa. Por exemplo, "OSSO" é um palíndrome. A função recursiva abaixo verifica se uma cadeia de caracteres (= string) é palíndrome. Ela foi copiada da Figura 4-4 de Roberts.
typedef enum {FALSE, TRUE} bool;
// Function: IsPalindrome
// Usage: if (IsPalindrome(str) == 1) ...
// --------------------------------------
// This function returns TRUE if the
// character string str is a palindrome.
// (The function is just a wrapper.)
//
bool IsPalindrome (char str[]) {
return CheckPalindrome(srtr, strlen(str));
}
// Function: CheckPalindrome
// Usage: if (IsPalindrome(str, n) == 1) ...
// -----------------------------------------
// This function returns TRUE if the array
// of characters str[0..n-1] is a
// palindrome.
//
bool CheckPalindrome (char str[], int n) {
if (n <= 1) {
return TRUE;
} else {
return (str[0] == str[n-1] &&
CheckPalindrome(str + 1, n-2));
}
Imagine uma linha vertical que representa o intervalo 0..2n. Marque os pontos 0, 1, 2, … , 2n ao longo da linha, de cima para baixo. Agora desenhe traços horizontais a partir dos pontos 1, 2, 3, … , 2n-1 da linha vertical. O traço horizontal no ponto médio do intervalo deve ter comprimento n; os traços nos pontos médios dos subintervalos 0..2n-1 e 2n-1..2n têm comprimento n-1; e assim por diante. Diremos que isso é uma régua de ordem n.
01 -
02 --
03 -
04 ---
05 -
06 --
07 -
08 ----
09 -
10 --
11 -
12 ---
13 -
14 --
15 -
O seguinte programa recursivo desenha uma régua de ordem n. Ele foi copiado do Programa 5.8 de Sedgewick. Também é o exercício 5.11 do livro do Roberts.
// Desenha uma régua de ordem n no intervalo
// 0..2^n. Esta função é apenas uma
// "embalagem".
//
void Rule (int n) {
int i, pot = 1;
for (i = 0; i < n; i++)
pot *= 2;
rule(0, pot, n);
}
// Desenha uma régua de ordem h no intervalo
// p..r.
//
void rule (int p, int r, int h) {
int m = (p + r)/2;
if (h > 0) {
rule(p, m, h-1);
mark(m, h);
rule(m, r, h-1);
}
}
Estamos supondo que o procedimento auxiliar mark(m,h) faz um traço horizontal de comprimento h a partir do ponto m da linha vertical.
000
001
010
011
100
101
110
111
abc acb bac bca cab cbaO programa deve imprimir aquelas permutações que são palavras válidas da língua portuguesa. Use o arquivo br-latin1.txt, que contém todas as palavras da língua portuguesa falada no Brasil. (O arquivo foi gerado por Yoshiharu Kohayakawa a partir do trabalho de Ricardo Ueda.) Minha página sobre algoritmos de enumeração pode ser útil. Veja também o programa 3.17 no livro de Sedgewick.
?se necessário); aplique a permutação a cada segmento. Exemplo: se k = 4 e a chave é 2431 então Mary torna-se yMra e Maryan torna-se yMra?a?n. Escreva uma função que, ao receber cadeias plaintext, cyphertext1 e cyphertext2, encontre um k e uma chave que transforme plaintext em cyphertext1. Em seguida, aplique a chave inversa a cyphertext2.