Lista 05 · Algoritmos clássicos: escrevendo na mão¶
Exercícios da Semana 5 — Algoritmos clássicos: escrevendo na mão.
Esta lista tem uma regra que vale para todos os exercícios: não use <algorithm>. Nada de std::sort, std::find, std::count_if, std::max_element ou std::accumulate. Tudo aqui se resolve com for, if e uma variável auxiliar.
Não é birra: cada uma dessas funções existe e é melhor que a sua versão. Você vai usá-las a partir da Lista 08, depois da Avaliação 1. O ponto desta lista é você saber o que elas fazem por dentro antes de passar a chamá-las.
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 busca_linear, que recebe um std::vector<int> e um valor alvo, e devolve o índice da primeira ocorrência do alvo — ou -1 se ele não estiver no vector.
Percorra com um índice e devolva assim que achar: não adianta continuar procurando.
O -1 serve como "não achei" porque nenhum índice válido é negativo. É a mesma convenção do busca_posicao da Lista 03.
// 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 o indice da primeira ocorrencia de "alvo" em "v",
// ou -1 se o alvo nao estiver no vector.
int busca_linear(const std::vector<int>& v, int alvo);
#endif
// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
int busca_linear(const std::vector<int>& v, int alvo) {
// TODO: percorra "v" com um indice; devolva o indice assim que achar "alvo".
// Se o laco terminar sem achar, devolva -1.
return -1;
}
// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
std::vector<int> v = {4, 1, 9, 1};
assert(busca_linear(v, 4) == 0);
assert(busca_linear(v, 9) == 2);
// primeira ocorrencia, nao a ultima
assert(busca_linear(v, 1) == 1);
assert(busca_linear(v, 7) == -1);
std::vector<int> vazio;
assert(busca_linear(vazio, 1) == -1);
std::cout << "Todos os testes passaram!\n";
return 0;
}
ex02¶
Escreva indice_do_menor, que recebe um std::vector<int> e devolve o índice do menor valor — ou -1 se o vector estiver vazio. Havendo empate, devolva o índice da primeira ocorrência.
Repare que a resposta é o índice, e não o valor: você precisa guardar as duas coisas enquanto percorre — o menor visto até agora e onde ele estava.
Comece a comparação por v[0], e não por 0: um dos casos de teste só tem números positivos, e é ele que separa as duas versões.
indice_do_menor({4, 1, 9, 1}) // -> 1 (a primeira das duas ocorrencias de 1)
indice_do_menor({7, 3, 5}) // -> 1
indice_do_menor({}) // -> -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 indice do menor valor de "v" (o primeiro, em caso de empate),
// ou -1 se o vector estiver vazio.
int indice_do_menor(const std::vector<int>& v);
#endif
// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
int indice_do_menor(const std::vector<int>& v) {
// TODO:
// 1. vector vazio -> devolva -1.
// 2. comece o menor em v[0] e o indice em 0 (NAO comece o menor em 0).
// 3. percorra de i = 1 ate o fim; se v[i] for MENOR que o menor,
// atualize os dois. Use < , nao <= , para o empate ficar com o primeiro.
return -1;
}
// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
assert(indice_do_menor({4, 1, 9, 2}) == 1);
// empate: vale o indice da PRIMEIRA ocorrencia
assert(indice_do_menor({4, 1, 9, 1}) == 1);
// so positivos: quem comecou o menor em 0 erra aqui
assert(indice_do_menor({7, 3, 5}) == 1);
// so negativos
assert(indice_do_menor({-5, -2, -9}) == 2);
// o menor ja na primeira posicao
assert(indice_do_menor({1, 2, 3}) == 0);
// um elemento so
assert(indice_do_menor({42}) == 0);
std::vector<int> vazio;
assert(indice_do_menor(vazio) == -1);
std::cout << "Todos os testes passaram!\n";
return 0;
}
ex03¶
Escreva conta_trocas_de_sinal, que recebe um std::vector<int> sem zeros e devolve quantas vezes a sequência troca de sinal de um elemento para o seguinte.
Em {3, -1, -2, 5} há duas trocas: de 3 para -1 (positivo → negativo) e de -2 para 5 (negativo → positivo). A troca de -1 para -2 não conta, porque os dois são negativos.
Dois cuidados. O contador precisa ser declarado antes do laço: se ele nascer dentro, é recriado a cada volta e a resposta sai sempre 0 ou 1. E o laço compara pares de vizinhos, não elementos isolados — então ele começa em 1 (para poder olhar v[i - 1]) e um vector com um elemento só nunca tem troca.
Dica para decidir se dois números têm sinais diferentes: o produto v[i - 1] * v[i] é negativo exatamente nesse caso.
conta_trocas_de_sinal({3, -1, -2, 5}) // -> 2
conta_trocas_de_sinal({1, 2, 3}) // -> 0
conta_trocas_de_sinal({1, -1, 1, -1}) // -> 3
conta_trocas_de_sinal({}) // -> 0
// 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 quantas vezes a sequencia troca de sinal entre elementos
// vizinhos. Assume que v nao contem zeros.
int conta_trocas_de_sinal(const std::vector<int>& v);
#endif
// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
int conta_trocas_de_sinal(const std::vector<int>& v) {
// TODO: declare o contador ANTES do laco.
// Percorra de i = 1 ate o fim comparando v[i - 1] com v[i]:
// se os sinais forem diferentes, incremente o contador.
return 0;
}
// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
assert(conta_trocas_de_sinal({3, -1, -2, 5}) == 2);
// nenhuma troca: todos do mesmo sinal
assert(conta_trocas_de_sinal({1, 2, 3}) == 0);
assert(conta_trocas_de_sinal({-1, -2, -3}) == 0);
// troca em toda posicao: se o contador nascer dentro do laco, da 1
assert(conta_trocas_de_sinal({1, -1, 1, -1}) == 3);
// um elemento so nao tem vizinho: nao ha troca
assert(conta_trocas_de_sinal({7}) == 0);
// vector vazio: o laco nem roda
std::vector<int> vazio;
assert(conta_trocas_de_sinal(vazio) == 0);
std::cout << "Todos os testes passaram!\n";
return 0;
}
ex04¶
Escreva media_dos_positivos, que recebe um std::vector<double> e devolve a média aritmética apenas dos valores maiores que zero. Se não houver nenhum positivo, devolva 0.0.
O exercício pede duas variáveis vivendo lado a lado no mesmo laço: a soma dos positivos e quantos positivos você somou. Não dá para dividir por v.size() no fim — o divisor é o contador, não o tamanho do vector.
E é o contador que protege a divisão: {-1.0, -2.0} tem tamanho 2, mas nenhum positivo. Sem o if antes da divisão, essa é uma divisão por zero.
media_dos_positivos({8.0, -3.0, 10.0}) // -> 9.0 (soma 18 / 2 positivos)
media_dos_positivos({-1.0, -2.0}) // -> 0.0
media_dos_positivos({}) // -> 0.0
// 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 <cmath>
#include <vector>
// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX04_H
#define EX04_H
// Retorna a media dos valores maiores que zero em v,
// ou 0.0 se nao houver nenhum positivo.
double media_dos_positivos(const std::vector<double>& v);
#endif
// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
double media_dos_positivos(const std::vector<double>& v) {
// TODO: declare a soma (double) e o contador (int) antes do laco.
// Percorra v: para cada valor > 0, some ao acumulador e incremente
// o contador. No fim, se o contador for 0, devolva 0.0;
// senao devolva soma / contador.
return 0.0;
}
// ============================================================
// NAO ALTERE — testes
// ============================================================
static bool perto(double a, double b) {
return std::fabs(a - b) < 1e-9;
}
int main() {
assert(perto(media_dos_positivos({8.0, -3.0, 10.0}), 9.0));
// todos positivos: a media e a do vector inteiro
assert(perto(media_dos_positivos({2.0, 4.0}), 3.0));
// nenhum positivo: 0.0, e nao uma divisao por zero
assert(perto(media_dos_positivos({-1.0, -2.0}), 0.0));
// o zero NAO conta como positivo
assert(perto(media_dos_positivos({0.0, 6.0}), 6.0));
assert(perto(media_dos_positivos({0.0, 0.0}), 0.0));
// vector vazio
std::vector<double> vazio;
assert(perto(media_dos_positivos(vazio), 0.0));
std::cout << "Todos os testes passaram!\n";
return 0;
}
ex05¶
Escreva bubble_sort, que ordena um std::vector<int> em ordem crescente no próprio vector, comparando vizinhos e trocando quando estiverem fora de ordem. Nada de std::sort.
Dois cuidados: a troca precisa de uma variável temporária, e o vector pode estar vazio — guarde o tamanho num int antes do laço para não cair na armadilha de v.size() - 1.
// 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
// Ordena v em ordem crescente, no proprio vector, usando bubble sort
// (comparar vizinhos e trocar). Nao use std::sort.
void bubble_sort(std::vector<int>& v);
#endif
// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
void bubble_sort(std::vector<int>& v) {
// TODO: guarde o tamanho num int n antes do laco.
// Repita passadas comparando v[i] com v[i + 1] e trocando quando
// estiverem fora de ordem. Voce vai precisar de uma variavel
// temporaria para a troca.
}
// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
std::vector<int> a = {3, 1, 2};
bubble_sort(a);
assert((a == std::vector<int>{1, 2, 3}));
std::vector<int> b = {5, 4, 3, 2, 1};
bubble_sort(b);
assert((b == std::vector<int>{1, 2, 3, 4, 5}));
// ja ordenado continua ordenado
std::vector<int> c = {1, 2, 3};
bubble_sort(c);
assert((c == std::vector<int>{1, 2, 3}));
// repetidos e negativos
std::vector<int> d = {2, -1, 2, 0};
bubble_sort(d);
assert((d == std::vector<int>{-1, 0, 2, 2}));
// um elemento e vazio nao podem estourar
std::vector<int> e = {7};
bubble_sort(e);
assert((e == std::vector<int>{7}));
std::vector<int> vazio;
bubble_sort(vazio);
assert(vazio.empty());
std::cout << "Todos os testes passaram!\n";
return 0;
}
ex06¶
Escreva busca_binaria, que recebe um std::vector<int> já ordenado e um alvo, e devolve o índice do alvo — ou -1 se ele não estiver lá.
A cada volta, descarte metade dos candidatos: olhe o elemento do meio e decida em qual metade continuar. Compare com o ex01: num vector de mil elementos, a busca linear faz até mil comparações; esta faz no máximo dez.
Atenção à condição de parada: com inicio < fim em vez de inicio <= fim, a função erra quando sobra um único candidato — e há um caso de teste exatamente para isso.
// 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 <vector>
// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX06_H
#define EX06_H
// Retorna o indice de "alvo" num vector JA ORDENADO,
// ou -1 se o alvo nao estiver nele.
int busca_binaria(const std::vector<int>& v, int alvo);
#endif
// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
int busca_binaria(const std::vector<int>& v, int alvo) {
// TODO: mantenha "inicio" e "fim" delimitando os candidatos.
// Enquanto inicio <= fim: olhe o meio; se for o alvo, devolva o indice;
// se for menor que o alvo, jogue "inicio" para depois do meio;
// senao jogue "fim" para antes do meio.
// Se o laco terminar, devolva -1.
return -1;
}
// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
std::vector<int> v = {1, 3, 5, 7, 9};
assert(busca_binaria(v, 1) == 0);
assert(busca_binaria(v, 5) == 2);
assert(busca_binaria(v, 9) == 4);
assert(busca_binaria(v, 4) == -1);
assert(busca_binaria(v, 0) == -1);
assert(busca_binaria(v, 10) == -1);
// um elemento so: o <= da condicao de parada e o que faz isto passar
std::vector<int> um = {42};
assert(busca_binaria(um, 42) == 0);
assert(busca_binaria(um, 1) == -1);
std::vector<int> vazio;
assert(busca_binaria(vazio, 1) == -1);
std::cout << "Todos os testes passaram!\n";
return 0;
}
ex07¶
Escreva insere_ordenado, que recebe um std::vector<int> já ordenado em ordem crescente (por referência, para poder alterá-lo) e um valor, e insere o valor na posição certa — de modo que o vector continue ordenado depois da chamada.
Nada de ordenar tudo de novo: o vector já está ordenado, e você só precisa abrir espaço para o valor novo. A receita é a seguinte:
- Acrescente o valor ao fim com
push_back— só para o vector ganhar uma posição. - Ande do fim para o começo enquanto o elemento à esquerda for maior que o valor, empurrando cada um deles uma casa para a direita.
- Quando parar, escreva o valor na posição em que você parou.
Repare que aqui não há troca de dois elementos, e sim um deslocamento: v[i] = v[i - 1] sobrescreve v[i], mas o valor que estava lá já foi copiado para a direita na volta anterior — por isso não se perde nada e não é preciso variável temporária.
Este é, na prática, um passo do insertion sort. Se você chamar esta função repetidamente sobre um vector que começa vazio, ele fica ordenado no fim.
std::vector<int> v = {1, 3, 7};
insere_ordenado(v, 5);
// v agora vale {1, 3, 5, 7}
insere_ordenado(v, 0);
// v agora vale {0, 1, 3, 5, 7}
// 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
// Insere valor em v (que ja esta ordenado de forma crescente),
// mantendo v ordenado.
void insere_ordenado(std::vector<int>& v, int valor);
#endif
// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
void insere_ordenado(std::vector<int>& v, int valor) {
// TODO:
// 1. v.push_back(valor) -- so para abrir uma posicao no fim.
// 2. guarde em i o indice da ultima posicao (tamanho - 1, num int).
// 3. enquanto i > 0 e v[i - 1] > valor: v[i] = v[i - 1]; i--;
// 4. v[i] = valor;
}
// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
// no meio
std::vector<int> v = {1, 3, 7};
insere_ordenado(v, 5);
assert((v == std::vector<int>{1, 3, 5, 7}));
// no comeco: o laco tem que andar ate o indice 0
insere_ordenado(v, 0);
assert((v == std::vector<int>{0, 1, 3, 5, 7}));
// no fim: o laco nao anda nenhuma vez
insere_ordenado(v, 9);
assert((v == std::vector<int>{0, 1, 3, 5, 7, 9}));
// vector vazio
std::vector<int> vazio;
insere_ordenado(vazio, 42);
assert((vazio == std::vector<int>{42}));
// valor repetido: o vector continua ordenado e cresce de tamanho
std::vector<int> repetidos = {2, 2, 5};
insere_ordenado(repetidos, 2);
assert((repetidos == std::vector<int>{2, 2, 2, 5}));
// negativos
std::vector<int> negativos = {-5, -1, 4};
insere_ordenado(negativos, -3);
assert((negativos == std::vector<int>{-5, -3, -1, 4}));
std::cout << "Todos os testes passaram!\n";
return 0;
}
ex08¶
Escreva moda, que escreve num parâmetro por referência o valor mais frequente de um std::vector<int>. A função devolve bool: true se havia o que responder, false se o vector estiver vazio. Se dois valores empatarem em frequência, devolva o que aparece primeiro no vector.
Repare por que aqui não serve um -1 como nas buscas: o que volta é um valor do vector, e -1 é um valor perfeitamente possível. Quando nenhum valor sobra para significar "não achei", a resposta vem separada, num bool.
Você ainda não tem std::map (ele chega na Lista 06), então a contagem é feita na força bruta, com um laço dentro do outro: para cada posição i, percorra o vector inteiro contando quantas vezes v[i] aparece; guarde o melhor resultado até agora, como no ex02.
Dois detalhes decidem o exercício. O contador do laço interno tem que ser zerado a cada i — ele é a única variável desta lista que deve mesmo nascer dentro do laço externo. E a comparação com o melhor até agora precisa ser >, e não >=: com >=, o último empatado ganha, e o enunciado pede o primeiro.
Não se preocupe com eficiência: esta função faz n × n comparações, e tudo bem. Ela existe para você ver o custo de contar sem uma estrutura de dados adequada — na Lista 06 o mesmo problema sai numa passada só.
int valor;
moda({1, 2, 2, 3}, valor) // -> true, e valor vale 2
moda({1, 1, 2, 2}, valor) // -> true, e valor vale 1 (empate: o primeiro)
moda({7}, valor) // -> true, e valor vale 7
moda({}, valor) // -> false
// 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
// Escreve em "valor" o elemento mais frequente de "v" (o primeiro, em caso de
// empate). Devolve true se havia o que responder; devolve false e nao mexe em
// "valor" se o vector estiver vazio.
bool moda(const std::vector<int>& v, int& valor);
#endif
// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
bool moda(const std::vector<int>& v, int& valor) {
// TODO:
// 1. vector vazio -> devolva false.
// 2. para cada i, conte quantas vezes v[i] aparece no vector inteiro
// (laco interno, com o contador zerado a cada i).
// 3. guarde o melhor até agora; use > , e nao >= , para o empate
// ficar com o valor que aparece primeiro.
// 4. escreva o melhor em "valor" e devolva true.
return false;
}
// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
int m = 0;
assert(moda({1, 2, 2, 3}, m));
assert(m == 2);
// empate: vale o que aparece PRIMEIRO (quem usou >= devolve 2)
assert(moda({1, 1, 2, 2}, m));
assert(m == 1);
// todos distintos: todos empatam com 1, vence o primeiro
assert(moda({4, 7, 9}, m));
assert(m == 4);
// um elemento so
assert(moda({7}, m));
assert(m == 7);
// negativos e a moda no fim do vector
assert(moda({-1, 3, 3, -1, 3}, m));
assert(m == 3);
// valores repetidos espalhados, nao contiguos
assert(moda({5, 8, 5, 8, 5}, m));
assert(m == 5);
// vazio: devolve false e nao mexe no parametro de saida
m = 99;
std::vector<int> vazio;
assert(!moda(vazio, m));
assert(m == 99);
std::cout << "Todos os testes passaram!\n";
return 0;
}
ex09¶
Escreva k_esimo_menor, que recebe um std::vector<int> e um número k, e escreve num parâmetro por referência o k-ésimo menor valor do vector. O k conta a partir de 1: k = 1 é o menor de todos, k = 2 é o segundo menor, e assim por diante. A função devolve bool: false se k estiver fora do intervalo — menor que 1 ou maior que a quantidade de elementos.
Valores repetidos ocupam posições próprias: em {5, 1, 5}, o menor é 1, o segundo menor é 5 e o terceiro menor também é 5.
Repare na assinatura: o vector vem por valor, e não por const& como no resto do curso. É proposital — a função precisa ordenar para responder, e ordenar o vector de quem chamou seria um efeito colateral surpreendente: ninguém espera que perguntar "qual é o segundo menor?" reorganize a sua lista. Recebendo por valor, você ordena a sua própria cópia. Há um caso de teste que verifica exatamente isso.
Para ordenar, reaproveite o bubble sort que você escreveu no ex05 — cole-o aqui como uma função auxiliar. E continua valendo a regra da lista: nada de <algorithm>.
int r;
k_esimo_menor({7, 3, 9, 1}, 1, r) // -> true, e r vale 1 (o menor)
k_esimo_menor({7, 3, 9, 1}, 2, r) // -> true, e r vale 3
k_esimo_menor({7, 3, 9, 1}, 4, r) // -> true, e r vale 9 (o maior)
k_esimo_menor({7, 3, 9, 1}, 5, r) // -> false
// 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 <vector>
// ============================================================
// Declaracoes do exercicio
// ============================================================
#ifndef EX09_H
#define EX09_H
// Escreve em "valor" o k-esimo menor elemento de "v". k comeca em 1.
// Devolve true se k estiver em [1, v.size()]; devolve false e nao mexe em
// "valor" caso contrario.
// Recebe o vector por valor porque precisa ordenar uma copia.
bool k_esimo_menor(std::vector<int> v, int k, int& valor);
#endif
// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
bool k_esimo_menor(std::vector<int> v, int k, int& valor) {
// TODO:
// 1. se k < 1 ou k > v.size(), devolva false.
// 2. cole aqui o bubble sort do ex05 como funcao auxiliar e ordene "v"
// (que e a sua copia, nao o vector do chamador).
// 3. escreva v[k - 1] em "valor" e devolva true.
return false;
}
// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
std::vector<int> v = {7, 3, 9, 1};
int r = 0;
assert(k_esimo_menor(v, 1, r));
assert(r == 1);
assert(k_esimo_menor(v, 2, r));
assert(r == 3);
assert(k_esimo_menor(v, 3, r));
assert(r == 7);
assert(k_esimo_menor(v, 4, r));
assert(r == 9);
// k fora do intervalo: devolve false e nao mexe no parametro de saida
r = 99;
assert(!k_esimo_menor(v, 0, r));
assert(!k_esimo_menor(v, 5, r));
assert(!k_esimo_menor(v, -1, r));
assert(r == 99);
// o vector de quem chamou NAO pode ter sido ordenado
assert((v == std::vector<int>{7, 3, 9, 1}));
// repetidos ocupam posicoes proprias
assert(k_esimo_menor({5, 1, 5}, 2, r));
assert(r == 5);
assert(k_esimo_menor({5, 1, 5}, 3, r));
assert(r == 5);
// negativos
assert(k_esimo_menor({-2, -9, 0}, 1, r));
assert(r == -9);
// um elemento so
assert(k_esimo_menor({42}, 1, r));
assert(r == 42);
// vector vazio: qualquer k esta fora do intervalo
std::vector<int> vazio;
assert(!k_esimo_menor(vazio, 1, r));
std::cout << "Todos os testes passaram!\n";
return 0;
}
ex10¶
Escreva todos_aprovados, que recebe um std::vector<double> de notas e devolve true se todas forem >= 6.0.
Percorra o vector à mão, com for e if — as funções de <algorithm> só entram no capítulo 8.
Repare no caso do vector vazio: se não há nenhuma nota, também não há nenhum reprovado.
todos_aprovados({7.0, 8.5, 6.0}) // -> true
todos_aprovados({7.0, 5.9}) // -> false
todos_aprovados({}) // -> true (vazio: nao ha reprovado)
// 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 todas as notas forem >= 6.0.
// Escreva com laco: nada de <algorithm> nesta avaliacao.
bool todos_aprovados(const std::vector<double>& notas);
#endif
// ============================================================
// ESCREVA SUA SOLUCAO AQUI
// ============================================================
bool todos_aprovados(const std::vector<double>& notas) {
// TODO: percorra as notas. Assim que achar uma menor que 6.0, ja pode
// devolver false. Se o laco terminar sem achar nenhuma, devolva true.
return false;
}
// ============================================================
// NAO ALTERE — testes
// ============================================================
int main() {
assert(todos_aprovados({7.0, 8.5, 6.0}));
assert(!(todos_aprovados({7.0, 5.9})));
assert(todos_aprovados({}));
std::cout << "Todos os testes passaram!\n";
return 0;
}