Fondamenti di Informatica - Ingegneria per l'Ambiente e il Territorio - A.A. 97/98

- Seconda esercitazione in laboratorio -

2.1.1 Problema (test di primalità)

"Dato un naturale n, stabilire se esso è primo oppure no"

Si propone di seguito il codice C di un programma che risolve il problema. Si invitano gli studenti a:

  1. Analizzare il programma per comprenderne la modalità di funzionamento.
  2. Scrivere il programma in un ambiente di sviluppo per il linguaggio C (ad es., TurboC).

#include <stdio.h>

main () {

int n, primo, divisore;

/* n e` il naturale da testare

primo e` una variabile che alla fine della esecuzione contiene uno fra i seguenti valori:

0 (il numero non e` primo)

1 (il numero e` primo)

2 (errore, il numero inserito e` negativo

divisore contiene i vari divisori che si provano (2, 3, 4, ...) per stabilire se n e` primo

*/

printf("\n\n\nTest di primalita`. Benvenuti.\n");

printf("Digita il numero da testare: ");

scanf("%d", &n);

if (n <= 0)

primo = 2;

else {

primo = 1; /* assumiamo che n sia primo */

divisore = 2;

while (divisore < n) {

if (n % divisore == 0)

primo = 0; /* e` stato trovato un divisore */

divisore = divisore + 1;

}

}

if (primo == 0)

printf("Il numero %d non e` primo.", n);

else if (primo == 1)

printf("Il numero %d e` primo.", n);

else /* (primo == 2) */

printf("Errore: hai immesso un numero negativo.");

printf(" Arrivederci.\n");

}

2.1.2 Attività di raffinamento

Con riferimento al programma di cui sopra, sono evidenti alcuni limiti dello stesso:

  1. In caso di numero non primo, il programma continua (inutilmente) a lavorare.
  2. Il test utilizzato nel ciclo while usa un valore limite (n) inutilmente elevato (per verificare se un naturale m è primo basta cercare un divisore nell'intervallo ).
  3. Se il numero non è primo il programma non ci dà informazione alcuna sui suoi divisori.

Ciò premesso, si invitano gli studenti a modificare il programma in modo da ovviare ai limiti descritti. In particolare, scrivere un programma per il test di primalità che termini non appena la risposta al test sia "certa" e restituisca, in caso di numero non primo, il più piccolo divisore del numero.

2.2.1 Problema (ricerca di occorrenze di una parola in una frase)

"Date una frase e una parola, determinare tutte le occorrenza della parola nella frase"

Si propone di seguito il codice C di un programma che risolve il problema. Si invitano gli studenti a:

  1. Analizzare il programma per comprenderne la modalità di funzionamento.
  2. Scrivere il programma in un ambiente di sviluppo per il linguaggio C (ad es., TurboC).

#include <stdio.h>

#define LUN_FRASE 200

#define LUN_PAROLA 20

main()

{

char frase[LUN_FRASE], parola[LUN_PAROLA];

int i, j, k, primo, conta_occ;

/* scanf non consente di leggere spazi; viene usata gets per leggere le stringhe */

printf("Ricerca delle occorrenze di una parola in un frase. Benvenuti.\n");

printf("\nScrivi la frase:\n\t");

gets(frase);

printf("\nScrivi ora la parola:\n\t");

gets(parola);

/* inizializzazioni */

conta_occ=0;

i = 0;

/* ciclo principale */

do {

j = 0;

primo = i;

k = i;

/* ciclo verifica occorrenza */

while((frase[k] != '\0')&&
(parola[j] != '\0')&&
(frase[k] == parola[j])) {

k = k+1;

j = j+1;

}

if(parola[j] == '\0') {

conta_occ = conta_occ+1;

printf("\nOccorrenza in posizione %d.\n%s\n", primo, frase);

while(primo > 0) {

printf(" ");

primo = primo-1;

}

printf("%s\n", parola);

}

i = i+1;

} while(frase[i] != '\0');

printf("\nSi sono verificate %d occorrenze. Arrivederci.\n", conta_occ);

}

2.2.2 Attività di raffinamento

Con riferimento al programma di cui sopra, si invitano gli studenti a:

  1. Generalizzare il programma, prevedendo la possibilità di un carattere '?' nella parola, in corrispondenza di cui ogni carattere della frase è accettabile.
  2. Poiché la tecnica introdotta al punto precedente di fatto elimina la possibilità di verificare la presenza effettiva del carattere '?' nella frase, generalizzare ulteriormente il programma allo scopo di prevedere anche tale possibilità.