2010 – 3

di

Si considerino i 3 seguenti frammenti di programma, dove le variabili i, k, n e p sono di tipo int, e n è inizializzata con un valore positivo maggiore di

  1. #define TRUE 1
#define FALSE 0
p=TRUE;
k=n;
for(i=2; i < k; i++)
   if(n%i == 0)
   {
      printf("Il numero %d non e' primo\n",n);
      p=FALSE;
      break;
   }
if(p)
   printf("Il numero %d e' primo\n",n);
  2. #define TRUE 1
#define FALSE 0
p=TRUE;
k=n/2+1;
for(i=2; i < k; i++)
   if(n%i == 0)
   {
      printf("Il numero %d non e' primo\n", n);
      p=FALSE;
      break;
   }
if(p)
   printf("Il numero %d e' primo\n", n);
  3. #define TRUE 1
#define FALSE 0
p=TRUE;
k=sqrt(n)+1;
for(i=2; i < k; i++)
   if(n%i == 0)
   {
      printf("Il numero %d non e' primo\n", n);
      p=FALSE;
      break;
   }
if(p)
   printf("Il numero %d e' primo\n", n);

Quale delle seguenti affermazioni è vera?

  1. Se n è un numero primo i tre frammenti di programma lo indicano impiegando lo stesso tempo.
  2. Se n è un numero primo solo i frammenti di programma A) e B) lo indicano, mentre C) può non funzionare correttamente per particolari valori di n.
  3. Se n è un numero primo i tre frammenti di programma lo indicano ma impiegando tempi diversi.
  4. Se n è un numero primo solo il frammento di programma A) lo indica, mentre B) e C) possono non funzionare correttamente per particolari valori di n.

Soluzione: c (se n è un numero primo i tre frammenti di programma lo indicano ma impiegando tempi diversi).

I tre algoritmi sono quasi identici e risolvono lo stesso problema.

Il limite del for() decresce

  1. k=n
  2. k=n/2+1
  3. k=sqrt(n)+1

e corrispondentemente decresce il tempo richiesto dall'algoritmo.