 |
Ancora i ragazzi conoscono i vettori ma non le funzioni, quindi il programma viene scritto
tutto nel main.
Il testo dell'esercizio è il seguente:
Scrivere un programma C che calcoli l'entropia dei dati letti da statndard input.
I dati dovranno essere terminati da un EOF (ctrl-d). Si dovrà calcolare
l'entropia di coppie di caratteri, quindi i caratteri andranno letti a due a due e poi
composti in un unico codice a 16 bit, del quale calcoleremo l'entropia.
Il programma dovrà stampare:
- Il numero di simboli (coppie di caratteri) letti
- I 10 simboli più frequenti
- L'entropia calcolata per il messaggio letto
- La dimensione ottima teorica del messaggio, in bit, espressa come <entropia> *
<no simboli letti>
- La dimensione ottima teorica del messaggio, in byte, espressa come <entropia> *
<no simboli letti> / 8
Note:
- Per calcolare le frequenze relative, creare un vetore di interi della dimensione
del numero di possibili codici diversi letti (i codici sono ad 16 bit, quindi avremo
216 = 65536 codici diversi al massimo) ed incrementare l'elemento dell'array il cui
indice è il codice letto.
- La funzione getchar () legge un carattere, ma ritorna un tipo intero. EOF
non è un carattere, ma il numero intero -1. Inserire il risultato di
getchar () in un int, per poter fare il confronto con EOF e poi
verificare di utilizzare solo i caratteri (nel campo da 0 a 255) come indici del vettore
- Per comporre due codici ad 8 bit in uno a 16 si può sommare il primo codice letto
con il secondo moltiplicato per 256.
- Fare attenzione che la divisione di due numeri interi è un numero intero, quindi, per ottenere delle Ps attendibili occorrerà convertire il primo operando in
float prima della divisione, per forzare una sivisione in virgola mobile.
- Fare attenzione che il logaritmo di 0 non è definito, quindi non cercare di calcolare
log (Ps) se la frequenza relativa è 0, pena un errore matematico
- Per trovare i 10 simboli piu' frequenti:
- predisporre un array che possa contenere i 10 codici
- Calcolare per ognuno il massimo dell'array delle frequenze, con il solito algoritmo
- Dopo ogni calcolo di massimo, azzerare la frequenza dell'elemento con frequenza massima
in modo da trovare come massimo il successivo nell'ordine al ciclo successivo
- La funzione log10() non fà parte della libreria standard del C, ma della
libreria matematica. Per usarla, con cc occorre aggiungere l'opzione -lm
Una possibile soluzione è la seguente:
// Tizio - Pinco - 3AIN
// Calcola l'entropia di una stringa considerando coppie di caratteri
#include <stdio.h> // Contiene le dichiarazioni delle funzioni standard
#include <math.h> // Contiene la definizione della funzione log10
#define DIM (256*256) /* Numero di combinazioni (due caratteri) */
main()
{
int i,j; // Contatori
int max; // Codice con il conteggio massimo
int vet[10]; // I 10 codici piu' frequenti
float ps; // Probabilita' di sorgente
float q=0; // Entropia
float it; // Informazione totale (in bit)
float itb; // Informazione Totale (in byte)
int a,b; // Codici letti, da comporre
int c; // Codice composto da due caratteri
int cc; // Contatore complessivo dei caratteri
int ca[DIM]; // Array delle frequenze relative
cc=0; // Inizializza il conteggio totale
// Inizializza il vettore dei conteggi parziali
for (i=0;i<DIM;i++)
{
ca[i]=0;
}
printf("Caratteri : ");
do { // Ciclo su tutti i caratteri letti
a=getchar(); // Legge il primo carattere della coppia
b=getchar(); // Legge il secondo carattere della coppia
c=b*256+a; // Compone i due caratteri in un codice a 16 bit
if(a!=EOF && b!=EOF) // Se non ha finito il messaggio
{
ca[c]++; // Conta la coppia di carattere (nel contatore del sio codice)
cc++; // Conta la coppia di carattere (nel totale)
}
}while(a!=EOF && b!=EOF); // Ripete fino a che l'input non e' terminato
// Calcolo l'entropia
for(i=0;i<DIM;i++) // Per ogni codice possibile
{
if (ca[i]!=0)
{
ps=(float)ca[i]/(float)cc; // Calcolo la probabilita' di sorgente
// Aggiungo il contributo del codice all'entropia (con segno -, subito)
q-=(ps * (log(ps)/log(2)));
}
}
// Individuo i 10 codici piu' frequenti
for(i=0;i<10;i++) // Per ognulo degli elementi
{
// Calcolo il massimo
max=0; // Codice con conteggio massimo, inizialmente il primo
for(j=1;j<DIM;j++) // Ciclo su tutti i codici
{
if (ca[j]>ca[max]) // Se il codice corrente ha conteggio maggiore
// di quello con il 'massimo corrente'
{
max=j; // Accetta il codice corrente come nuovo massimo
}
}
vet[i]=max; // Immagazzina il codice con conteggio massimo
ca[max]=0; // Azzera il conteggio di quel codice, per trovare il successivo
}
it=q*cc; // Calcolo l'informazione totale in bit
itb=it/8; // Calcolo l'informazione totale in byte
// Stampa finale dei risltati
printf("Sono stati inseriti %d caratteri\n",cc);
printf("Le 10 coppie di caratteri più frequenti sono :\n");
for(i=0;i<10;i++)
{
printf("'%c%c' ",vet[i]/256,vet[i]%256);
}
printf("\nL'entropia e' : %f\n",q);
printf("L'informazione tot e' : %f bit\n",it);
printf("L'informazione tot e' : %f byte\n\n",itb);
}
|
Per provare il programma, scaricare il sorgente, compilarlo
con il comando cc entropia1.c -lm ed eseguirlo con il comando ./a.out.
[Home Page dell'ITIS "Fermi"]
[Indice Terza]
[Precedente]
[Successivo]
© Ing. Stefano Salvi - Released under GPL licence
|
