Español
English
中文 (中国)
العربية
हिन्दी
Русский
Français
Deutsch
Ελληνικά
Italiano
日本語
한국어
LatineResumo
Esta aula abre a sexta unidade do curso, dedicada aos dados compostos. Explica para que serve a unidade: ensinar a representar coleções de dados (sequências de tamanho fixo e variável, tabelas e registros) e a processá-las com os algoritmos básicos, escritos à mão e tomados da biblioteca, estimando quanto custam; apresenta suas seis aulas e o fio que as une; recorda o que a unidade dá por sabido, sobretudo os laços com invariante e a passagem por referência constante; formula o problema que a unidade resolve, o de um programa que deve guardar dados cuja quantidade não conhece e que, escrito com variáveis soltas, cala em silêncio os que lhe sobram; antecipa o custo como segunda medida de um algoritmo, ao lado de sua correção; e mostra aonde conduz, nas unidades seguintes e no curso Programação em C++ II.
Objetivos de aprendizagem
- Descrever a sequência de conteúdos da unidade e explicar o que cada aula traz à seguinte.
- Recordar os laços, seus invariantes e a passagem de parâmetros (por valor, por referência e por referência constante), e revisá-los se for necessário.
- Antecipar, com um exemplo, o custo de um algoritmo como segunda medida de sua qualidade, ao lado de sua correção.
- Reconhecer o que se espera saber fazer ao terminar a unidade, e distingui-lo do que se aprenderá nas unidades seguintes.
Avaliação de entrada
Antes de percorrer a unidade, convém medir o ponto de partida. Esta avaliação é uma autoavaliação: não se pontua, e seu único propósito é orientar o estudo. As quatro primeiras perguntas verificam o que a unidade dá por sabido: o invariante do laço que busca um máximo, o modo de passagem de um parâmetro grande, o número de iterações de dois laços aninhados e a aritmética sem sinal. As seis seguintes tocam, na ordem das aulas, as ideias centrais da unidade: os índices válidos de uma sequência, a criação de um vetor, o número de vezes que um tamanho pode ser dividido pela metade, a busca em dados ordenados, o duplo índice de uma tabela e o perigo de guardar em coleções separadas os dados de uma mesma entidade. Ninguém é obrigado a acertá-las ainda, e em algumas delas “ainda não sei” é uma resposta honesta: cada resposta, certa ou não, explica o ponto e nomeia a aula que o trata. As mesmas habilidades voltam a ser medidas no final, na aula de síntese.
Antes de começar a unidade, meça seu ponto de partida. É uma autoavaliação breve: não recebe nota e seu resultado fica guardado apenas no seu navegador.
Pergunta 1De unidades anterioresO fragmento
int largest{0}; int t{}; while (std::cin >> t) { if (t > largest) { largest = t; } }deve deixar emlargesta maior das temperaturas lidas. Com que entrada ele falha?A primeira iteração compara o dado com 0 e o guarda se for positivo: com um só dado positivo o resultado é correto. Convém seguir o rastreamento antes de responder.Com>um dado igual ao máximo não o substitui, mas o máximo é o mesmo número: a repetição não altera o resultado.Revela que não se conferiu a inicialização com o invariante: um laço correto exige que o invariante valha antes da primeira iteração.O invariante desejado, “largesté o máximo do que foi lido até agora”, não vale no começo, porque antes de ler nada não há máximo, e o 0 inicial ganha de todo dado negativo. Corrige-se inicializando com o primeiro dado, depois de verificar que ele existe. A aula Vetores faz o mesmo sobre uma sequência guardada, e a biblioteca o expressa comstd::ranges::max, cuja pré-condição é que a sequência não esteja vazia.Revisar: Projetar laços corretos
Pergunta 2De unidades anterioresUma função calcula quantas vogais tem um texto de um milhão de caracteres, guardado em um
std::string, e não o modifica. Como convém declarar seu parâmetro?A passagem por valor copia o milhão de caracteres em cada chamada: é correta, mas paga um custo que não traz nada.Não copia, mas permite modificar o texto sem necessidade e não aceita um literal nem um temporário: confunde “não copiar” com “permitir modificar”.O modo de passagem faz parte da interface: a passagem por valor promete à função uma cópia própria, e o programa deve fazê-la.A referência constante lê o texto sem copiá-lo e sem permissão para modificá-lo, e admite além disso um temporário. Na unidade 6 essa escolha se torna a regra: uma função que lê um vetor de um milhão de dados o recebe comoconst std::vector<int>&, e a cópia desnecessária se converte no erro de custo mais frequente.Revisar: Parâmetros e escopo
Pergunta 3De unidades anterioresQuantas vezes se executa
++countemfor (int i{0}; i < 6; ++i) { for (int j{0}; j < i; ++j) { ++count; } }?Resposta correta:
O laço interno dá 0 iterações com , uma com , e assim até 5 com : no total , que é . A aula O custo de um algoritmo generaliza a conta: dois laços que percorrem todos os pares de dados dão iterações, e esse número decide se um algoritmo serve para um milhão de dados.Revisar: Laços
Pergunta 4De unidades anterioresO que escreve
std::println("{}", 0u - 1);em um sistema comunsigned intde 32 bits?Acredita que um tipo sem sinal admite negativos.Acredita que a subtração para no menor valor do tipo; a aritmética sem sinal dá a volta, não satura.Confunde um aviso possível com um erro: a expressão é válida e seu valor está definido.A aritmética sem sinal é modular: subtrair 1 de 0 dá a volta até o maior valor do tipo, . A unidade 6 mede os tamanhos comstd::size_t, que também é sem sinal, de modo quev.size() - 1com um vetor vazio não dá , mas um número enorme; a aula Arranjos adverte sobre essa subtração, e a aula Vetores mostra o laço que, por causa dela, sai dos limites.Revisar: Os inteiros e sua representação
Pergunta 5Em uma sequência de elementos numerados como em C++, que índices designam um elemento?
Numera a partir de um, como na linguagem comum; em C++,a[n]já está fora da sequência.É o erro de um a mais mais frequente: conta índices para elementos.É uma resposta honesta: a aula 6.1 o explica, com a razão pela qual se conta a partir de zero.O índice de C++ conta a partir de zero, porque é o deslocamento a partir do primeiro elemento: o primeiro éa[0]e o últimoa[n - 1]. Acessar com[]um índice fora desse intervalo é comportamento indefinido, e a aula Arranjos ensina a demonstrar, com o invariante do laço, que cada acesso é válido.Revisar: Arranjos
Pergunta 6O que contém
vdepois destd::vector<int> v(3, 7);?Lê os parênteses como se fossem chaves.Inverte o papel dos dois números.É uma resposta honesta: a aula 6.2 apresenta o vetor e suas formas de criação.Com parênteses, o primeiro número é a quantidade e o segundo o valor de cada elemento; com chaves,std::vector<int> v{3, 7};é a lista dos elementos, o 3 e o 7. O vetor é o primeiro tipo do curso em que as chaves e os parênteses dizem coisas distintas, e a aula Vetores o mostra com um programa.Revisar: Vetores
Pergunta 7Quantas iterações dá
for (int m{1024}; m > 1; m /= 2) { ... }?Resposta correta:
Os valores demno começo de cada iteração são 1024, 512, 256, 128, 64, 32, 16, 8, 4 e 2: dez iterações, porque , e dez é . Um algoritmo que reduz seu problema à metade a cada passo faz da ordem de passos, e a aula O custo de um algoritmo o chama de logarítmico: com um bilhão de dados bastam-lhe uns trinta.Revisar: O custo de um algoritmo
Pergunta 8Uma lista telefônica tem um milhão de nomes em ordem alfabética. Para encontrar um, ela é aberta ao meio, descarta-se a metade onde o nome não pode estar, e repete-se com a outra. Quantas vezes, no máximo, é preciso abri-la?
É a conta da busca que examina os nomes um por um: sem aproveitar a ordem, em média se percorre a metade da lista.É a raiz quadrada de um milhão: confunde dividir o trecho pela metade com dividi-lo em blocos.Usa o logaritmo decimal: cada abertura descarta a metade, não nove décimos.Cada abertura reduz à metade o trecho onde o nome pode estar, e supera o milhão: após vinte metades resta um só nome. É a busca binária da aula Buscar e ordenar, que só funciona se os dados estiverem ordenados e que se justifica com um invariante.Revisar: Buscar e ordenar
Pergunta 9Com
std::vector<std::vector<int>> t{{1, 2, 3}, {4, 5, 6}};, quanto valemt[1][0]et.size()?Lê o primeiro índice como coluna e conta as colunas em vez das linhas.Acredita quesize()conta todas as células da tabela.É uma resposta honesta: a aula 6.5 apresenta as tabelas como vetores de vetores.Pergunta 10Um programa guarda os nomes de uma turma em um vetor e suas notas em outro, de modo que a nota
grades[i]é a denames[i]. Se ordenar só o vetor das notas, o que acontece?Para o compilador os dois vetores são independentes: a relação existe só na mente de quem escreveu o programa.O algoritmo recebe um só vetor e não sabe da existência do outro.Todo acesso é válido e todo resultado está definido: o defeito é de lógica, e por isso não o informa nenhum dos dois detectores do curso (o de erros de memória, AddressSanitizer, e o de comportamento indefinido, UndefinedBehaviorSanitizer).
Carregando o conteúdo…