Pular para conteúdo

Lista 04 · std::vector

Exercícios da Semana 4 — std::vector.

Como resolver

Copie o bloco de código de cada exercício, cole no seu compilador online, preencha a parte marcada como ESCREVA SUA SOLUCAO AQUI e rode. A saída mostra quais testes passaram.

ex01

Escreva soma_vector, que recebe um std::vector<int> (por referência constante) e devolve a soma de todos os elementos.

soma_vector({1, 2, 3})  // -> 6
soma_vector({})         // -> 0

// ex01 — versao de arquivo unico (gerada automaticamente,
// nao edite este arquivo direto: edite os fontes em exercicios/ e rode
// tools/gerar_single.py --todos de novo).
//
// Cole este arquivo inteiro no seu compilador online e rode.

#include <cassert>
#include <iostream>
#include <vector>

// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX01_H
#define EX01_H

// Retorna a soma de todos os elementos do vector.
int soma_vector(const std::vector<int>& v);

#endif

// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
int soma_vector(const std::vector<int>& v) {
    // TODO: percorra v somando os elementos.
    return 0;
}

// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
    assert(soma_vector({1, 2, 3}) == 6);
    assert(soma_vector({}) == 0);
    assert(soma_vector({-5, 5}) == 0);
    assert(soma_vector({10}) == 10);
    std::cout << "Todos os testes passaram!\n";
    return 0;
}

ex02

Escreva maior_elemento, que recebe um std::vector<int> não vazio e devolve o maior valor.

maior_elemento({3, 9, 1, 7})  // -> 9
maior_elemento({-5, -1, -9})  // -> -1

// ex02 — versao de arquivo unico (gerada automaticamente,
// nao edite este arquivo direto: edite os fontes em exercicios/ e rode
// tools/gerar_single.py --todos de novo).
//
// Cole este arquivo inteiro no seu compilador online e rode.

#include <cassert>
#include <iostream>
#include <vector>

// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX02_H
#define EX02_H

// Retorna o maior elemento do vector (assume que v nao esta vazio).
int maior_elemento(const std::vector<int>& v);

#endif

// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
int maior_elemento(const std::vector<int>& v) {
    // TODO: percorra v guardando o maior valor visto ate agora.
    return 0;
}

// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
    assert(maior_elemento({3, 9, 1, 7}) == 9);
    assert(maior_elemento({-5, -1, -9}) == -1);
    assert(maior_elemento({4}) == 4);
    assert(maior_elemento({1, 1, 1}) == 1);
    std::cout << "Todos os testes passaram!\n";
    return 0;
}

ex03

Escreva filtra_pares, que recebe um std::vector<int> e devolve um novo vector contendo só os elementos pares, na mesma ordem.

filtra_pares({1, 2, 3, 4, 5, 6})  // -> {2, 4, 6}
filtra_pares({1, 3, 5})           // -> {}

// ex03 — versao de arquivo unico (gerada automaticamente,
// nao edite este arquivo direto: edite os fontes em exercicios/ e rode
// tools/gerar_single.py --todos de novo).
//
// Cole este arquivo inteiro no seu compilador online e rode.

#include <cassert>
#include <iostream>
#include <vector>

// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX03_H
#define EX03_H

// Retorna um novo vector so com os elementos pares de v, na mesma ordem.
std::vector<int> filtra_pares(const std::vector<int>& v);

#endif

// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
std::vector<int> filtra_pares(const std::vector<int>& v) {
    // TODO: monte um novo vector so com os elementos pares de v (use push_back).
    return {};
}

// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
    std::vector<int> esperado1 = {2, 4, 6};
    assert(filtra_pares({1, 2, 3, 4, 5, 6}) == esperado1);

    std::vector<int> esperado2 = {};
    assert(filtra_pares({1, 3, 5}) == esperado2);

    std::vector<int> esperado3 = {2, 4};
    assert(filtra_pares({2, 4}) == esperado3);

    std::cout << "Todos os testes passaram!\n";
    return 0;
}

ex04

Escreva inverte_vector, que recebe um std::vector<int>& e inverte a ordem dos elementos no próprio vector (não use std::reverse — pratique trocando elementos de posição na mão, como fez com string na Lista 01).

