E25.1 Veja a subsequência de 1..9 abaixo. Dê a subsequência seguinte na ordem lexicográfica. Explique como você obteve a resposta.
1 3 4 6 7 9
E25.2 Subset Sum. O código abaixo enumera as subsequências não vazias de 1..n. Modifique o código de modo que ele resolva o seguinte problema: Dado um número t e um vetor v[1..n] de números (não necessariamente todos positivos), encontrar todas as subsequências não vazias subs[1..k] de 1..n tais que v[subs[1]] + … + v[subs[k]] == t .
void subseqLex (int n) {
int *subs, k;
subs = malloc ((n+1) * sizeof (int));
subs[k=0] = 0;
while (1) {
if (subs[k] < n) {
subs[k+1] = subs[k] + 1;
k++;
} else {
subs[k-1] += 1;
k--;
}
if (k == 0) break;
imprima (subs, k);
}
free (subs);
}
E25.3 Veja a permutação de 1..6 abaixo. Dê a permutação seguinte na ordem lexicográfica. Explique como você obteve essa permutação.
6 5 2 1 4 3
E25.4 O seguinte algoritmo enumera as permutações de 1..n. Considere o caso n = 5 e mostre perm[1..k] e m no início de cada uma das 7 primeiras iterações.
void permutacoes (int n) {
int k, m;
int *perm = malloc ((n+1) * sizeof (int));
for (k = 1; k <= n; k++) perm[k] = k;
k = n;
m = n+1;
while (1) {
if (k >= n) {
imprime (perm, n);
m = n+1;
}
while (m <= n && !pode (perm, k, m))
m++;
if (m <= n) {
perm[k+1] = m;
m = 1;
k++;
} else {
if (k < 1) break;
m = perm[k] + 1;
k--;
}
}
free (perm);
}
int pode (int *perm, int k, int m) {
int i;
for (i = 1; i <= k; ++i)
if (m == perm[i])
return 0;
return 1;
}
E25.5 Rainhas. Problema: como colocar n rainhas num tabuleiro de xadrez n-por-n de modo que elas não se ataquem? Modifique o algoritmo que enumera as permutações de 1..n (veja a questão E25.4) de modo que ele enumere as soluções do problema das rainhas.