E27.1 Subset sum para 2 elementos. Problema: dados um vetor v[1..n] de números inteiros e um número inteiros t, decidir se existem dois índices distintos i e j tais que v[i] + v[j] == t. Escreva um algoritmo eficiente que resolva o problema.
E27.2 Subsequências de strings. Escreva uma função que receba uma string e imprima todas as subsequências não vazias da string. Por exemplo, as subsequências não vazias de "ABC" são
A B C AB AC BC ABC
E27.3 Subsequência crescente máxima. Uma subvetor (ou subsequência) de um vetor v é o que sobra depois que alguns dos elementos de v são apagados. Escreva uma função que determine um subvetor crescente máximo (ou seja, de comprimento máximo) de um vetor v[0..n-1].
E27.4
Fila de prioridade e árvore binária.
Digamos
que uma árvore hp
é uma árvore binária quase completa
com a seguinte propriedade:
x->chave ≥ x->esq->chave
e
x->chave ≥ x->dir->chave
para todo nó x,
desde que os filhos existam.
Escreva uma implementação de fila de prioridade
baseada em árvore hp.
A implementação deve ter funções
para as seguintes tarefas:
criar uma fila vazia,
retirar um elemento máximo da fila,
inserir um elemento na fila.
Os nós da árvore devem ter a seguinte estrutura:
struct cel {
int chave;
struct cel *pai, *esq, *dir;
};
typedef struct cel noh;