std::vector<int> v = {1, 2, 3, 4};
inverte_vector(v);
// v agora e {4, 3, 2, 1}

// ex04 — versao de arquivo unico (gerada automaticamente,
// nao edite este arquivo direto: edite os fontes em exercicios/ e rode
// tools/gerar_single.py --todos de novo).
//
// Cole este arquivo inteiro no seu compilador online e rode.

#include <cassert>
#include <iostream>
#include <vector>

// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX04_H
#define EX04_H

// Inverte a ordem dos elementos de v, alterando o proprio vector do chamador.
void inverte_vector(std::vector<int>& v);

#endif

// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
void inverte_vector(std::vector<int>& v) {
    // TODO: troque v[i] com v[v.size()-1-i] para i indo do inicio ate o meio.
}

// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
    std::vector<int> a = {1, 2, 3, 4};
    inverte_vector(a);
    std::vector<int> esperado_a = {4, 3, 2, 1};
    assert(a == esperado_a);

    std::vector<int> b = {1, 2, 3};
    inverte_vector(b);
    std::vector<int> esperado_b = {3, 2, 1};
    assert(b == esperado_b);

    std::vector<int> c = {};
    inverte_vector(c);
    assert(c.empty());

    std::cout << "Todos os testes passaram!\n";
    return 0;
}

ex05

Escreva soma_matriz, que recebe uma "matriz" (std::vector<std::vector<int>>) e devolve a soma de todos os elementos, de todas as linhas.

soma_matriz({{1, 2}, {3, 4}})  // -> 10
soma_matriz({{5}})             // -> 5
soma_matriz({})                // -> 0

// ex05 — versao de arquivo unico (gerada automaticamente,
// nao edite este arquivo direto: edite os fontes em exercicios/ e rode
// tools/gerar_single.py --todos de novo).
//
// Cole este arquivo inteiro no seu compilador online e rode.

#include <cassert>
#include <iostream>
#include <vector>

// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX05_H
#define EX05_H

// Retorna a soma de todos os elementos da matriz (vector de vector).
int soma_matriz(const std::vector<std::vector<int>>& matriz);

#endif

// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
int soma_matriz(const std::vector<std::vector<int>>& matriz) {
    // TODO: percorra cada linha e, dentro dela, cada elemento, somando tudo.
    return 0;
}

// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
    assert(soma_matriz({{1, 2}, {3, 4}}) == 10);
    assert(soma_matriz({{5}}) == 5);
    assert(soma_matriz({}) == 0);
    assert(soma_matriz({{1, 1, 1}, {1, 1, 1}}) == 6);
    std::cout << "Todos os testes passaram!\n";
    return 0;
}

ex06

Dada a struct Aluno (campos nome e nota, já declarada), escreva media_turma, que recebe um std::vector<Aluno> não vazio e devolve a média das notas.

media_turma({{"Ana", 8.0}, {"Bruno", 6.0}})  // -> 7.0

// ex06 — versao de arquivo unico (gerada automaticamente,
// nao edite este arquivo direto: edite os fontes em exercicios/ e rode
// tools/gerar_single.py --todos de novo).
//
// Cole este arquivo inteiro no seu compilador online e rode.

#include <cassert>
#include <iostream>
#include <cmath>
#include <string>
#include <vector>

// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX06_H
#define EX06_H

struct Aluno {
    std::string nome;
    double nota;
};

// Retorna a media das notas da turma (assume que turma nao esta vazia).
double media_turma(const std::vector<Aluno>& turma);

#endif

// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
double media_turma(const std::vector<Aluno>& turma) {
    // TODO: some as notas de cada Aluno em turma e divida pela quantidade.
    return 0.0;
}

// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
    std::vector<Aluno> t1 = {{"Ana", 8.0}, {"Bruno", 6.0}};
    assert(std::abs((media_turma(t1)) - (7.0)) <= (0.0001));

    std::vector<Aluno> t2 = {{"Carla", 10.0}};
    assert(std::abs((media_turma(t2)) - (10.0)) <= (0.0001));

    std::vector<Aluno> t3 = {{"A", 5.0}, {"B", 5.0}, {"C", 5.0}};
    assert(std::abs((media_turma(t3)) - (5.0)) <= (0.0001));

    std::cout << "Todos os testes passaram!\n";
    return 0;
}

