Simulado — Avaliação 1¶
Este simulado tem o mesmo formato da Avaliação 1 de verdade: manuscrito, 90 minutos, uma questão de leitura de código e quatro de escrever função, cobrindo as Unidades 1 e 2 (capítulos 1 a 6). Veja as regras da Avaliação 1 para peso, consulta e critério de correção.
Como usar este simulado
Resolva no papel, com um cronômetro de 90 minutos e só a sua folha de consulta ao lado. Resistir à tentação de digitar é o ponto: escrever código à mão é mais lento, e é exatamente essa diferença que você quer descobrir aqui, e não na prova.
Cada questão traz a resposta logo abaixo, recolhida. Só abra depois de ter escrito a sua.
Sem <algorithm>
Nada de std::sort, std::find, std::count_if ou std::accumulate — eles só aparecem no capítulo 8. Aqui tudo se resolve com for, if e o que você já viu até o capítulo 6.
Questão 1 — Leitura de código¶
Leia a função abaixo.
std::vector<int> misterio(const std::vector<int>& v) {
std::vector<int> r;
for (std::size_t i = 0; i < v.size(); i++) {
int soma = 0;
for (std::size_t j = 0; j <= i; j++) {
soma += v[j];
}
r.push_back(soma);
}
return r;
}
a) O que misterio({4, -1, 3, 2, 5}) devolve? Escreva o vector completo.
b) Em uma frase, o que essa função faz?
c) Ela faz mais trabalho do que o necessário. Quantas somas (soma += ...) são executadas ao todo para um vector de 5 elementos? E como obter exatamente o mesmo resultado percorrendo o vector uma vez só? Escreva o laço.
Resposta
a) {4, 3, 6, 8, 13}.
Cada posição acumula tudo que veio antes: 4, depois 4 + (-1) = 3, depois 3 + 3 = 6, 6 + 2 = 8, 8 + 5 = 13. O -1 serve de armadilha: quem responde somando só valores positivos erra da segunda posição em diante.
b) Devolve as somas acumuladas do vector: cada posição i do resultado contém a soma de todos os elementos de v da posição 0 até i. (Dizer "soma parcial", "soma corrida" ou "total até ali" é a mesma resposta.)
c) São 15 somas: o laço de dentro roda 1 vez, depois 2, 3, 4 e 5 — e 1+2+3+4+5 = 15. Para 10 elementos seriam 55, e o custo cresce muito mais rápido que o tamanho do vector, porque a cada posição a função recomeça a somar do zero tudo que já tinha somado antes.
O desperdício some ao guardar o total acumulado entre as voltas, em vez de recalculá-lo:
std::vector<int> acumuladas(const std::vector<int>& v) {
std::vector<int> r;
int soma = 0;
for (int x : v) {
soma += x;
r.push_back(soma);
}
return r;
}
Agora são 5 somas para 5 elementos — uma por elemento.
Questão 2 — conta_palavras¶
Escreva conta_palavras, que recebe uma frase e devolve quantas palavras ela tem. Palavras são separadas por um ou mais espaços.
Trate estes casos:
- espaços repetidos entre palavras contam como um separador só;
- a frase pode começar e/ou terminar com espaço;
- frase vazia (ou só com espaços) tem
0palavras.
conta_palavras("o rato roeu a roupa") // -> 5
conta_palavras(" espacos demais ") // -> 2
conta_palavras("") // -> 0
Resposta
A ideia é não contar espaços nem letras, e sim começos de palavra: uma palavra começa quando um caractere não-espaço aparece logo depois de um espaço (ou no início da frase). Guardar se estamos "dentro" de uma palavra resolve tudo de uma vez.
int conta_palavras(const std::string& frase) {
int total = 0;
bool dentro = false;
for (std::size_t i = 0; i < frase.size(); i++) {
if (frase[i] != ' ') {
if (!dentro) { // comecou uma palavra nova
total++;
dentro = true;
}
} else {
dentro = false; // saiu da palavra
}
}
return total;
}
Erro comum: contar espaços e somar 1. Isso dá a resposta certa só quando há exatamente um espaço entre palavras e nenhum nas pontas — ou seja, erra os três casos que o enunciado pediu para tratar.
Questão 3 — media_sem_extremos¶
Escreva media_sem_extremos, que devolve a média das notas descartando a maior e a menor, para reduzir o peso de um extremo isolado.
- Se o vector tiver menos de 3 elementos, não sobra nada para calcular: devolva
falsee não mexa emmedia. - Descarte uma ocorrência da maior e uma ocorrência da menor. Com
{5, 5, 5, 5}, sobram dois5e a média é5— não se descartam todos os valores empatados. - Com exatamente 3 elementos sobra um só, e a média é ele mesmo.
double m;
media_sem_extremos({10.0, 2.0, 6.0}, m) // -> true, e m vale 6.0
media_sem_extremos({1.0, 2.0, 3.0, 4.0}, m) // -> true, e m vale 2.5
media_sem_extremos({1.0, 2.0}, m) // -> false
Resposta
Não é preciso ordenar nem copiar o vector: basta uma passada guardando soma, maior e menor, e então tirar os dois extremos da soma. Como se descarta uma ocorrência de cada, a divisão é sempre por n - 2.
bool media_sem_extremos(const std::vector<double>& v, double& media) {
if (v.size() < 3) {
return false;
}
double soma = v[0];
double maior = v[0];
double menor = v[0];
for (std::size_t i = 1; i < v.size(); i++) {
soma += v[i];
if (v[i] > maior) maior = v[i];
if (v[i] < menor) menor = v[i];
}
media = (soma - maior - menor) / (static_cast<int>(v.size()) - 2);
return true;
}
Erros comuns:
- inicializar
maiorcom0em vez dev[0]— quebra se todas as notas forem negativas (é a armadilha do capítulo 5); - devolver
0ou-1no caso de menos de 3 elementos, em vez defalse: uma média de-1é um resultado perfeitamente possível, e quem chamou não teria como distinguir os dois casos; - dividir por
v.size()em vez dev.size() - 2.
Questão 4 — eh_anagrama¶
Duas palavras são anagramas quando uma é feita exatamente com as letras da outra, em outra ordem. Escreva eh_anagrama, que devolve true nesse caso.
Para simplificar, as duas strings contêm apenas letras minúsculas de a a z, sem espaços nem acentos.
- Tamanhos diferentes →
false, sem nem olhar as letras. - Duas strings vazias →
true.
eh_anagrama("amor", "roma") // -> true
eh_anagrama("aab", "abb") // -> false
eh_anagrama("abc", "ab") // -> false
Resposta
Não basta ver se toda letra de uma aparece na outra: é preciso comparar quantas vezes cada letra aparece — é o que separa "aab" de "abb". Um map<char, int> conta isso naturalmente.
O truque é contar +1 para a primeira palavra e -1 para a segunda: se forem anagramas, tudo se cancela e todos os contadores terminam em zero.
bool eh_anagrama(const std::string& a, const std::string& b) {
if (a.size() != b.size()) {
return false;
}
std::map<char, int> contagem;
for (char c : a) contagem[c]++;
for (char c : b) contagem[c]--;
for (const auto& [letra, n] : contagem) {
if (n != 0) {
return false;
}
}
return true;
}
Montar dois maps e comparar com ma == mb também está correto e vale a questão inteira.
Erro comum: esquecer a checagem de tamanho e confiar só na contagem — sem ela, "aa" e "aaa" passariam pelo laço final com o contador de a diferente de zero, o que por acaso funciona aqui, mas a checagem torna a intenção explícita e evita trabalho à toa.
Questão 5 — resultado_para¶
Dadas as declarações abaixo:
struct Partida {
std::string casa;
int gols_casa;
std::string fora;
int gols_fora;
};
enum class Resultado { Vitoria, Empate, Derrota };
escreva resultado_para, que devolve o resultado da partida do ponto de vista do time informado.
Pode assumir que o time informado jogou essa partida — ou em casa, ou fora.
Partida p{"Sao Paulo", 2, "Santos", 1};
resultado_para(p, "Sao Paulo") // -> Resultado::Vitoria
resultado_para(p, "Santos") // -> Resultado::Derrota
Resposta
A questão toda está em perceber que "meus gols" e "gols deles" trocam de lado conforme o time tenha jogado em casa ou fora. Resolvido isso, a comparação é trivial — e é por isso que vale a pena separar os dois passos, em vez de escrever quatro if encadeados comparando tudo com tudo.
Resultado resultado_para(const Partida& p, const std::string& time) {
int meus;
int deles;
if (p.casa == time) {
meus = p.gols_casa;
deles = p.gols_fora;
} else {
meus = p.gols_fora;
deles = p.gols_casa;
}
if (meus > deles) return Resultado::Vitoria;
if (meus == deles) return Resultado::Empate;
return Resultado::Derrota;
}
Erros comuns:
- comparar sempre
gols_casacomgols_forae esquecer de inverter a perspectiva — a função acerta o time da casa e erra o visitante em todos os jogos; - escrever
return Vitoria;sem oResultado::. Comenum classo nome mora dentro do tipo, e sem o qualificador não compila.