next up previous contents index
Next: Definizione di un array Up: Array, enumerati, stringhe Previous: Array, enumerati, stringhe   Indice   Indice analitico

Vettori

Fino ad ora abbiamo avuto a che fare con tipi primitivi, con puntatori e riferimenti; introduciamo a questo punto il primo dei tipi aggregati che incontriamo, nel nostro studio del C++. Un tipo, o più in generale una struttura dati, è detto aggregato se gli oggetti di tale tipo, contengono più oggetti; nel caso degli array gli oggetti in esso contenuti sono tutti del medesimo tipo. Cosa è dunque un array? Si tratta semplicemente di un vettore (o una matrice) di oggetti; si immagini di avere a disposizione una cassettiera, in grado di contenere solo un determinato tipo di oggetto: se i cassetti formano un'unica colonna allora abbiamo un vettore, altrimenti se essi formano una scacchiera abbiamo una matrice bidimensionale (in quanto si sviluppa su due dimensioni: altezza e larghezza). Con il termine inglese ``array'' indicheremo sia i vettori (unidimensionali) sia le matrici (pluridimensionali). Ci oppureremo per il momento solo di vettori.

Un array in definitiva è un contenitore, il quale ha l'importante caratteristica di essere indicizzato; cosa vuol dire? che possiamo accedere ad ogni cella del vettore semplicemente tramite un indice, cioè un numero che la identifichi univocamente. In C++, se un vettore ha $n$ celle, esse sono numerate da $0$ a $n-1$. Per creare vettori, dobbiamo usare un nuovo derivatore di tipo: le parentesi quadre '[]'; esempi di dichiarazioni di vettori sono le seguenti:

 int v[5] vettore di 5 interi (0-4)
 double v[7] vettore di 7 reali (0-6)
 char* v[2] vettore di 2 caratteri (0,1)
Per accedere la $x$-esima casella di un vettore, vanno usate nuovamente le parentesi quadre, all'interno delle quali è da inserire l'indice della casella da accedere. Si faccia molta attenzione a non tentare di accedere caselle che non esistono, ovvero che cadono fuori dall'intervallo da $0$ a $n-1$ del vettore; il compilatore, infatti, non avverte errori del genere, i quali risultano dunque insidiosi e difficili da rimuovere. Vediamo un semplcie esempio:

// ex6_1_1.cpp
#include <iostream.h>
void main() {
  int a[5];
  a[0] = 7; a[1] = 9;
  a[2] = 3; a[3] = -5;
  a[4] = 0;
  // a[5] = 19;   // NO! a[5] non esiste
  cout << a[0] << " " <<
    a[1] << " " <<
    a[2] << " " <<
    a[3] << " " <<
    a[4] << " ";
}

output:
7 9 3 -5 0

Ogni casella di un vettore è, nel nostro esempio, una variabile che può essere modificata o acceduta in maniera del tutto indipendente dalle altre; qual è allora il vantaggio di usare un vettore? Perché possiamo, grazie ai cicli a noi noti, accedere con poche righe di codice un numero arbitrario di dati; vediamo un esempio:


// ex6_1_4.cpp
#include <iostream.h>
#include <math.h>
void main() {
  double x[5];
  cout << "scrivi cinque numeri separati da spazi:\n";
  for (int i = 0; i < 5; i++)
    cin >> x[i];
  double p;
  cout << "potenza? "; cin >> p;
  // eleva ogni elemento del vettore alla p-esima potenza
  for (int i = 0; i < 5; i++)
    x[i] = pow (x[i], p);
  // stampa il vettore
  for (int i = 0; i < 5; i++)
    cout << x[i] << "\n";
}

esempio di output:
scrivi cinque numeri separati da spazi:
2.5 1.5 5 1 7
potenza? 3
15.625
3.375
125
1
343

Un altro esempio è il seguente, il quale calcola la media dei voti di uno studente:


// ex6_1_2.cpp
// calcola la media dei voti di uno studente
#include <iostream.h>
void main() {
  // il vettore contiene al massimo 50 voti
  const int MAX_VOTI = 50;
  double voti[MAX_VOTI];
  int i; // dichiariamo l'indice i prima
         // del for perche' ci servira
         // all'esterno di esso
  cout << "inserisci un numero negativo per terminare\n";
  for (i = 0; i < MAX_VOTI; i++) {
    double x;
    cout << "voto? "; cin >> x;
    if (x < 0)
      break;
    voti[i] = x;
  }
  // i e' il numero dei voti immessi
  // sommiamo tutti i voti
  // utilizzando un nuovo indice j
  double somma = 0;
  for (int j = 0; j < i; j++)
    somma += voti[j];
  double media = somma / i;
  cout << "la media dei voti e': " << media;
}

