|
Siamo arrivati agli esercizi in linguaggio C. In questo momento 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).
Il programma dovrà stampare:
- Il numero di carateri 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 8 bit, quindi avremo
28 = 256 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
- 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:
// Pinco - Tizio - 3AIN
// Informazione e 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 /* dimensione del vettore, pari a 2^8 */
main()
{
int n, i; // Variabili per i contatori
int ch; // Codice letto
int cl[DIM]; // Array delle frequenze relative
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 prossimo carattere
if(ch!=EOF) // Se non ha finito la stringa
{
c++; // Conta il carattere (nel totale)
cl[ch]++; // Conta il carattere (nel contatore del sio codice)
}
} while (ch != EOF); // Ripete fino a che l'input non e' terminato
// Ciclo del calcolo dell'entropia
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);
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\n",(somm*c)/8);
}
|
Per provare il programma, scaricare il sorgente, compilarlo
con il comando cc primo.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
|