Esercitazione 8 - 16/11

Indice degli esercizi

EsercizioArgomento
Esercizio 1Inversione di un array
Esercizio 2Ogni 2 è seguito da un 3
Esercizio 3Riempire un array con numeri casuali
Esercizio 4Riempire un array con numeri chiesti all'utente
Esercizio 5Copiare un array: perché non basta b = a

Esercizio 1

Ripasso: Recap 1 · Gli array (indici, length, ciclo for) e Recap 2 · Array e funzioni (regola del nuovo array).

Dato un array v, scrivere un programma che costruisca un nuovo array risultato (senza modificare v) e lo stampi.

A. risultato contiene gli stessi elementi di v in ordine inverso. Ad esempio con v = [1, 2, 3, 4] si stampa [4, 3, 2, 1].

B. In risultato gli elementi che si trovano in posizione pari (indici 0, 2, 4, ...) sono presi in ordine inverso, mentre quelli in posizione dispari restano dove sono. Ad esempio:

Provate i programmi anche con un array di un solo elemento e con l'array vuoto.

Soluzione

A lezione sono usciti tanti modi diversi di ragionare, tutti corretti: quale viene più naturale dipende da come si imposta il problema all'inizio. Qui li trovate nell'ordine in cui li abbiamo visti, con gli errori che abbiamo incontrato lungo la strada.

A · Invertire un array

Prima di tutto: come si crea risultato? Ci sono due modi.

let v = [1, 2, 3, 4];

let r1 = [];                                    // vuoto e lungo 0
let r2 = new Array(v.length);                   // vuoto ma già lungo 4

console.log(r1, r1.length);                     // [] 0
console.log(r2, r2.length);                     // [ <4 empty items> ] 4

Con new Array(v.length) le «celle» ci sono già e basta scriverci dentro; con [] le celle vanno create man mano. Sappiamo già che risultato avrà tanti elementi quanti v, quindi la seconda forma è la più naturale per questo esercizio.

A1 · Due indici che si muovono in direzioni opposte. Si scorre v dalla fine con i (da v.length - 1 fino a 0, con i--) e, intanto, si scrive in risultato dall'inizio con un secondo indice j:

let v = [1, 2, 3, 4];

let risultato = new Array(v.length);
let j = 0;                                      // dove scrivere in risultato
for (let i = v.length - 1; i >= 0; i--) {       // dove leggere in v
  risultato[j] = v[i];
  j++;
}

console.log(risultato);                         // [ 4, 3, 2, 1 ]
console.log(v);                                 // [ 1, 2, 3, 4 ]: v non è cambiato

Si legge il 4 e lo si scrive in posizione 0, poi si legge il 3 e lo si scrive in posizione 1, e così via. j non è un array: è solo il numero della cella di risultato in cui scrivere. Per vedere passo passo come cambiano i, j e le celle, provate il codice su Python Tutor.

A2 · Un solo indice e una formula. In A1 le due variabili sono legate: ogni volta che i scende di uno, j sale di uno, e vale sempre i + j == v.length - 1. Allora una delle due si può ricavare dall'altra. Si scorre risultato dall'inizio e si legge da v in posizione v.length - 1 - i:

let v = [1, 2, 3, 4];

let risultato = new Array(v.length);
for (let i = 0; i < v.length; i++) {
  risultato[i] = v[v.length - 1 - i];
}

console.log(risultato);                         // [ 4, 3, 2, 1 ]

