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

Primeira lista

Exercício 1

Não tenho muita certeza em relação ao item (g). Só consegui chegar a (g) = . A ordem que achei foi:
f > a > j ~ d > e > g ~ h > b ~ c > i

Exercício 2

Tive que usar o teorema mestre do Cormen para fazer a complexidade do (d).

(a)
(b)
(c)
(d)

Exercício 3

A1: e
A2: e . ou
A3: e .
A4: e .

Exercício 6

(a)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
 
using namespace std;
 
#define FOR(i,n) for (int i=0;i<n;i++)
#define FORA(i,a,b) for (int i=a;i<b;i++)
#define all(c) (c).begin(),(c).end()
#define sz(c) (int)((c).size())
 
vector<int> randomVector(int n) {
        //srand(time(0));
        srand(45355);
        vector<int> v(n,0);
        FOR(i,n) v[i] = rand()%(1<<5);
        return v;
}
void printVector(vector<int> &v) {
        FOR(i,sz(v)) cout << v[i] << " ";
        cout << endl;
}
 
int main() {
        int n;
        cin >> n;
        vector<int> V = randomVector(n);
 
        int numInversoes = 0;
        FOR(i,n) FORA(j,i+1,n) {
           if (V[j] < V[i]) numInversoes++;
        }
        printVector(V);
        cout << numInversoes << endl;
 
        return 0;
}

(b)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
 
using namespace std;
 
#define FOR(i,n) for (int i=0;i<n;i++)
#define FORA(i,a,b) for (int i=a;i<b;i++)
#define all(c) (c).begin(),(c).end()
#define sz(c) (int)((c).size())
 
vector<int> randomVector(int n) {
        //srand(time(0));
        srand(45355);
        vector<int> v(n,0);
        FOR(i,n) v[i] = rand()%(1<<5);
        return v;
}
void printVector(vector<int> &v) {
        FOR(i,sz(v)) cout << v[i] << " ";
        cout << endl;
}
 
const int INF = 1000000000;
int mistura(vector<int> &v, int b, int m, int e) {
        int N1 = (m-b+1);
        int N2 = (e-m);
        vector<int> L(N1+1,INF);
        vector<int> R(N2+1,INF);
 
        FOR(i,N1) L[i] = v[b+i];
        FOR(i,N2) R[i] = v[m+1+i];
 
        // conta as inversoes O(N1 + N2) = O(N)
        int ret = 0, pL = 0, pR = 0;
        while (pR < N2) {
           while (pL < N1 && L[pL] <= R[pR]) pL++;
           ret += (N1 - pL);
           pR++;
        }
 
        // intercala e retorna ordenado
        int k = b;
        pL = pR = 0;
        while (k <= e) {
           if (L[pL] < R[pR])
                v[k] = L[pL++];
           else
                v[k] = R[pR++];
           k++;
        }
        return ret;
}
 
int numInversoes(vector<int> &v, int b, int e) {
        if (b < e) {
           int meio = (b+e)/2;
           int left = numInversoes(v,b,meio); // inversoes do lado esquerdo
           int right = numInversoes(v,meio+1,e); // inversoes do lado direito
           int mix = mistura(v,b,meio,e); // inversoes da mistura dos dois lados
           return left + right + mix;
        }
        return 0;
}
 
int main() {
        int n;
        cin >> n;
        vector<int> V = randomVector(n);
        printVector(V);
 
        cout << numInversoes(V,0,sz(V)-1) << endl;
 
        return 0;
}

(c)

(d)

O primeiro algoritmo é , enquanto o segundo é . No segundo algoritmo estamos fazendo uma ordenação igualzinha ao merge-sort, só que na hora de juntar os dois pedaços (intercalar as duas sub-listas ordenadas) nós "aproveitamos" e contamos as inversões.

Exercício 7

Semelhante a um exercício de outra lista.

Exercício 8

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
 
using namespace std;
 
#define FOR(i,n) for (int i=0;i<n;i++)
#define FORA(i,a,b) for (int i=a;i<b;i++)
#define all(c) (c).begin(),(c).end()
#define sz(c) (int)((c).size())
 
vector<int> randomVector(int n) {
        vector<int> v(n,0);
        FOR(i,n) v[i] = rand()%(1<<5);
        return v;
}
void printVector(vector<int> &v) {
        FOR(i,sz(v)) cout << v[i] << " ";
        cout << endl;
}
 
int main() {
        srand(time(0));
        int n, k;
        cin >> n >> k;
        vector<int> S = randomVector(n), T = randomVector(k);
        sort(all(S));
        sort(all(T));
        cout << "S -> "; printVector(S);
        cout << "T -> "; printVector(T);
 
        int i = 0, j = 0;
        while (i < n && j < k) {
           if (S[i] == T[j])
                j++;
           else
                i++;
        }
        cout << (j == k ? "SIM" : "NAO") << endl;
 
        return 0;
}

Exercício 14

(ver exercício 4 da lista de 2007.1)
Complexidade do algoritmo original: (recorrência ).
Complexidade do algoritmo modificado: (recorrência ).