E24.1 (Repetição de 22.4) Escreva uma função que transforme um vetor crescente em uma árvore de busca que seja balanceada.
E24.2 (Repetição de 22.5) Escreva uma função que transforme uma árvore de busca em um vetor crescente. Suponha que as chaves são do tipo int. Comece por alocar dinamicamente o vetor.
E24.3 Subset Sum. Suponha que você emitiu cheques nos valores v[1], … , v[n] ao longo de um mês. No fim do mês, o banco informa que um total t foi debitado em sua conta. Quais dos cheques foram descontados? Por exemplo, se v é 61 62 63 64 e t = 125 então só há duas possibilidades: ou foram debitados os cheques 1 e 4 ou foram debitados os cheques 2 e 3.
Essa é uma instância do problema da soma de subconjunto
,
mais conhecido como subset sum:
Dado um número t e um vetor
v[1..n] de números (não necessariamente inteiros positivos),
encontrar todas as subsequências
s[1..k] de 1..n tais que
v[s[1]] + … + v[s[k]]
= t .
Escreva uma função que resolva o problema.
E24.4 Permutações. Uma permutação da sequência 1..n é qualquer rearranjo dessa sequência. Por exemplo, as 6 permutações de 1 2 3 são 1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2, 3 2 1. Escreva uma função que imprima, exatamente uma vez, cada uma das n! permutações de 1..n.
E24.5 Problema das rainhas. É possível colocar 8 rainhas do jogo de xadrez sobre o tabuleiro de modo que nenhuma das rainhas possa atacar outra? Generalize o problema para tabuleiros n×n.
E24.6 Passeio do cavalo. Suponha dado um tabuleiro de xadrez n-por-n . Determine se é possível que um cavalo do jogo de xadrez parta da posição (1,1) do tabuleiro e complete um passeio por todas as n×n posições do tabuleiro em n×n - 1 passos válidos. Por exemplo, para um tabuleiro 5-por-5 uma solução do problema é
1 6 15 10 21
14 9 20 5 16
19 2 7 22 11
8 13 24 17 4
25 18 3 12 23
Sugestão: Numere as casas do tabuleiro da maneira óbvia (a primeira linha da esquerda para a direita, depois a segunda linha etc.). Agora examine todas as permutações de 1 2 … n2. Para cada permutação, verifique se ela representa um passeio válido.