ex07

Um pico é um elemento estritamente maior que o anterior e estritamente maior que o seguinte. Escreva conta_picos, que recebe um std::vector<int> e devolve quantos picos ele tem.

O primeiro e o último elemento nunca são picos (falta vizinho de um dos lados), e um vector com menos de três elementos não tem pico nenhum.

conta_picos({1, 3, 2, 5, 4})   // -> 2   (o 3 e o 5)
conta_picos({1, 2, 3})         // -> 0   (o 3 nao tem sucessor)
conta_picos({5, 5, 5})         // -> 0   (precisa ser estritamente maior)

// ex07 — versao de arquivo unico (gerada automaticamente,
// nao edite este arquivo direto: edite os fontes em exercicios/ e rode
// tools/gerar_single.py --todos de novo).
//
// Cole este arquivo inteiro no seu compilador online e rode.

#include <cassert>
#include <iostream>
#include <vector>

// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX07_H
#define EX07_H

// Retorna quantos elementos sao estritamente maiores que o anterior
// e que o seguinte. Vectors com menos de 3 elementos nao tem picos.
int conta_picos(const std::vector<int>& v);

#endif

// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
int conta_picos(const std::vector<int>& v) {
    // TODO: percorra de i = 1 ate v.size() - 2 (assim i-1 e i+1 sempre existem)
    // e conte quantas vezes v[i] > v[i-1] && v[i] > v[i+1].
    return 0;
}

// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
    assert(conta_picos({1, 3, 2, 5, 4}) == 2);
    assert(conta_picos({1, 2, 3}) == 0);
    assert(conta_picos({5, 5, 5}) == 0);
    assert(conta_picos({3, 1, 2}) == 0);
    assert(conta_picos({1, 9, 1}) == 1);
    assert(conta_picos({}) == 0);
    assert(conta_picos({7}) == 0);
    assert(conta_picos({7, 8}) == 0);
    std::cout << "Todos os testes passaram!\n";
    return 0;
}

ex08

Escreva soma_diagonal, que recebe uma matriz quadrada (std::vector<std::vector<int>>) e devolve a soma dos elementos da diagonal principal — aqueles em que o índice da linha é igual ao índice da coluna.

soma_diagonal({{1, 2}, {3, 4}})                  // -> 5    (1 + 4)
soma_diagonal({{1, 0, 0}, {0, 2, 0}, {0, 0, 3}}) // -> 6

// ex08 — versao de arquivo unico (gerada automaticamente,
// nao edite este arquivo direto: edite os fontes em exercicios/ e rode
// tools/gerar_single.py --todos de novo).
//
// Cole este arquivo inteiro no seu compilador online e rode.

#include <cassert>
#include <iostream>
#include <vector>

// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX08_H
#define EX08_H

// Retorna a soma dos elementos da diagonal principal de uma matriz quadrada
// (os elementos em que linha == coluna).
int soma_diagonal(const std::vector<std::vector<int>>& matriz);

#endif

// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
int soma_diagonal(const std::vector<std::vector<int>>& matriz) {
    // TODO: percorra i de 0 ate matriz.size() - 1 e acumule matriz[i][i].
    return 0;
}

// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
    assert(soma_diagonal({{1, 2}, {3, 4}}) == 5);
    assert(soma_diagonal({{1, 0, 0}, {0, 2, 0}, {0, 0, 3}}) == 6);
    assert(soma_diagonal({{7}}) == 7);
    assert(soma_diagonal({{-1, 5}, {5, -2}}) == -3);
    assert(soma_diagonal({}) == 0);
    std::cout << "Todos os testes passaram!\n";
    return 0;
}

ex09

Dada a struct Produto (campos nome, quantidade e preco, já declarada), escreva adiciona_produto, que recebe um std::vector<Produto>& (o inventário), um nome, uma quantidade e um preço:

  • se já existir um produto com aquele nome, atualize a quantidade e o preço dele e devolva false;
  • se não existir, acrescente um novo Produto ao fim do vector e devolva true.
