Programmazione I
Anno Accademico 1999-2000
Prof. Giovanni Pighizzini


Lezione 8
25 ottobre 1999



Argomenti trattati

-
Cicli FOR innestati.
-
Alcuni esempi.

8.1  Ancora sull'uso dei cicli FOR

Presentiamo ora un semplice programma che legge due numeri non negativi w e z e calcola la potenza wz. Il programma è basato su tre fasi: la prima di acquisizione dall'esterno dei dati, la seconda di calcolo, e la terza di comunicazione all'esterno del risultato.

Supponiamo che alla fine della prima fase i dati si trovino in due variabili di tipo integer di nomi w e z, rispettivamente. Decidiamo inoltre che la seconda fase dovrà porre il risultato in una variabile di nome potenza, anch'essa di tipo integer. Fissate queste convenzioni, è possibile sviluppare le tre frasi indipendentemente l'una dall'altra.

Concentriamoci dunque sulla fase di calcolo. Ricordando che wz non è altro che w moltiplicato z volte per se stesso, non è difficile vedere che tale fase può essere realizzata mediante un ciclo FOR:

   potenza := 1;
   FOR k := 1 TO z DO
      potenza := potenza * w

Si osservi che l'istruzione interna al ciclo viene ripetuta esattamente z volte (se z contiene zero non viene mai eseguita).

Riportiamo il testo del programma completo:

PROGRAM power (input, output);

