Español
English
Português
中文 (中国)
العربية
हिन्दी
Русский
Français
Deutsch
Ελληνικά
日本語
한국어
LatineRiepilogo
Questa lezione apre la sesta unità del corso, dedicata ai dati composti. Spiega a che cosa serve l’unità: insegnare a rappresentare collezioni di dati (sequenze di dimensione fissa e variabile, tabelle e record) e a elaborarle con gli algoritmi di base, scritti a mano e presi dalla libreria, stimando quanto costano; presenta le sue sei lezioni e il filo che le unisce; ricorda ciò che l’unità dà per scontato, soprattutto i cicli con invariante e il passaggio per riferimento costante; formula il problema che l’unità risolve, quello di un programma che deve conservare dati di cui non conosce la quantità e che, scritto con variabili sciolte, tace in silenzio quelli in eccesso; anticipa il costo come seconda misura di un algoritmo, accanto alla sua correttezza; e mostra dove conduce, nelle unità successive e nel corso Programmazione in C++ II.
Obiettivi di apprendimento
- Descrivere la sequenza dei contenuti dell’unità e spiegare che cosa apporta ciascuna lezione alla successiva.
- Ricordare i cicli, i loro invarianti e il passaggio dei parametri (per valore, per riferimento e per riferimento costante), e ripassarli se occorre.
- Anticipare, con un esempio, il costo di un algoritmo come seconda misura della sua qualità, accanto alla sua correttezza.
- Riconoscere che cosa ci si aspetta di saper fare al termine dell’unità, e distinguerlo da ciò che si imparerà nelle unità successive.
Valutazione d’ingresso
Prima di percorrere l’unità conviene misurare il punto di partenza. Questa valutazione è un’autovalutazione: non ha voto, e il suo unico scopo è orientare lo studio. Le prime quattro domande verificano ciò che l’unità dà per scontato: l’invariante del ciclo che cerca un massimo, la modalità di passaggio di un parametro grande, il numero di iterazioni di due cicli annidati e l’aritmetica senza segno. Le sei successive toccano, nell’ordine delle lezioni, le idee centrali dell’unità: gli indici validi di una sequenza, la creazione di un vettore, il numero di volte che una dimensione si può dividere a metà, la ricerca in dati ordinati, il doppio indice di una tabella e il pericolo di conservare in collezioni separate i dati di una stessa entità. Nessuno è tenuto a indovinarle già, e in alcune di esse «non lo so ancora» è una risposta onesta: ogni risposta, giusta o no, spiega il punto e nomina la lezione che lo tratta. Le stesse abilità si misurano di nuovo alla fine, nella lezione di sintesi.
Prima di iniziare l’unità, misura il tuo punto di partenza. È un’autovalutazione breve: non riceve voto e il risultato resta solo nel tuo browser.
Domanda 1Dalle unità precedentiIl frammento
int largest{0}; int t{}; while (std::cin >> t) { if (t > largest) { largest = t; } }deve lasciare inlargestla più alta delle temperature lette. Con quale input fallisce?La prima iterazione confronta il dato con 0 e lo conserva se è positivo: con un solo dato positivo il risultato è corretto. Conviene seguire la traccia prima di rispondere.Con>un dato uguale al massimo non lo sostituisce, ma il massimo è lo stesso numero: la ripetizione non altera il risultato.Rivela che non si è controllata l’inizializzazione con l’invariante: un ciclo corretto esige che l’invariante valga prima della prima iterazione.L’invariante voluto, «largestè il massimo di ciò che si è letto finora», non vale all’inizio, perché prima di leggere qualcosa non c’è massimo, e lo 0 iniziale batte ogni dato negativo. Si corregge inizializzando con il primo dato, dopo aver verificato che esiste. La lezione Vettori fa lo stesso su una sequenza conservata, e la libreria lo esprime constd::ranges::max, la cui precondizione è che la sequenza non sia vuota.Ripassare: Progettare cicli corretti
Domanda 2Dalle unità precedentiUna funzione calcola quante vocali ha un testo di un milione di caratteri, conservato in uno
std::string, e non lo modifica. Come conviene dichiarare il suo parametro?Il passaggio per valore copia il milione di caratteri a ogni chiamata: è corretto, ma paga un costo che non apporta nulla.Questa dichiarazione non copia, ma permette di modificare il testo senza necessità e non accetta né un letterale né un temporaneo: la risposta confonde «non copiare» con «permettere di modificare».La modalità di passaggio fa parte dell’interfaccia: il passaggio per valore promette alla funzione una copia propria, e il programma deve farla.Il riferimento costante legge il testo senza copiarlo e senza il permesso di modificarlo, e ammette inoltre un temporaneo. Nell’unità 6 questa scelta diventa la regola: una funzione che legge un vettore di un milione di dati lo riceve comeconst std::vector<int>&, e la copia inutile diventa l’errore di costo più frequente.Ripassare: Parametri e ambito di visibilità
Domanda 3Dalle unità precedentiQuante volte si esegue
++countinfor (int i{0}; i < 6; ++i) { for (int j{0}; j < i; ++j) { ++count; } }?Risposta corretta:
Il ciclo interno fa 0 iterazioni con , una con , e così via fino a 5 con : in totale , cioè . La lezione Il costo di un algoritmo generalizza il conto: due cicli che percorrono tutte le coppie di dati fanno iterazioni, e questo numero decide se un algoritmo serve per un milione di dati.Ripassare: Cicli
Domanda 4Dalle unità precedentiChe cosa scrive
std::println("{}", 0u - 1);in un sistema conunsigned intdi 32 bit?Crede che un tipo senza segno ammetta valori negativi.Crede che la sottrazione si fermi al valore minimo del tipo; l’aritmetica senza segno ricomincia dall’altro estremo, non si satura.Confonde un avviso possibile con un errore: l’espressione è valida e il suo valore è definito.L’aritmetica senza segno è modulare: sottrarre 1 da 0 ricomincia dall’altro estremo, il valore massimo del tipo, . L’unità 6 misura le dimensioni constd::size_t, anch’esso senza segno, sicchév.size() - 1con un vettore vuoto non dà , ma un numero enorme; la lezione Array mette in guardia da questa sottrazione, e la lezione Vettori mostra il ciclo che, a causa sua, esce dai limiti.Ripassare: Gli interi e la loro rappresentazione
Domanda 5In una sequenza di elementi numerati come in C++, quali indici designano un elemento?
Numera da uno, come nel linguaggio comune; in C++,a[n]è già fuori dalla sequenza.È l’errore di uno più frequente: conta indici per elementi.È una risposta onesta: la lezione 6.1 lo spiega, con la ragione per cui si conta da zero.L’indice di C++ conta da zero, perché è l’offset dal primo elemento: il primo èa[0]e l’ultimoa[n - 1]. Accedere con[]a un indice fuori da questo intervallo è comportamento indefinito, e la lezione Array insegna a dimostrare, con l’invariante del ciclo, che ogni accesso è valido.Ripassare: Array
Domanda 6Che cosa contiene
vdopostd::vector<int> v(3, 7);?Legge le parentesi tonde come se fossero graffe.Inverte il ruolo dei due numeri.È una risposta onesta: la lezione 6.2 presenta il vettore e i suoi modi di creazione.Con le parentesi tonde, il primo numero è la quantità e il secondo il valore di ciascun elemento; con le graffe,std::vector<int> v{3, 7};è la lista degli elementi, il 3 e il 7. Il vettore è il primo tipo del corso in cui le graffe e le tonde dicono cose diverse, e la lezione Vettori lo mostra con un programma.Ripassare: Vettori
Domanda 7Quante iterazioni fa
for (int m{1024}; m > 1; m /= 2) { ... }?Risposta corretta:
I valori dimall’inizio di ogni iterazione sono 1024, 512, 256, 128, 64, 32, 16, 8, 4 e 2: dieci iterazioni, perché , e dieci è . Un algoritmo che riduce il suo problema alla metà a ogni passo fa dell’ordine di passi, e la lezione Il costo di un algoritmo lo chiama logaritmico: con un miliardo di dati gliene bastano una trentina.Ripassare: Il costo di un algoritmo
Domanda 8Un elenco telefonico ha un milione di nomi in ordine alfabetico. Per trovarne uno, lo si apre a metà, si scarta la metà in cui il nome non può stare, e si ripete con l’altra. Quante volte, al massimo, bisogna aprirlo?
È il conto della ricerca che esamina i nomi uno per uno: senza sfruttare l’ordine, in media si percorre metà dell’elenco.È la radice quadrata di un milione: confonde dividere il tratto a metà con dividerlo in blocchi.Usa il logaritmo decimale: ogni apertura scarta la metà, non nove decimi.Ogni apertura riduce alla metà il tratto in cui può stare il nome, e supera il milione: dopo venti dimezzamenti resta un solo nome. È la ricerca binaria della lezione Cercare e ordinare, che funziona solo se i dati sono ordinati e che si giustifica con un invariante.Ripassare: Cercare e ordinare
Domanda 9Con
std::vector<std::vector<int>> t{{1, 2, 3}, {4, 5, 6}};, quanto valgonot[1][0]et.size()?Legge il primo indice come colonna e conta le colonne invece delle righe.Crede chesize()conti tutte le celle della tabella.È una risposta onesta: la lezione 6.5 presenta le tabelle come vettori di vettori.Domanda 10Un programma conserva i nomi di un gruppo in un vettore e i loro voti in un altro, in modo che il voto
grades[i]sia quello dinames[i]. Se ordina solo il vettore dei voti, che cosa succede?Per il compilatore i due vettori sono indipendenti: la relazione esiste solo nella mente di chi ha scritto il programma.L’algoritmo riceve un solo vettore e non sa dell’esistenza dell’altro.Ogni accesso è valido e ogni risultato è definito: il difetto è di logica, e per questo non lo segnala nessuno dei due sanitizer del corso (quello degli errori di memoria, AddressSanitizer, e quello del comportamento indefinito, UndefinedBehaviorSanitizer).
Caricamento del contenuto…