PAA - Listas de exercícios de 2006.1 (prof. Poggi)

Lista Livre 1 (paa061-ll1.pdf)

Exercícios 1 e 2

Foram resolvidos em sala.

Exercício 3

Ele ainda não falou nada sobre polinomial x pseudopolinomial.

Exercício 4

A descrição aqui estava errada! Para uma resolução correta, ver a resolução do exercício 19 da primeira lista de 2007.1

Exercício 5

Ainda estou matutando sobre esse. Não sou muito bom em provas, então fica complicado.

Lista de revisão para a primeira prova

Essa lista foi fornecida pelo David Sotelo, acho que ela não está no site.

Exercício 1

Resolvido em sala.

Exercício 2

(Cormen, capítulo de estatísticas de ordem)
Basta comparar de dois em dois elementos e, para cada par, descobrir o maior/menor entre eles e então comparar com o maior/menor global. Como temos n elementos e, para cada dois elementos fazemos 3 comparações, ficamos com comparações no total.

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;
 
const int NUM = 10;
 
pair<int,int> MaxMin(int a, int b) {
        if (a > b) return make_pair(b,a);
        else return make_pair(a,b);
}
 
int main() {
    // cria e popula um vetor com numeros aleatorios
        vector<int> v(NUM);
        srand(time(0));
        for (int i=0;i<NUM;i++) v[i] = rand() % (1<<20);
 
        pair<int,int> maioremenor = MaxMin(v[0],v[1]);
        int maximo = maioremenor.second, minimo = maioremenor.first;
        for (int i=2;i<NUM;i+=2) {
                maioremenor = MaxMin(v[i],v[i+1]); // 1
                minimo = min(minimo,maioremenor.first); // 2
                maximo = max(maximo,maioremenor.second); // 3 comparacoes
        }
        cout << minimo << " " << maximo << endl;
}

Exercício 3

Esse ainda não consegui fazer. Alguém tem alguma idéia?

Exercício 4

Esse eu nem entendi direito. Vou mandar um e-mail para tirar algumas dúvidas.

Exercício 5

Na verdade, retirando toda a história bonitinha, o que a questão pede é que seja encontrado o MMC entre dois números em tempo - é só reler com cuidado e perceber que o próximo ano que o eclipse vai acontecer é o menor múltiplo dos dois números. Uma maneira fácil de encontrar o MMC entre dois números é fazendo:

(1)

A multiplicação e a divisão são feitas em , o problema é fazer o MDC. Usando o (famoso) algoritmo de Euclides, temos complexidade onde n é o número de dígitos do número, o que equivale ao logaritmo do número em si na base original. Logo, temos um algoritmo :

#include <iostream>
 
using namespace std;
 
int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
}
 
int main() {
        int a, b;
        cin >> a >> b;
        cout << (a*b)/gcd(a,b) << endl;
        return 0;
}

Exercício 6

A idéia é manter alguma estrutura de dados que dê, a cada passo (no total de n passos), o elemento que deve ser inserido naquele passo na lista final - o menor elemento - em tempo . Uma estrutura possível para fazer isso é um heap, outra é uma árvore binária de busca balanceada. O algoritmo é simples: colocamos os primeiros elementos de cada lista na estrutura de dados e, a cada passo, retiramos o menor valor da estrutura e inserimos o próximo elemento da lista que forneceu o menor valor. A implementação a seguir é em C++, se você não conhece STL pode ficar um pouco confuso. Usei um multimap para manter a ordenação e permitir também guardar um índice para qual lista forneceu aquele valor.

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <map>
#include <ctime>
#include <cstdlib>
 
using namespace std;
 
int main() {
        int m, k; // m -> tamanho de cada lista pequena, k -> numero de listas pequenas
        cin >> m >> k;
 
        // cria um vetor de K listas
        vector< list<int> > listas(k);
        // popula cada lista com M elementos aleatorios
        srand(time(0));
        for (int i=0;i<k;i++) for (int j=0;j<m;j++)
                listas[i].push_back( rand() % (1<<20) );
        // ordena cada lista
        for (int i=0;i<k;i++) listas[i].sort();
 
        // imprime as listas
        for (int i=0;i<k;i++) {
                cout << "lista[" << i << "] ->";
                for(list<int>::iterator it = listas[i].begin(); it != listas[i].end(); it++) {
                        cout << " " << *it;
                }
                cout << endl;
        }
 
        // ---> aqui comeca o algoritmo pedido <---
 
        // ABB que vai manter os menores elementos a cada instante mapeados em qual lista eles foram retirados
        multimap<int,int> menores;
 
        // coloca os primeiros elementos de cada lista no ABB e os remove da lista
        for (int i=0;i<k;i++) {
                menores.insert( pair<int,int>(*listas[i].begin(),i) );
                listas[i].erase( listas[i].begin() );
        }
 
        list<int> listaFinal;
        // para cada um dos M*K elementos que serao inseridos na lista final
        for (int i=0;i<m*k;i++) {
                // retira o menor elemento do conjunto
                pair<int,int> menor = *menores.begin();
                menores.erase( menores.begin() );
                // insere na lista final
                listaFinal.push_back( menor.first );
                // retira mais um elemento da lista original e o coloca na ABB
                if ( !listas[ menor.second ].empty() ) {
                        menores.insert( pair<int,int>( *listas[ menor.second ].begin(), menor.second ) );
                        listas[ menor.second ].erase( listas[ menor.second ].begin() );
                }
        }
 
        for( list<int>::iterator it = listaFinal.begin(); it != listaFinal.end(); it++) {
                cout << *it << endl;
        }
        return 0;
}

Exercício 7

Nem entendi…