{calcola l'elevamento a potenza di due numeri non negativi}

   VAR
      z, w, k, potenza: integer;

BEGIN {power}
   {fase di lettura}
   write('Inserire due interi non negativi ');
   readln(w, z);
   WHILE (z < 0) OR (w < 0) DO
      BEGIN
         write('Errore nei dati: ripetere l''inserimento ');
         readln(w, z)
      END; {while}

   {fase di calcolo}
   potenza := 1;
   FOR k := 1 TO z DO
      potenza := potenza * w;

   {fase di scrittura}
   writeln('Il risultato e'' ', potenza : 1)
END. {power}

Vogliamo ora riscrivere il programma precedente, senza l'utilizzo diretto dell'operatore * per il calcolo del prodotto, ma facendo uso esclusivamente di operazioni di somma. In altre parole, dobbiamo riscrivere l'assegnamento potenza := potenza * w.

Cominciamo col dividere l'operazione di assegnamento nelle due parti fondamentali che la costituiscono, cioè il calcolo e l'assegnamento del risultato:

1.
calcola il valore dell'espressione potenza * w;

2.
assegna il risultato alla variabile potenza.

Per la prima fase, cioè il calcolo del prodotto potenza * w, possiamo utilizzare la tecnica vista nella lezione precedente, in cui abbiamo calcolato il prodotto di due interi non negativi utilizzando un ciclo FOR. A tale scopo introduciamo una nuova variabile di nome prodotto, in cui verrà memorizzato il risultato, e una variabile di nome j per il ciclo:

   prodotto := 0;
   FOR j := 1 TO w DO
      prodotto := prodotto + potenza

Per assegnare il risultato alla variabile potenza, sarà sufficiente scrivere potenza := prodotto. Pertanto, l'intera fase di calcolo, risulta riscritta come:

   potenza := 1;
   FOR k := 1 TO z DO
      BEGIN
         prodotto := 0;
         FOR j := 1 TO w DO
            prodotto := prodotto + potenza;
         potenza := prodotto
      END

Si osservi che il codice appena scritto contiene due costrutti FOR innestati. Per ogni esecuzione del costrutto esterno, cioè per ogni valore della variabile k da 1 fino a z, viene eseguito l'intero costrutto interno, con j che va da 1 a w. Pertanto, l'istruzione prodotto := prodotto + potenza verrà eseguita w * z volte: prima con k=j=1, poi con k=1 e j=2, ..., poi con k=1 e j=w, poi con k=2 e j=1, e così via.

Le istruzioni interne al FOR piú esterno, come ad esempio l'assegnamento potenza := prodotto, vengono invece eseguite z volte.

La parte di codice appena presentata, è equivalente al seguente codice, in cui si utilizzano esclusivamente cicli WHILE:

   potenza := 1;
   k := 1;
   WHILE k <= z DO
      BEGIN
         prodotto := 0;
         j := 1;
         WHILE j <= w DO
            BEGIN
               prodotto := prodotto + potenza;
               j := j + 1
            END; {while j}
         potenza := prodotto;
         k := k + 1
      END {while k}

Si noti in particolare che ad ogni ripetizione delle istruzioni del ciclo esterno è necessario eseguire tutto il ciclo interno. Pertanto, il valore della variabile j viene fatto ripartire da 1 prima di ogni esecuzione del ciclo interno. Per esercizio, si consiglia di esaminare come sarebbe eseguito il ciclo, se l'assegnamento j := 1 venisse spostato immediatamente dopo l'assegnamento k := 1.

Riportiamo ora il testo completo del programma nella seconda versione, cioè utilizzando due cicli FOR innestati per il calcolo della potenza. Sia in questa versione, che nella prima, il programma non gestisce correttamente il calcolo di zero elevato alla zero. Si introducano per esercizio le modifiche necessarie per operare correttamente anche questo calcolo.

PROGRAM power (input, output);

{calcola l'elevamento a potenza di due numeri non negativi}
{nel calcolo non viene utilizzata la moltiplicazione}

   VAR
      z, w, k, j, potenza, prodotto: integer;

BEGIN {power}
   {fase di lettura}
   write('Inserire due interi non negativi ');
   readln(w, z);
   WHILE (z < 0) OR (w < 0) DO
      BEGIN
         write('Errore nei dati: ripetere l''inserimento ');
         readln(w, z)
      END; {while}

   {fase di calcolo}
   potenza := 1;
   FOR k := 1 TO z DO
      BEGIN
         {simulazione dell'assegnamento potenza := potenza * w}
         {1 - calcolo di potenza * w}
         prodotto := 0;
         FOR j := 1 TO w DO
            prodotto := prodotto + potenza;
         {2 - assegnamento del risultato alla variabile potenza}
         potenza := prodotto
      END; {for k}

   {fase di scrittura}
   writeln('Il risultato e'' ', potenza : 1)
END. {power}

8.2  Alcuni suggerimenti per la scrittura dei programmi

Per migliorare la leggibilità dei programmi e rendere quindi piú agevoli le fasi di modifica e individuazione di errori, è indispensabile:

8.3  Esempio: decidere se un numero è primo

Sviluppiamo ora un programma che legge un numero e stabilisce se esso sia primo o no.

Prima di tutto, ricordiamo che un numero p è primo se valgono le seguenti condizioni:

1.
p>1;

2.
p non ha divisori positivi, eccetto 1 e p stesso.

Il metodo immediato per verificare se un numero p è primo consiste quindi nel provare a dividere p per tutti i numeri compresi tra 2 e p-1.

Possiamo quindi descrivere un algoritmo, basato su questo metodo, formato dalle seguenti fasi:

1.
lettura del numero;

2.
divisioni del numero per i numeri compresi tra 2 e il numero meno uno, per deciderne la primalità;

3.
scrittura del risultato.

Per la scrittura del programma ci serviranno due variabili di tipo integer, che chiameremo numero e divisore, per memorizzare rispettivamente il numero di cui si deve testare la primalità e il divisore con cui si tenta di dividere il numero. Utilizzeremo inoltre una variabile di nome primo e di tipo boolean. Alla fine della seconda fase, la variabile primo dovrà contenere true se e solo se il numero dato è primo. Con questa convenzione, è immediato scrivere la fase finale del programma:

   {scrittura del risultato}
   IF primo THEN
      writeln('Il numero ', numero : 1, ' e'' primo')
   ELSE
      writeln('Il numero ', numero : 1, ' non e'' primo')

Nella fase iniziale di acquisizione dei dati si richiede l'inserimento del numero da esaminare, fino a quando non venga inserito un numero maggiore di 1. Tale fase può dunque essere scritta utilizzando un ciclo REPEAT o un ciclo WHILE. Ecco una possibile soluzione:

   {lettura dati}
   write('Inserisci un intero maggiore di 1 ');
   readln(numero);
   WHILE numero <= 1 DO
      BEGIN
         write('Input non valido. Inserisci un intero maggiore di 1 ');
         readln(numero)
      END;{while}

Consideriamo ora la fase centrale. Abbiamo stabilito che alla fine di questa fase, la variabile primo dovrà contenere true se e solo se numero è primo. Il metodo piú semplice è quello di assegnare a primo inizialmente il valore true, di dividere poi numero iterativamente per tutti i valori tra 2 e numero-1, assegnando a primo valore false nel caso in cui una delle divisioni dia resto uguale a zero. Questa fase può dunque essere codificata utilizzando un ciclo FOR:

   {verifica se numero e' primo, dividendolo per tutti i numeri tra 2 e numero-1}
   primo := true;
   FOR divisore := 2 TO numero - 1 DO
      IF numero MOD divisore = 0 THEN
         primo := false;

Ecco il testo del programma completo:

PROGRAM primi (input, output);

{Dato in ingresso un intero maggiore di 1, verifica se questo e' primo}

   VAR
      numero, divisore: integer;
      primo: boolean;

BEGIN {primi}

   {lettura dati}
   write('Inserisci un intero maggiore di 1 ');
   readln(numero);
   WHILE numero <= 1 DO
      BEGIN
         write('Input non valido. Inserisci un intero maggiore di 1 ');
         readln(numero)
      END;{while}

   {verifica se numero e' primo, dividendolo per tutti i numeri tra 2 e numero-1}
   primo := true;
   FOR divisore := 2 TO numero - 1 DO
      IF numero MOD divisore = 0 THEN
         primo := false;

   {scrittura del risultato}
   IF primo THEN
      writeln('Il numero ', numero : 1, ' e'' primo')
   ELSE
      writeln('Il numero ', numero : 1, ' non e'' primo')

END. {primi}

È possibile apportare al programma alcuni miglioramenti. Prima di tutto possiamo osservare che si potrebbe uscire dal ciclo non appena viene individuato un divisore di numero. A tale fine, possiamo sostituire il ciclo FOR con un ciclo WHILE, aggiungendo un controllo sulla variabile primo.

   {verifica se numero e' primo, dividendolo per i numeri tra 2 e numero-1}
   primo := true;
   divisore := 2;
   WHILE primo AND (divisore < numero) DO
      BEGIN
         primo := numero MOD divisore <> 0;
         divisore := divisore + 1
      END; {while}

Osserviamo poi che se numero ammette un divisore, allora ammette sicuramente anche un divisore minore o uguale alla propria radice quadrata. Questo permette di ridurre il numero di ripetizioni del ciclo:

   {verifica se numero e' primo, dividendolo per i numeri tra 2 e 
    la radice quadrata di numero}
   primo := true;
   divisore := 2;
   WHILE primo AND (divisore * divisore <= numero) DO
      BEGIN
         primo := numero MOD divisore <> 0;
         divisore := divisore + 1
      END; {while}

Infine, ricordando che l'unico numero primo pari è 2, possiamo evitare le divisioni per numeri pari:

   {verifica se numero e' primo, controllando prima di tutto che non sia pari, e 
    poi dividendolo per i numeri dispari tra 3 e la radice quadrata di numero}
   IF numero = 2 THEN
      primo := true
   ELSE
      BEGIN
         {controlla se il numero e' pari}
         primo := numero MOD 2 <> 0;
         divisore := 3;
         WHILE primo AND (divisore * divisore <= numero) DO
            BEGIN
               primo := numero MOD divisore <> 0;
               divisore := divisore + 2
            END {while}
      END; {else}

Ecco il programma completo, dopo queste modifiche:

PROGRAM primi4 (input, output);

{Dato in ingresso un intero maggiore di 1, verifica se questo e' primo}
{In questa versione si esce dal ciclo di controllo non appena si trova un 
 divisore o quando si sono esaminati tutti i numeri fino alla radice 
 quadrata del numero dato. Inoltre non si esaminano divisori pari (eccetto 2)}

   VAR
      numero, divisore: integer;
      primo: boolean;

BEGIN {primi4}

   {lettura dati}
   write('Inserisci un intero maggiore di 1 ');
   readln(numero);
   WHILE numero <= 1 DO
      BEGIN
         write('Input non valido. Inserisci un intero maggiore di 1 ');
         readln(numero)
      END;{while}

   {verifica se numero e' primo, controllando prima di tutto che non sia pari, e 
    poi dividendolo per i numeri dispari tra 3 e la radice quadrata di numero}
   IF numero = 2 THEN
      primo := true
   ELSE
      BEGIN
         {controlla se il numero e' pari}
         primo := numero MOD 2 <> 0;
         divisore := 3;
         WHILE primo AND (divisore * divisore <= numero) DO
            BEGIN
               primo := numero MOD divisore <> 0;
               divisore := divisore + 2
            END {while}
      END; {else}

   {scrittura del risultato}
   IF primo THEN
      writeln('Il numero ', numero : 1, ' e'' primo')
   ELSE
      writeln('Il numero ', numero : 1, ' non e'' primo')

END. {primi4}

Esercizi

1.
Il programma che verifica se un numero è primo, dopo avere esaminato un numero fornisce la risposta e termina la propria esecuzione. In questo modo, l'utente che voglia esaminare piú numeri è costretto a lanciare piú volte il programma. Modificare il programma in modo tale che, dopo avere esaminato un numero e fornito la risposta, chieda all'utente se vuole continuare, esaminando altri numeri, o se vuole terminare l'esecuzione.

2.
Scrivere un programma che riceva in ingresso un numero intero n e stampi un elenco di tutti i numeri primi compresi tra 1 e n.
3.
Scrivere un programma che riceva in ingresso un numero intero n e stampi un elenco dei primi n numeri primi.

4.
Per ognuno dei seguenti frammenti di codice, individuare delle dichiarazioni di variabile in modo che le istruzioni che vi appaiono risultino corrette dal punto di vista della compatibilità dei tipi. Indicare inoltre, in funzione dei valori iniziali delle variabili, l'istruzione indicata con il commento {*}. Riscrivere infine il frammento sostituendo i cicli FOR con cicli WHILE.

 
©1999 Giovanni Pighizzini
Il contenuto di queste pagine è protetto dalle leggi sul copyright e dalle disposizioni dei trattati internazionali. Il titolo ed i copyright relativi alle pagine sono di proprietà dell'autore. Le pagine possono essere riprodotte ed utilizzate liberamente dagli studenti, dagli istituti di ricerca, scolastici ed universitari afferenti ai Ministeri della Pubblica Istruzione e dell'Università e della Ricerca Scientifica e Tecnologica per scopi istituzionali, non a fine di lucro. Ogni altro utilizzo o riproduzione (ivi incluse, ma non limitatamente a, le riproduzioni a mezzo stampa, su supporti magnetici o su reti di calcolatori) in toto o in parte è vietata, se non esplicitamente autorizzata per iscritto, a priori, da parte dell'autore.
L'informazione contenuta in queste pagine è ritenuta essere accurata alla data della pubblicazione. Essa è fornita per scopi meramente didattici e non per essere utilizzata in progetti di impianti, prodotti, ecc.
L'informazione contenuta in queste pagine è soggetta a cambiamenti senza preavviso. L'autore non si assume alcuna responsabilità per il contenuto di queste pagine (ivi incluse, ma non limitatamente a, la correttezza, completezza, applicabilità ed aggiornamento dell'informazione).
In ogni caso non può essere dichiarata conformità all'informazione contenuta in queste pagine. In ogni caso questa nota di copyright non deve mai essere rimossa e deve essere riportata anche in utilizzi parziali.



Giovanni Pighizzini
1999-10-25