 |
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
- 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
- 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
// Calcolo dell'informazione e dell'entropia di una stringa
#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; // Contatore
int cl[DIM]; // Array delle frequenze relative
int ch,ch1; // Codici letti, da comporre
int comp; // Codice composto da due caratteri
int c; // Contatore complessivo dei caratteri
float ps; // Probabilita' di sorgente
float somm; // Entropia
printf("Caratteri: ");
// Inizializzazione frequenze relative
for(i=0;i<DIM;i++)
{
cl[i]=0;
}
c = 0; // Inizializza il contegio dei caratteri
somm = 0.0; // Inizializza l'entropia
do { // Ciclo su tutti i caratteri letti
ch=getchar(); // Legge il primo carattere della coppia
ch1=getchar(); // Legge il secondo carattere della coppia
comp=ch+ch1*256; // Compone i due caratteri in un codice a 16 bit
if(ch!=EOF && ch1!=EOF) // Se non ha finito il messaggio
{
c++; // Conta la coppia di carattere (nel totale)
cl[comp]++; // Conta la coppia di carattere (nel contatore del sio codice)
}
} while (ch!=EOF && ch1!=EOF); // Ripete fino a che l'input non e' terminato
for(i=0;i<DIM;i++) // Per ogni codice possibile
{
if(cl[i] > 0) // Se ho letto almeno un carattere con quel codice
{
ps= ((float) cl[i])/c; // Calcolo la probabilita' di sorgente
// Aggiunge il contributo del codice all'entropia (con segno -, subito)
somm = somm - (log10(ps)/log10(2))*ps;
}
}
// Stampa finale dei risltati
printf("Sono stati inseriti %d caratteri\n",c * 2);
printf("L'entropia della stringa inserita e': %f\n",somm);
printf("L'informazione in bit della stringa inserita e': %f\n",somm*c);
printf("L'informazione in byte della stringa inserita e': %f\n",(somm*c)/8);
}
|
Per provare il programma, scaricare il sorgente, compilarlo
con il comando cc comp.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
|