esempio di output:
inserisci un numero negativo per terminare
voto? 6.5
voto? 7.5
voto? 7
voto? -1
la media dei voti e': 7

Si noti che il secondo for non è streattamente necessario, in quanto avremmo potuto calcolare la somma parziale, mano a mano che l'utente inserisce i dati. In questo esempio abbiamo utilizzato una variabile costante per indicare il numero di elementi del vettore, piuttosto che una costante letterale; si tratta dei due unici tipi ammessi per la creazione di un vettore, cioè non è possibile utilizzare una variabile non costante: il compilatore deve sapere imediatamente il numero esatto degli elementi, per potere occupare il giusto quantitativo di memoria (vedremo nel prossimo capitolo il motivo). Vediamo ora un esempio che ci permette di ridurre in fattori primi un numero intero:


// ex6_1_3.cpp
// scompone in fattori primi
// numeri interi minori di MAX*MAX
#include <stdlib.h>   // contiene exit(1)
#include <math.h>
#include <iostream.h>
const int MAX = 1000;
void main() {
  int n;
  cout << "? "; cin >> n;
  if (n >= MAX*MAX)
    exit(1);   // serve per chiudere il programma
               // tornano uno stato di errore
  int fattori[MAX];
  // mettiamo ad esponente 0 tutti i fattori
  for (int i = 0; i < MAX; i++)
    fattori[i] = 0;
  int maxIndice = (int)sqrt(n) + 1;
  for (int i = 2; i < maxIndice; i++) {
    for (;;) {
      if (n % i == 0) {
        n /= i;
        fattori[i]++;
      }
      else
        break;
    }
  }
  for (int i = 2; i < maxIndice; i++) {
    if (fattori[i] != 0)
      cout << i << ": " << fattori[i] << "\n";
  }
}

esempio di output:
? 880821
3: 3
17: 1
19: 1
101: 1

Sappiamo che ogni numero intero è divisibile in modo unico (a meno dell'ordine) in fattori primi, aventi ciascuno una certa molteplicità, ovvero un esponente; il programma appena presentato non fa altro che scrivere, dato un numero intero, gli esponenti non nulli dei fattori primi nei quali esso può essere decomposto. Il nostro programma è però limitato; infatti noi utilizziamo un array per salvare gli esponenti dei fattori primi del numero, il cui numero è dipendente dal numero dato: ad esempio, per i fattori primi di $100 = 2^2 \cdot 5^2$ basterebbero due sole celle nell'array, mentre ce ne vorrebbero quattro per $120=2 \cdot 3 \cdot 4 \cdot 5$. Come possiamo sapere a priori, quante celle ci vogliono? Non possiamo, allora fissiamo il numero massimo che il programma supporta, che è contenuto nella variabile costante MAX, e che può quindi essere facilmente adattato a diverse esigenze. In realtà poi possiamo, per risparmiare spazio, creare un vettore avente un numero di celle uguale alla radice quadrata di MAX, perché sappiamo dalla teoria dei numeri (se non lo sappiamo prendiamolo per buono ...) che i fattori primi di un numero $n$ sono compresi tra $1$ e $\sqrt{n}$.

Gettate le premesse per il nostro programma, vediamo come esso funziona in pratica. La prima operazione che compiamo è quella di mettere a zero tutti gli esponenti dei fattori primi del nostro numero; successivamente proviamo uno ad uno i possibili fattori primi, tramite un ciclo da $2$ (il più piccolo numero primo) a maxIndice. Tale variabile è calcolata come la radice quadrata del numero n da scomporre; ovviamente siccome abbiamo bisogno che l'indice sia intero, dobbiamo convertire esplicitamente la radice, e sommarle una unità. All'interno del corpo di ogni ciclo, proviamo a dividere n fino a quando il resto è non-zero, per poi passare al fattore successivo. In realtà non sarebbe necessario provare tutti i numeri, perché ad esempio tolti tutti i fattori di $2$, è sicuro che fattori di $4$ non ce ne saranno, e così per tutti i multipli dei fattori già scartati. Tuttavia per semplicità possiamo tralasciare questo particolare, che influenza solo la velocità di esecuzione del programma e non i concetti su cui esso si basa. Infine si stampano tutti gli esponenti dei fattori primi di n, tranne, ovviamente, quelli nulli. Si noti, infine, che abbiamo utilizzato la funzione exit(1), la quale è contenuta nella libreria stdlib.h (il cui nome sta per STandarD LIBrary = ``libreria standard'') e provoca l'arresto immediato del programma.



Subsections
next up previous contents index
Next: Definizione di un array Up: Array, enumerati, stringhe Previous: Array, enumerati, stringhe   Indice   Indice analitico
Claudio Cicconetti
2000-09-06