std::vector<Produto> estoque;
adiciona_produto(estoque, "resistor", 10, 0.25);  // -> true   (entrou um novo)
adiciona_produto(estoque, "resistor", 40, 0.30);  // -> false  (so atualizou)
// estoque tem 1 produto, com quantidade 40 e preco 0.30

// ex09 — versao de arquivo unico (gerada automaticamente,
// nao edite este arquivo direto: edite os fontes em exercicios/ e rode
// tools/gerar_single.py --todos de novo).
//
// Cole este arquivo inteiro no seu compilador online e rode.

#include <cassert>
#include <iostream>
#include <cmath>
#include <string>
#include <vector>

// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX09_H
#define EX09_H

struct Produto {
    std::string nome;
    int quantidade;
    double preco;
};

// Se ja houver um produto com esse nome no inventario, atualiza quantidade e
// preco e retorna false. Caso contrario, acrescenta um novo e retorna true.
bool adiciona_produto(std::vector<Produto>& inventario,
                      const std::string& nome, int quantidade, double preco);

#endif

// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
bool adiciona_produto(std::vector<Produto>& inventario,
                      const std::string& nome, int quantidade, double preco) {
    // TODO: procure um produto com esse nome no inventario.
    // Se achar, atualize os campos quantidade e preco dele e devolva false.
    // Se nao achar, use push_back para acrescentar um Produto novo e devolva true.
    return false;
}

// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
    std::vector<Produto> estoque;

    assert(adiciona_produto(estoque, "resistor", 10, 0.25));
    assert(estoque.size() == 1);
    assert(estoque[0].quantidade == 10);

    assert(!(adiciona_produto(estoque, "resistor", 40, 0.30)));
    assert(estoque.size() == 1);
    assert(estoque[0].quantidade == 40);
    assert(std::abs((estoque[0].preco) - (0.30)) <= (0.0001));

    assert(adiciona_produto(estoque, "capacitor", 5, 1.50));
    assert(estoque.size() == 2);
    assert(estoque[1].nome == std::string("capacitor"));

    // O produto que ja existia nao pode ter sido alterado pela insercao do outro.
    assert(estoque[0].quantidade == 40);

    std::cout << "Todos os testes passaram!\n";
    return 0;
}

ex10

Escreva eh_ordenado, que devolve true se o vector estiver em ordem crescente. Elementos iguais lado a lado contam como ordenados. Um vector vazio ou com um único elemento está ordenado.

Este é um exercício de lógica: compare cada elemento com o seguinte, e devolva false assim que achar um par fora de ordem. Não use std::is_sorted — as ferramentas de <algorithm> chegam na Lista 08.

Cuidado com o limite do laço: quem percorre até o último elemento e lê v[i + 1] sai do vector.

eh_ordenado({1, 2, 3})   // -> true
eh_ordenado({3, 1, 2})   // -> false
eh_ordenado({})          // -> true

// ex10 — versao de arquivo unico (gerada automaticamente,
// nao edite este arquivo direto: edite os fontes em exercicios/ e rode
// tools/gerar_single.py --todos de novo).
//
// Cole este arquivo inteiro no seu compilador online e rode.

#include <cassert>
#include <iostream>
#include <vector>

// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX10_H
#define EX10_H

// Retorna true se v estiver em ordem crescente (elementos iguais lado a
// lado sao aceitos). Um vector vazio ou de um elemento so esta ordenado.
bool eh_ordenado(const std::vector<int>& v);

#endif

// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
bool eh_ordenado(const std::vector<int>& v) {
    // TODO: compare cada elemento com o seguinte. Se achar um par fora de
    // ordem, ja pode devolver false. Se o laco terminar, esta ordenado.
    return false;
}

// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
    assert(eh_ordenado({1, 2, 3}));
    assert(eh_ordenado({1, 1, 2}));
    assert(!(eh_ordenado({3, 1, 2})));
    assert(!(eh_ordenado({1, 2, 0})));

    assert(eh_ordenado({7}));
    assert(eh_ordenado({}));

    std::cout << "Todos os testes passaram!\n";
    return 0;
}

ex11

Escreva ultima_ocorrencia, que recebe um std::vector<int> (por referência constante) e um valor alvo, e devolve o índice da última ocorrência de alvo no vector, ou -1 se ele não aparecer.