Con i = 0 si legge v[3] (l'ultimo), con i = 1 si legge v[2] (il penultimo), con i = 3 si legge v[0]. Con una variabile in meno; A1 però si legge forse più facilmente.

A3 · Partire da [] e aggiungere in fondo. Se risultato nasce vuoto e lungo 0, si può sfruttare una proprietà di JavaScript: scrivendo in una posizione che non esiste, l'array si allunga da solo. La prima posizione libera di un array è sempre risultato.length:

let v = [1, 2, 3, 4];

let risultato = [];
for (let i = v.length - 1; i >= 0; i--) {
  risultato[risultato.length] = v[i];           // scrive nella prima cella libera
}

console.log(risultato);                         // [ 4, 3, 2, 1 ]

Il ruolo di j lo fa risultato.length, che vale 0, poi 1, poi 2... perché cresce di uno a ogni elemento aggiunto.

Due osservazioni:

B · Invertire solo le posizioni pari

Con v = [7, -1, 33, 9, 0, 5] le posizioni dispari (1, 3, 5) restano uguali, mentre i valori in posizione pari (7, 33, 0) vanno messi al contrario:

posizione:    0    1    2    3    4    5
v:          [ 7,  -1,  33,   9,   0,   5 ]
risultato:  [ 0,  -1,  33,   9,   7,   5 ]

La strategia: spezzare il problema. L'esercizio è fatto di due pezzi: copiare le posizioni dispari (facile) e invertire le posizioni pari (più difficile, ma è il punto A). Non serve scrivere un unico ciclo che fa tutto in un colpo: si risolve prima il pezzo facile, ci si assicura che funzioni, e poi ci si dedica all'altro.

B1 · Due cicli e due indici. È il ragionamento di A1 applicato ai due pezzi.

let v = [7, -1, 33, 9, 0, 5];

let risultato = new Array(v.length);

// pezzo facile: le posizioni dispari si copiano uguali
let j = 0;
for (let i = 0; i <= v.length - 1; i++) {
  if (i % 2 != 0) {
    risultato[j] = v[i];
  }
  j++;                                          // FUORI dall'if: j va di pari passo con i
}

// pezzo difficile: le posizioni pari al contrario
j = 0;                                          // si riparte dall'inizio di risultato
for (let i = v.length - 1; i >= 0; i--) {       // v letto dalla fine, come in A1
  if (i % 2 == 0) {
    risultato[j] = v[i];
    j += 2;                                     // DENTRO l'if: solo dopo aver scritto
  }
}

console.log(risultato);                         // [ 0, -1, 33, 9, 7, 5 ]

Il punto delicato è dove si aggiorna j, ed è diverso nei due cicli:

Con questo ragionamento non bisogna chiedersi se la lunghezza di v è pari o dispari: leggendo v dalla fine, il primo elemento in posizione pari che si incontra è sempre l'ultimo, e finisce in posizione 0.

B2 · Senza j: riusare la formula di A2. Si parte di nuovo dai due pezzi: un ciclo copia i dispari e un altro usa la formula di A2, ma solo sulle posizioni pari.

let risultato = new Array(v.length);
for (let i = 0; i < v.length; i++) {
  if (i % 2 != 0) {
    risultato[i] = v[i];
  }
}
for (let i = 0; i < v.length; i++) {
  if (i % 2 == 0) {
    risultato[i] = v[v.length - 1 - i];
  }
}

Rileggendo il codice ci si accorge che i due for sono identici: scorrono l'array nello stesso verso. Allora si possono fondere in uno solo, e i due if diventano un if / else, perché una posizione o è pari o è dispari:

let risultato = new Array(v.length);
for (let i = 0; i < v.length; i++) {
  if (i % 2 != 0) {
    risultato[i] = v[i];
  } else {
    risultato[i] = v[v.length - 1 - i];
  }
}

Anche lasciare due cicli andava benissimo: i programmi si scrivono a pezzi e si migliorano dopo. In B1 invece i due cicli non si potevano fondere, perché scorrono v in versi opposti.

Il problema della lunghezza pari. Con v = [7, -1, 33, 9, 0] questo codice funziona, ma con v = [7, -1, 33, 9, 0, 5] stampa [ 5, -1, 9, 9, -1, 5 ]: nelle posizioni pari sono finiti elementi che stavano in posizione dispari. Il motivo è che lo specchio parte da v.length - 1, che è una posizione pari solo se la lunghezza è dispari. Lo specchio va fatto tra le sole posizioni pari, quindi deve partire dall'ultima posizione pari:

v.lengthultima posizioneultima posizione pari
dispari (es. 5)4, pari4, cioè length - 1
pari (es. 6)5, dispari4, cioè length - 2

La correzione «a mano» (che non basta). Scrivere v[v.length - 2 - i] sistema l'array lungo 6, ma rompe quello lungo 5: con [7, -1, 33, 9, 0] si ottiene [ 9, -1, -1, 9, undefined ]. Una soluzione che funziona solo perché l'input di prova è fatto in un certo modo non è una soluzione: vogliamo un codice che vada bene per qualunque array. Le due correzioni che seguono lo fanno.

B3 · Calcolare l'ultima posizione pari con un if. Si controlla prima se la lunghezza è pari o dispari, come nella tabella:

let v = [7, -1, 33, 9, 0, 5];

let ultimoPari;
if (v.length % 2 == 1) {
  ultimoPari = v.length - 1;
} else {
  ultimoPari = v.length - 2;
}

let risultato = new Array(v.length);
for (let i = 0; i < v.length; i++) {
  if (i % 2 != 0) {
    risultato[i] = v[i];                        // le posizioni dispari non si muovono
  } else {
    risultato[i] = v[ultimoPari - i];           // specchio tra le posizioni pari
  }
}

console.log(risultato);                         // [ 0, -1, 33, 9, 7, 5 ]

ultimoPari vale 4: in posizione 0 va v[4], in posizione 2 va v[2] (resta lì) e in posizione 4 va v[0].

B4 · Un fattore calcolato con il modulo. Nella tabella i due casi differiscono solo per un 1 in più da togliere quando la lunghezza è pari, e quel numero si può calcolare invece di scegliere con un if: 1 - v.length % 2 vale 0 se la lunghezza è dispari e 1 se è pari.

let v = [7, -1, 33, 9, 0, 5];

let fattore = 1 - v.length % 2;                 // 0 se length è dispari, 1 se è pari

let risultato = new Array(v.length);
for (let i = 0; i < v.length; i++) {
  if (i % 2 != 0) {
    risultato[i] = v[i];
  } else {
    risultato[i] = v[v.length - 1 - fattore - i];
  }
}

console.log(risultato);                         // [ 0, -1, 33, 9, 7, 5 ]

È la stessa soluzione di B3, perché v.length - 1 - fattore è proprio ultimoPari; cambia solo il modo di ottenerlo. B3 si legge più facilmente, B4 è più compatta: questo tipo di «raffinatezza» viene col tempo, quando il ragionamento di base è chiaro.

B5 · Ricondursi al punto A con un array di appoggio (non l'abbiamo vista a lezione). Si mettono da parte i soli elementi in posizione pari, in un array pari; a quel punto il problema è invertire pari, cioè il punto A, e la parità della lunghezza di v non conta più.

let v = [7, -1, 33, 9, 0, 5];

let pari = [];
for (let i = 0; i < v.length; i += 2) {
  pari[pari.length] = v[i];                     // [ 7, 33, 0 ]
}

let risultato = new Array(v.length);
for (let i = 0; i < v.length; i++) {
  if (i % 2 != 0) {
    risultato[i] = v[i];
  } else {
    risultato[i] = pari[pari.length - 1 - i / 2];   // formula di A2 su pari
  }
}

console.log(risultato);                         // [ 0, -1, 33, 9, 7, 5 ]

La posizione pari i di v corrisponde alla posizione i / 2 di pari (0 → 0, 2 → 1, 4 → 2).

I casi limite. B1, B3, B4 e B5 danno sempre lo stesso risultato: con [1, 2, 3, 4, 5] si stampa [ 5, 2, 3, 4, 1 ], con [10, 11, 12, 13, 14, 15] si stampa [ 14, 11, 12, 13, 10, 15 ], con [7] si stampa [ 7 ] e con [] i cicli non partono e si stampa [].

Errori che abbiamo incontrato

Esercizio 2

Ripasso: Recap 1 · Gli array; per la variabile flag, l'esercizio di ricerca dello zero dell'esercitazione 7.

Dato un array v, scrivere un programma che stampi true se ogni 2 presente nell'array è immediatamente seguito da un 3, false altrimenti. Se non ci sono 2 la risposta è true; un 2 in ultima posizione non è seguito da niente, quindi dà false.

Provate il programma con questi array:

vcosa stampa
[1, 2, 3, 5, 2, 3]true
[2, 4, 3]false
[5, 2, 3, 2]false
[1, 5, 7]true
[2, 2, 3]false
[]true
Soluzione

È la solita variabile flag: si parte da true e si cambia idea solo se si trova un controesempio, cioè un 2 che non è seguito da un 3. Per guardare l'elemento successivo si usa v[i + 1]: se i è l'ultima posizione, v[i + 1] non esiste e vale undefined, che è diverso da 3, quindi il caso del 2 in fondo è già gestito.

let v = [1, 2, 3, 5, 2, 3];

let ok = true;
for (let i = 0; i < v.length; i++) {
  if (v[i] == 2 && v[i + 1] != 3) {             // un 2 non seguito da un 3
    ok = false;
  }
}

console.log(ok);                                // true

Per gli altri array della tabella si ottiene: [2, 4, 3] → false; [5, 2, 3, 2] → false (l'ultimo 2 non ha un successivo); [1, 5, 7] → true (nessun 2); [2, 2, 3] → false (il primo 2 è seguito da un 2); [] → true.

Due errori frequenti:

In alternativa si può restituire false appena si trova il controesempio e true dopo il ciclo.

Esercizio 3

Ripasso: Recap 2 · Array e funzioni; la funzione contiene è nell'Esercizio 11 dell'esercitazione 7.

Funzioni che costruiscono un array di numeri casuali rispettando una regola. Ricordate che un intero casuale tra min e max (estremi inclusi) è Math.floor(Math.random() * (max - min + 1)) + min.

A. Scrivere la funzione casualiPari(n, min, max) che restituisce un array di n numeri casuali pari compresi tra min e max.

B. Scrivere la funzione casualiDistinti(n, min, max) che restituisce un array di n numeri casuali compresi tra min e max tutti diversi tra loro. Suggerimento: estraete un numero con un do ... while finché non ne trovate uno che non è già nell'array.

Provatele, ad esempio, con casualiPari(8, 1, 20) e casualiDistinti(5, 1, 10).

Soluzione

A. Il modo più semplice per ottenere un pari è estrarre finché non esce un pari, con un do ... while:

function casualiPari(n, min, max) {
  let risultato = [];
  for (let i = 0; i < n; i++) {
    let x;
    do {
      x = Math.floor(Math.random() * (max - min + 1)) + min;
    } while (x % 2 != 0);                       // si ripete finché x è dispari
    risultato[i] = x;
  }
  return risultato;
}

console.log(casualiPari(8, 1, 20));             // ad esempio [ 12, 4, 18, 4, 2, 20, 10, 6 ]

Si può usare anche una formula che produce direttamente un pari (si estrae un numero casuale e lo si moltiplica per 2), ma bisogna stare attenti agli estremi: con min e max dispari il primo e l'ultimo pari possibili sono diversi da min e max. Il do ... while evita questo problema. Attenzione però: se tra min e max non c'è nessun pari (ad esempio min = max = 7) il ciclo non finisce mai.

B. La regola «diverso da tutti gli altri» si controlla con la funzione contiene dell'esercitazione 7, applicata al risultato che si sta costruendo:

function contiene(v, x) {
  for (let i = 0; i < v.length; i++) {
    if (v[i] == x) {
      return true;
    }
  }
  return false;
}

function casualiDistinti(n, min, max) {
  let risultato = [];
  for (let i = 0; i < n; i++) {
    let x;
    do {
      x = Math.floor(Math.random() * (max - min + 1)) + min;
    } while (contiene(risultato, x));           // si ripete finché x c'è già
    risultato[risultato.length] = x;
  }
  return risultato;
}

console.log(casualiDistinti(5, 1, 10));         // ad esempio [ 7, 2, 9, 4, 10 ]

Qui si assegna a risultato[risultato.length] (e non a risultato[i]): è lo stesso, ma rende evidente che si aggiunge in fondo, e che contiene guarda solo gli elementi già inseriti.

Attenzione: se i valori possibili sono meno di n (ad esempio casualiDistinti(5, 1, 3)) non ci sono abbastanza numeri diversi e il programma non termina. Una funzione robusta controllerebbe prima che max - min + 1 >= n.

Esercizio 4

Ripasso: Recap 2 · Array e funzioni.

Funzioni che costruiscono un array con numeri chiesti all'utente. Si legge con prompt e si converte con Number, come negli esercizi precedenti.

A. Scrivere la funzione leggiArray(n) che chiede all'utente n numeri e restituisce l'array che li contiene, nell'ordine in cui sono stati inseriti.

B. Scrivere la funzione leggiFinoAZero() che chiede numeri finché l'utente non inserisce 0 e restituisce l'array dei numeri inseriti, senza lo zero finale. Non si sa in anticipo quanti saranno.

C. Scrivere la funzione leggiPositivi(n) che chiede all'utente n numeri positivi: se l'utente ne inserisce uno non positivo, il programma lo richiede finché non è valido.

Per ciascuna scrivete poi un breve programma che la usa e stampa l'array letto.

Soluzione

A. Si sa quante volte ripetere: un ciclo for che a ogni giro aggiunge il numero letto:

function leggiArray(n) {
  let risultato = [];
  for (let i = 0; i < n; i++) {
    risultato[i] = Number(prompt("Numero " + (i + 1) + ": "));
  }
  return risultato;
}

let v = leggiArray(4);
console.log(v);                                 // ad esempio [ 5, -2, 9, 5 ]

B. Non si sa quante volte ripetere: serve un while con sentinella (lo zero), come nell'esercitazione 6. Si legge prima del ciclo e di nuovo alla fine di ogni giro:

function leggiFinoAZero() {
  let risultato = [];
  let x = Number(prompt("Numero (0 per finire): "));
  while (x != 0) {
    risultato[risultato.length] = x;            // lo zero finale non si aggiunge
    x = Number(prompt("Numero (0 per finire): "));
  }
  return risultato;
}

let w = leggiFinoAZero();
console.log(w);                                 // con 4, 7, 0 si stampa [ 4, 7 ]

Qui si assegna a risultato[risultato.length], e non a risultato[i]: non c'è un contatore i, e si aggiunge sempre in fondo. Se l'utente scrive subito 0 si restituisce l'array vuoto [].

C. È la validazione dell'input con do ... while (esercitazione 4), ripetuta per ognuno degli n numeri:

function leggiPositivi(n) {
  let risultato = [];
  for (let i = 0; i < n; i++) {
    let x;
    do {
      x = Number(prompt("Numero positivo " + (i + 1) + ": "));
    } while (x <= 0);                           // si richiede finché non è positivo
    risultato[i] = x;
  }
  return risultato;
}

let p = leggiPositivi(3);
console.log(p);

La variabile x va dichiarata fuori dal do ... while ma dentro il for: così il while (x <= 0) la vede, e a ogni giro del for se ne usa una nuova.

Esercizio 5

Ripasso: Recap 2 · Array e funzioni (la parte sul passaggio per riferimento).

Un array non si copia con l'assegnazione. Vediamo perché e come si fa.

A. Dite cosa stampa questo programma, senza eseguirlo. Poi spiegate con le vostre parole perché a è cambiato anche se abbiamo modificato solo b.

let a = [1, 2, 3];
let b = a;
b[0] = 99;
console.log(a);
console.log(b);
console.log(a == b);

B. Volevamo conservare a e lavorare su una copia. Scrivere la funzione copia(v) che restituisce un nuovo array con gli stessi elementi di v, e usarla per correggere il programma di A: dopo la modifica di b, a deve essere ancora [1, 2, 3].

Soluzione

A. Stampa [ 99, 2, 3 ], poi [ 99, 2, 3 ], poi true.

Una variabile che contiene un array non contiene gli elementi: contiene un riferimento, cioè l'«indirizzo» dell'array in memoria. Con let b = a; si copia solo il riferimento: a e b sono due nomi per lo stesso array. Modificare l'array tramite b lo cambia anche per a, perché c'è un solo array. Per questo a == b è true: sono lo stesso array.

È diverso dai numeri: con let y = x; si copia il valore, e cambiare y non tocca x.

B. Per avere una copia vera bisogna creare un array nuovo e riempirlo con gli elementi di v:

function copia(v) {
  let risultato = [];
  for (let i = 0; i < v.length; i++) {
    risultato[i] = v[i];
  }
  return risultato;
}

let a = [1, 2, 3];
let b = copia(a);                               // array nuovo, non un secondo nome per a
b[0] = 99;
console.log(a);                                 // [ 1, 2, 3 ]
console.log(b);                                 // [ 99, 2, 3 ]
console.log(a == b);                            // false: sono due array diversi

È anche il motivo per cui le nostre funzioni costruiscono un array nuovo invece di modificare quello ricevuto: un parametro array è un riferimento allo stesso array di chi chiama.