(6) Escreva uma função genérica que recebe como parâmetro um vector de valores de qualquer tipo e retorna true se os elementos estiverem ordenados ou false, caso contrário. Na função main, faça a chamada da função para valores do tipo int, float e char.
(7) Crie e preencha um deque de elementos inteiros na função main. Crie funções em seu programa, que encontrem e retornem (deve ser criada uma função para cada tópico abaixo):
  • o maior elemento;
  • o menor elemento;
  • a quantidade de vezes que o maior elemento aparece na lista;
  • a quantidade de vezes que o menor elemento aparece na lista.
    (8) Crie uma função capaz de mesclar (unir preservando a ordenação dos elementos) duas listas (list) previamente ordenadas, percorrendo apenas uma vez essas listas. Observações: uma nova lista deve ser criada e retornada e as listas originais não devem ser alteradas.

Passo 1

Beleza, o exercício junta três temas de C++ bem legais:
  1. Função genérica (template) que recebe um std::vector<T> e diz se ele está ordenado;
  2. Uso de std::deque<int>, criando funções para encontrar o maior, o menor e contar quantas vezes cada um aparece;
  3. Função para mesclar (merge) duas std::list<T> já ordenadas, caminhando apenas uma vez em cada lista.
Pra resolver isso vamos usar template functions, iteradores da STL e lógica de comparação simples.

Passo 2

(Exercício 6) Função genérica para testar se um vector está ordenado
  1. Criar um template <typename T> bool isSorted(const std::vector<T>& v).
  2. Percorrer o vetor com um laço de i = 1 até v.size() - 1.
  3. Em cada passo, comparar v[i] com v[i-1]. Se v[i] < v[i-1], não está ordenado → retorna false.
  4. Se sair do laço sem achar quebra, retorna true.
Explicando a teoria: usamos template pra aceitar qualquer tipo que suporte operador <. A checagem é linha-a-linha, comparando pares consecutivos.

Passo 3

(Exercício 7) Deque de inteiros e funções sobre ele
  1. Em main(), preencher um std::deque<int> d{ … }.
  2. Criar quatro funções:
    • int findMax(const std::deque<int>& d): faz um scan, guarda o maior visto.
    • int findMin(const std::deque<int>& d): igual, mas acha o menor.
    • int countMax(const std::deque<int>& d): primeiro chama findMax, depois faz outro scan contando quantas vezes o valor aparece.
    • int countMin(const std::deque<int>& d): idem para o mínimo.
Teoria: deque funciona como vetor duplo. Iterar é O(n). Guardamos valor e incrementamos contador quando bate.

Passo 4

(Exercício 8) Mesclando duas listas ordenadas
  1. Declarar template <typename T> std::list<T> mergeLists(const std::list<T>& a, const std::list<T>& b).
  2. Criar duas iterators itA = a.begin(), itB = b.begin().
  3. Enquanto itA != a.end() e itB != b.end(), comparar *itA e *itB:
    • Se *itA < *itB, push_back(*itA++) na lista resultado.
    • Senão, push_back(*itB++).
  4. Quando um acabar, joga o resto do outro na lista resultado.
  5. Retorna a lista mesclada, sem alterar a e b.
Isso é o famoso algoritmo de merge de listas – percorre cada lista uma única vez, O(n+m).

Resposta

#include <iostream>
#include <vector>
#include <deque>
#include <list>

// Exercício 6: função genérica para vetor ordenado
template<typename T>
bool isSorted(const std::vector<T>& v) {
    if (v.size() < 2) return true;
    for (size_t i = 1; i < v.size(); ++i) {
        if (v[i] < v[i-1])
            return false;
    }
    return true;
}

// Exercício 7: funções para deque<int>
int findMax(const std::deque<int>& d) {
    if (d.empty()) throw std::runtime_error("Deque vazio");
    int m = d.front();
    for (int x : d)
        if (x > m) m = x;
    return m;
}

int findMin(const std::deque<int>& d) {
    if (d.empty()) throw std::runtime_error("Deque vazio");
    int m = d.front();
    for (int x : d)
        if (x < m) m = x;
    return m;
}

int countMax(const std::deque<int>& d) {
    int m = findMax(d), cnt = 0;
    for (int x : d)
        if (x == m) ++cnt;
    return cnt;
}

int countMin(const std::deque<int>& d) {
    int m = findMin(d), cnt = 0;
    for (int x : d)
        if (x == m) ++cnt;
    return cnt;
}

// Exercício 8: merge de duas listas ordenadas
template<typename T>
std::list<T> mergeLists(const std::list<T>& a, const std::list<T>& b) {
    std::list<T> result;
    auto itA = a.begin(), itB = b.begin();
    while (itA != a.end() && itB != b.end()) {
        if (*itA < *itB) {
            result.push_back(*itA);
            ++itA;
        } else {
            result.push_back(*itB);
            ++itB;
        }
    }
    // joga o resto
    while (itA != a.end()) result.push_back(*itA++);
    while (itB != b.end()) result.push_back(*itB++);
    return result;
}

int main() {
    // Testando exercício 6
    std::vector<int> vi {1, 2, 3, 3, 5};
    std::vector<float> vf {1.0f, 0.5f, 2.3f};
    std::vector<char> vc {'a', 'b', 'c'};
    std::cout << std::boolalpha;
    std::cout << "vi ordenado? " << isSorted(vi) << "\n";
    std::cout << "vf ordenado? " << isSorted(vf) << "\n";
    std::cout << "vc ordenado? " << isSorted(vc) << "\n\n";

    // Exercício 7
    std::deque<int> dq {5, 3, 9, 3, 9, 1, 9};
    std::cout << "Maior: " << findMax(dq) << "\n";
    std::cout << "Menor: " << findMin(dq) << "\n";
    std::cout << "Qtde máximo: " << countMax(dq) << "\n";
    std::cout << "Qtde mínimo: " << countMin(dq) << "\n\n";

    // Exercício 8
    std::list<int> la {1, 4, 6, 8};
    std::list<int> lb {2, 3, 5, 7, 9};
    std::list<int> lm = mergeLists(la, lb);
    std::cout << "Merge: ";
    for (int x : lm) std::cout << x << ' ';
    std::cout << '\n';

    return 0;
}

Exercícios relacionados