ultima_ocorrencia({5, 7, 5, 2}, 5)  // -> 2   (a segunda aparicao do 5)
ultima_ocorrencia({5, 7, 5, 2}, 9)  // -> -1
ultima_ocorrencia({}, 5)            // -> -1

Dois pontos do capítulo 4 aparecem juntos aqui: o retorno é int, mas o índice de um vector é std::size_t; e a varredura mais direta é de trás para frente, que é exatamente onde um índice std::size_t nunca chega a ser negativo — o laço não termina. Guarde o tamanho num int com static_cast<int> antes do laço, e o problema some.

// ex11 — versao de arquivo unico (gerada automaticamente,
// nao edite este arquivo direto: edite os fontes em exercicios/ e rode
// tools/gerar_single.py --todos de novo).
//
// Cole este arquivo inteiro no seu compilador online e rode.

#include <cassert>
#include <iostream>
#include <vector>

// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX11_H
#define EX11_H

// Devolve o indice da ultima ocorrencia de alvo em v, ou -1 se nao houver.
int ultima_ocorrencia(const std::vector<int>& v, int alvo);

#endif

// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
int ultima_ocorrencia(const std::vector<int>& v, int alvo) {
    // TODO: guarde o tamanho em int n = static_cast<int>(v.size()) e percorra
    // de n - 1 ate 0. Nao use std::size_t no indice: andando para tras ele
    // nunca fica negativo, e o laco nao termina.
    return -1;
}

// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
    assert(ultima_ocorrencia({5, 7, 5, 2}, 5) == 2);
    assert(ultima_ocorrencia({5, 7, 5, 2}, 9) == -1);
    assert(ultima_ocorrencia({5, 7, 5, 2}, 2) == 3);
    assert(ultima_ocorrencia({5, 7, 5, 2}, 7) == 1);
    assert(ultima_ocorrencia({}, 5) == -1);
    assert(ultima_ocorrencia({4}, 4) == 0);
    assert(ultima_ocorrencia({4}, 5) == -1);
    assert(ultima_ocorrencia({-1, -1, -1}, -1) == 2);

    std::cout << "Todos os testes passaram!\n";
    return 0;
}

ex12

Escreva aplica_desconto, que recebe um std::vector<double>& de preços e um percentual de desconto (double, com valor padrão 10.0), e reduz cada preço do próprio vector por esse percentual.

Note que o vector chega por referência não constante: a função não devolve nada, ela altera os preços do chamador. É o argumento padrão do capítulo 2 encontrando o vector do capítulo 4.

std::vector<double> precos = {100.0, 50.0};
aplica_desconto(precos);        // usa 10% (padrao)
// precos agora e {90.0, 45.0}

aplica_desconto(precos, 50.0);  // 50% sobre os novos valores
// precos agora e {45.0, 22.5}

// ex12 — versao de arquivo unico (gerada automaticamente,
// nao edite este arquivo direto: edite os fontes em exercicios/ e rode
// tools/gerar_single.py --todos de novo).
//
// Cole este arquivo inteiro no seu compilador online e rode.

#include <cassert>
#include <iostream>
#include <cmath>
#include <vector>

// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX12_H
#define EX12_H

// Reduz cada preco de "precos" pelo percentual informado (in-place).
void aplica_desconto(std::vector<double>& precos, double percentual = 10.0);

#endif

// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
void aplica_desconto(std::vector<double>& precos, double percentual) {
    // TODO: para cada preco p em "precos", atualize p para p * (1 - percentual/100).
}

// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
    std::vector<double> precos = {100.0, 50.0};
    aplica_desconto(precos);
    assert(std::abs((precos[0]) - (90.0)) <= (0.0001));
    assert(std::abs((precos[1]) - (45.0)) <= (0.0001));

    aplica_desconto(precos, 50.0);
    assert(std::abs((precos[0]) - (45.0)) <= (0.0001));
    assert(std::abs((precos[1]) - (22.5)) <= (0.0001));

    std::vector<double> zero = {10.0};
    aplica_desconto(zero, 0.0);
    assert(std::abs((zero[0]) - (10.0)) <= (0.0001));

    std::cout << "Todos os testes passaram!\n";
    return 0;
}