 |
Compattare un array dinamico di numeri interi. dopo aver eliminato eventuali numeri perfetti Amendola Armando :: 2012-05-31Un numero intero N si dice perfetto quando la somma dei suoi divisori, escluso N stesso, è uguale ad N. In questo articolo vedremo come compattare un array dinamico dopo aver eliminato eventuali numeri perfetti in esso contenuto.
Per verificare un numero è perfetto, dobbiamo controllare se la somma dei suoi divisori, escluso se stesso, è uguale al numero stesso. Scriviamo allora la seguente funzione
// Verifica se n è un numero perfetto
boolean perfetto(int n)
{
int i=0;
boolean perf=false;
int somma=0;
for(i=1;i < n;i++)
{
if((n%i)==0) somma=somma+i;
}
if(somma==n)
perf=true;
return perf;
}
Definiamo il tipo boolean nel seguente modo:
typedef enum {false, true} boolean;
Allochiamo lo spazio per un vettore dinamico di n numeri interi:
printf("inserisci n :");
scanf("%d",&n);
p=malloc(n*sizeof(int));
Se non è possibile allocare la memoria richiesta, si visualizza un messaggio e si esce dall'applicazione:
if(p==NULL)
{
printf("memoria insufficiente");
exit(1);
}
Se invece è possibile allocare tutto lo spazio di memoria necessario, si provvede a leggere i dati dell'array dinamico
for(i=0; i < n ; i++)
{
printf("inserisci l'elemento :");
scanf("%d",p+i);
}
Dopo aver caricato il vettore dinamico, si verifica per ogni elemento di tale array se esso è perfetto o meno:
for(i=0; i < n-nperf;i++)
{
num=*(p+i);
if(perfetto(num)==true)
Se il test è positivo, allora si rialloca la memoria dinamica per il vettore q dei numeri perfetti, aggiungendo una nuova cella :
{
nperf++;
q=realloc(q,nperf*sizeof(int));
La variabile nperf conta il numero di celle del vettore dinamico, inizialmente vale zero, ed è incrementata di uno ogni volta che troviamo un nuovo numero perfetto
Una volta trovato il numero perfetto, e riallocato il blocco, verifichiamo se tale riallocazione ha avuto esito positivo:
if(q==NULL)
{
printf("memoria insufficiente");
exit(1);
}
Se la memoria è stata correttamente riallocata, si copia l'elemento corrente del vettore p nell'ultima posizione del vettore q:
*(q+i2)=*(p+i);
i2++;
la variabile i2 è l'indice del vettore di destinazione q.
Una volta ricopiato l'elemento corrente nel vettore di destinazione, si compatta il vettore sorgente, utilizzando la funzione compatta. Tale funzione restituisce un puntatore al blocco di memoria ridimensionato e chiede, come argomenti, l'indice dell'elemento corrente da rimuovere, la dimensione dell'array sorgente, il numero di elementi nperf rimossi, ed infine il puntatore al blocco di memoria corrente, cioè il puntatore all'array sorgente p:
p=compatta(i,n,nperf,p);
Ecco il codice della funzione compatta
int *compatta(int i,int n, int m,int *ptr)
{
int j=i;
while(j < (n-m-1))
{
*(ptr+j)=*(ptr+j+1);
j++;
}
ptr=realloc(ptr,(n-m)*sizeof(int));
return ptr;
}
#include"stdio.h"
#include"stdlib.h"
int perfetto(int n);
int *compatta(int i,int n, int m,int *ptr);
int main()
{
int *p=NULL,*q=NULL;
int n,i=0,i2=0,k=0,num;
printf("inserisci n :");
scanf("%d",&n);
p=malloc(n*sizeof(int));
if(p==NULL)
{
printf("memoria insufficiente");
exit(1);
}
for(i=0; i < n ; i++)
{
printf("inserisci l'elemento :");
scanf("%d",p+i);
}
for(i=0; i < n-k;i++)
{
num=*(p+i);
if(perfetto(num)==1)
{
k++;
q=realloc(q,k*sizeof(int));
if(q==NULL)
{
printf("memoria insufficiente");
exit(1);
}
*(q+i2)=*(p+i);
i2++;
p=compatta(i,n,k,p);
if(p==NULL)
{
printf("memoria insufficiente");
exit(1);
}
}
}
printf("gli elementi non perfetti sono:");
for(i=0;i < (n-k); i++)
printf("%d\n",*(p+i));
printf("gli %d elementi perfetti sono:\n ",k);
for(i=0;i < k;i++)
printf("%d\n",*(q+i));
return 0;
}
// Verifica se n è un numero perfetto
int perfetto(int n)
{
int i=0;
int perf=0;
int somma=0;
for(i=1;i < =n;i++)
{
if((n%i)==0)
{
if(i!=n)
somma=somma+i;
}
}
if(somma==n)
perf=1;
return perf;
}
int *compatta(int i,int n, int m,int *ptr)
{
while(i<(n-m-1))
{
*(ptr+i)=*(ptr+i+1);
i++;
}
ptr=realloc(ptr,(n-m)*sizeof(int));
return ptr;
}
|
