#Concetti base di programmazione in C++Prima di cominciare a risolvere effettivamente i problemi, dobbiamo possedere alcune conoscenze di base di programmazione. In questa guida assumeremo che il lettore conosca già i principali costrutti della programmazione (variabili, cicli, funzioni e istruzioni if/else).
Consigliamo di scrivere il codice in C++ per diversi motivi:
1.la libreria standard del C++ offre una vasta collezione di strutture dati e algoritmi pronti all’uso;2.è un linguaggio efficiente e permette, quando necessario, di controllare in modo granulare l’uso della memoria;3.è l’unico linguaggio ammesso alla finale OII e dalla maggior parte delle competizioni internazionali.Il file C++ più semplice (e inutile) che possiamo scrivere è il seguente:
int main() {
return 0;
}
int main() è il punto di ingresso del nostro programma. La funzione main restituisce un int: questo valore è il codice di uscita. Per convenzione, 0 indica la terminazione corretta, mentre un valore diverso da 0 segnala un’anomalia. Se l’esecuzione raggiunge la fine di main senza incontrare un’istruzione return, in C++ viene restituito automaticamente 0.
Questo programma per ora non produce alcun output. Proviamo a stampare una stringa di testo, per esempio Ciao Dario!.
#include <iostream>
using namespace std;
int main() {
cout << "Ciao Dario!" << endl;
return 0;
}
In C++ le varie dichiarazioni delle librerie vanno incluse nella compilazione tramite la keyword #include. La maggior parte delle dichiarazioni della libreria standard appartiene al namespace std. L’istruzione using namespace std; permette di usarle senza dover scrivere ogni volta il prefisso std::.
cout (abbr. di “character output”) scrive sullo stream standard di output. endl inserisce un carattere di fine riga e svuota il buffer associato allo stream.
Nota: in futuro useremo spesso '\n' al posto di endl, perché inserisce una nuova riga senza forzare lo svuotamento del buffer, operazione solitamente molto lenta. Il buffer viene comunque svuotato automaticamente, per esempio quando è pieno o quando lo stream viene chiuso.
Ora che abbiamo scritto il nostro programma, è giunto il momento di compilarlo! Per compilare il sorgente ci sono due modi principali:
1.Tramite l’IDE in cui stiamo lavorando è spesso possibile compilare ed eseguire il programma premendo un tasto (o una combinazione di tasti). Ad esempio, su Visual Studio Code F5, su Code::Blocks F9, su Dev-C++ F11.
Lo staff delle OII ha messo a disposizione un IDE online (https://editor.olinfo.it) per compilare ed eseguire il codice senza installare nulla sul proprio computer. Per quanto questo IDE sia comodo all’inizio, è consigliabile installare un IDE sul proprio computer per svariate ragioni, tra cui la possibilità di fare debugging in maniera più efficace e il fatto che l’editor online non sarà disponibile durante la finale delle OII.
2.(Consigliato) Tramite terminale si può avere un controllo più granulare sulla compilazione (che, come vedremo nel capitolo sul debugging, può tornare molto utile).
•Windows: Possiamo installare g++ tramite MinGW o MSYS2. Compiliamo il sorgente cong++ ilnomedeltuofile.cpp
Nella cartella comparirà un file chiamato a.exe, che possiamo eseguire tramite il comando
./a
•Linux: Tramite il package manager del sistema possiamo direttamente installare g++, appartenente al pacchetto gcc (Es. su Arch Linux, sudo pacman -S gcc). Compiliamo tramiteg++ ilnomedeltuofile.cpp
Nella cartella comparirà un file chiamato a.out, che possiamo eseguire tramite il comando
./a.out
#EsempiVediamo altri esempi. Il seguente programma legge prima un intero 𝑛, poi 𝑛 interi 𝑎0,…,𝑎𝑛−1 e li stampa in ordine inverso.
#include <vector>
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = n - 1; i >= 0; --i)
cout << a[i] << " ";
cout << "\n";
}
cin è lo stream di input standard del C++ ed è la controparte di cout. L’operatore >> (diverso da quello del cout, <<) legge i dati dallo stream, ignorando automaticamente gli spazi bianchi iniziali. L’istruzione vector<int> a(n) costruisce un vector di n elementi di tipo int. Gli elementi vengono poi letti uno alla volta nel ciclo for. Infine, un ciclo for percorre il vettore al contrario, dagli indici n - 1 a 0, e cout ne stampa gli elementi.
Vediamo ora un esempio leggermente più articolato:
#include <iostream>
#include <cstdio>
using namespace std;
void solve() {
int a;
cin >> a;
int b;
cin >> b;
cout << a + b << "\n";
}
int main() {
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int T;
cin >> T;
for (int caso = 1; caso <= T; caso++) {
cout << "Case #" << caso << ": ";
solve();
}
}
freopen(file, mode, stream) dirotta lo stream specificato e lo associa al file. Se mode è "r" (read), il file viene aperto per la lettura; se è "w" (write), viene aperto per la scrittura e il suo contenuto precedente viene sovrascritto. In questo caso il programma reindirizza l’input standard verso input.txt e l’output standard verso output.txt. Di conseguenza, le operazioni su cin e cout usano rispettivamente quei due file. Questo è il formato standard di input/output per la fase territoriale.
Oltre a main, abbiamo definito la funzione void solve(). Una funzione di tipo void non restituisce un valore; può terminare raggiungendo la fine delle istruzioni oppure eseguendo return;. Una funzione con un tipo di ritorno diverso da void deve invece restituire sempre un valore del tipo corretto tramite return <valore>;, altrimenti il comportamento è indefinito.
Una funzione può anche chiamare se stessa; in questo caso si dice che è ricorsiva. Implementiamo quindi una funzione ricorsiva di tipo int per il calcolo del fattoriale1 di un numero naturale 𝑛, definito come 𝑛!=1⋅2⋅…⋅𝑛=𝑛⋅(𝑛−1)! per 𝑛>0, ponendo 0!=1.
int fact(int n) {
if (n == 0)
return 1;
return n * fact(n - 1);
}
Secondo te cosa accadrebbe se non inserissi il caso base per 𝑛=0 nella definizione di fact? E se chiamassi fact(-1)?
Per ora abbiamo usato solo int, ma non è l’unico tipo di variabile. Presentiamo un breve elenco dei tipi più comunemente usati:
Tipo
Byte
Dettagli
char
1
Un singolo carattere.
bool
1
Un valore booleano: true oppure false.
int
4
Un intero; tipicamente da −231 a 231−1 (circa 2⋅109).
long long
8
Un intero di 64 bit; tipicamente da −263 a 263−1 (circa 9⋅1018).
float
4
Numero reale con precisione singola.
double
8
Numero reale con precisione doppia.
std::string
variabile
Stringa di lunghezza variabile; la memoria dipende dal contenuto.
Cosa succede quando si provano a salvare dentro un tipo di variabile come int valori superiori a quelli massimi consentiti? Un overflow si verifica quando il risultato di un’operazione supera il valore massimo, o scende sotto il valore minimo (underflow), rappresentabile dal tipo scelto. Con gli interi con segno, il comportamento risultante è indefinito, ma solitamente genera valori spazzatura. Con gli interi senza segno (solo positivi), il risultato è quello corretto ma troncato ai bit disponibili.
In molti problemi2 la memoria massima consentita è molto generosa, quindi risulta più conveniente usare long long ovunque al posto di int per evitare questo tipo di errori. Dato che long long è più lungo da scrivere, possiamo definire un alias all’inizio del codice con using ll = long long;, così da poter usare la sintassi abbreviata ll.
#Una nota per la programmazione competitivaQuando gareggi hai un tempo limitato per scrivere le tue soluzioni. Per questo motivo è comune adottare strategie per rendere più fluida la scrittura del codice ed eventualmente ridurre il numero di caratteri necessari a esprimere lo stesso concetto. Considera il seguente esempio.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
int main() {
int n; cin >> n;
vector<ll> a(n);
for (ll& x : a)
cin >> x;
sort(all(a));
a.erase(unique(all(a)), end(a));
for (ll x : a)
cout << x << " ";
cout << "\n";
}
In questo esempio non è importante comprendere il codice riga per riga; ciò che conta è il concetto: quando si gareggia, spesso conviene abbandonare le “buone pratiche” insegnate a lezione per favorire un’implementazione più rapida ed efficiente.
#Problemi consigliati
Trova il massimo (https://training.olinfo.it/task/massimo)
Filmati e canzoni (https://training.olinfo.it/task/terry/download)
Biglietti a Milano (https://training.olinfo.it/task/ois_biglietti)
Late for work (https://training.olinfo.it/task/ois_time)
Dangerous Parkour (https://training.olinfo.it/task/ois_parkour)
1In questo caso basterebbe anche un ciclo for, altre volte la ricorsione è estremamente utile.2In alcuni problemi, rispettare il limite di memoria è la parte più complicata del problema. Ad esempio, https://training.olinfo.it/task/tai_cct2.