Fondamenti di informatica

CODIFICA DEI NUMERI INTERI RELATIVI

Codifica con modulo e segno

Il primo bit a sinistra rappresenta il segno (bit di segno) i rimanenti bit codificano il

numero:

- 0 per numeri positivi

- 1 per numeri negativi

Codifica inefficiente:

-il numero 0 ha 2 rappresentazioni per lo zero

-con 3 bit dovremmo poter rappresentare 8 elementi distinti, invece ne rappresentiamo solo 7 (due volte 0)

-l’operazione di somma si deve tener conto dei segni degli addendi, cosa che non avviene con questa codifica

Complemento a due

Una codifica più efficiente per i numeri interi con segno è la codifica a complemento a due.

In complemento a due, il primo bit viene considerato negativo e prende il nome di bit di segno. Tuttavia, porta

molta più informazione.

Con questa codifica, con N bit possiamo rappresentare effettivamente valori distinti;

N

2

ad esempio con tre bit possiamo rappresentare 8 valori distinti, da -4 a +3.

Nella codifica a complemento a due, con N cifre, posso rappresentare tutti i numeri nell’intervallo: [ N−1 N−1

−2 ,2 −

]

1]

Conversione da decimale a binario

Procedimento:

- Per convertire un numero positivo (in base 10) in complemento a due si usa il solito procedimento.

- Per convertire un numero negativo (in base 10) in complemento a due si usa il seguente procedimento:

o Controllo che il numero sia compreso nell’intervallo di numeri rappresentabili

o Converto il numero in binario

o Inverto tutte le cifre (0→1, 1→0)

o Sommo 1 al risultato ottenuto dal passo precedente

Esempio: si converta il numero 105 in binario e il numero -105 in binario (complemento a 2) in 8 bit

!! importante: se il numero non è lungo 8 bit aggiungo gli 0 a sinistra che devo contare quando sommo 1

Conversione da binario a decimale

Per ottenere un numero con segno data la sua rappresentazione in complemento a due:

1.Se il primo bit è 0 il numero è positivo: per calcolare il valore assoluto si esegue la conversione da binario a

decimale

2.Se il primo bit è 1 il numero è negativo:

-Si ignora il primo bit

-Si invertono i restanti bit

-Si converte il numero da binario a decimale

-Si somma uno al numero ottenuto per ottenere il valore assoluto del numero negativo

Esempio: si converta il numero 1011 da complemento a due in decimale

Oppure

Esempio: si calcoli il numero minimo di bit per eseguire l’ operazione (8)+(-1): converto 8 e -1 in binario,

sommo e poi riconverto in decimale per verificare che la conversione sia giusta

Problema di overflow

L'overflow si verifica quando un valore supera il limite massimo che può essere rappresentato da un tipo di

dato.

Esempio di overflow nel sistema binario dovuto a operazioni aritmetiche:

-5 + 4 = 9 (in sistema decimale)

-abbiamo usato solo una cifra decimale per il risultato

Tornando all’ esempio del fattoriale:

Quando chiedo il fattoriale di n>12, vado in overflow

Char

–caratteri

–1 byte (8 bit)

–numeri da -128 a 127

–“conversione” in carattere tramite ASCII

c=97

Printf (“%d”,&c) stampa 97

→

Printf (“%c”,&c) stampa ‘a’

→

Tabella ascii corrispondenza numero-carattere

→

Sintassi in c:

Char carattere;

Printf ("inserisci un carattere");

Scanf (“%c”,&carattere);

-” “ i doppi apici indicano una sequenza di caratteri

-’ ‘ i singoli apici indicano 1 carattereì

Importante

!! anche l’ invio è considerato come un carattere devo quindi mettere lo spazio “ c” lo spazio indica che

→ →

devo ignorare il primo carattere che è l’ invio che premo dopo l’ istruzione

printf("Vuoi calcolare un diverso fattoriale? (s/n):");

!! char accetta come input un solo carattere!! (per le sequenze di caratteri devo usare le stringhe)

char

Un è in realtà un intero tra -128 e 127 (di solito), che rappresenta il codice ASCII del carattere.

Posso fare delle operazioni con i char:

char lettera = 'a';

lettera+= 1;

printf("%c\n", lettera); // stampa 'b'

char lettera = 'c';

int posizione = lettera - 'a'; // vale 2

Array

Un array è una struttura dati che memorizza un insieme di elementi dello stesso tipo in posizioni di memoria

contigue.

In memoria l’array è composto da celle di memoria adiacenti: []:

Un array si dichiara specificando il tipo di dati e la dimensione tra parentesi quadre

! la dimensione dell’ array può essere cambiata solo in fase di dichiarazione (devo stabilire all’ inizio del

programma una dimensione massima), ha una lunghezza fissa ovviamente, come nella rappresentazione

→

dei numeri ho una dimensione massima che può assumere l’ array

Per definire la dimensione di un vettore posso utilizzare #define

Accesso agli elementi

Per riferirsi a un elemento, si specificano:

nome dell’array

▪Il posizione dell'elemento (indice)

▪La

Il primo elemento ha indice 0, l’n°elemento dell’array è v[n-1]

•Sintassi:

Salvare dati in un array

Utilizzo : scanf(“%d”, “&numeri[i]);

Per esempio, devo scrivere un algoritmo che mi permetta di inserire n numeri in un array

Visualizzare gli elementi di un array

utilizzo un ciclo for

Se al posto di 10 dati volessi inserirne 100? Generalizzo utilizzando la direttiva #define

#define è una direttiva del preprocessore che consente di definire costanti. Queste costanti vengono

sostituite dal preprocessore con il loro valore definito prima della fase di compilazione del codice sorgente.

Sintassi:

in testa al programma scrivo:

#define LUNG_SEQ 100

Così possiamo adattare la lunghezza del vettore alle eventuali mutate esigenze senza riscrivere la costante

100 in molti i punti del programma.

Il preprocessore sostituisce nel codice LUNG_SEQ con 100 prima della compilazione. La lunghezza dell’array,

quindi, anche in questo caso è decisa al momento della compilazione del programma. Nella dichiarazione

degli array non si usano mai variabili per specificare la dimensione.

Come si rappresenta un’ immagine? Devo utilizzare una griglia e cioè una matrice all’ interno della quale, in

ogni cella è contenuto un pixel e cioè un punto.

Introduciamo quindi il concetto di matrice

Matrici

una matrice è un array bidimensionale (o multidimensionale) che memorizza dati in righe e colonne.

Immagini→ matrice in 2 dimensioni

Video frame→ matrice in 3 dimensioni

Dichiarazione di una matrice:

Dichiaro il tipo, dimensione ed elementi

float F[20][20][30];

F è una matrice 3D di 20x20x30 variabili di tipo float (12.000!)

Le dimensioni delle matrici, come per gli array,devono essere note a priori, ovvero a compile time

Somma di matrici

Due matrici A e B si possono sommare se hanno le stesse dimensioni

La loro somma A+B è definita come la matrice i cui elementi sono ottenuti sommando i corrispettivi elementi

di A e B.Formalmente:

Moltiplicazione tra matrici

La moltiplicazione è definita soltanto se il numero di righe di B coincide con il numero n di colonne di A. Il

risultato è una matrice con lo stesso numero di righe di A e lo stesso numero di colonne di B. L’elemento di

posizione (i,j) è dato dalla somma:

Matrici (array di array) in memoria

Esempio: dato un cubo di 3x2x4 (matrice 3x2x4 di 24 elementi) come viene rappresentato in memoria?

1)considero char data [dx]

2) introduco char data [dy] in memoria ho quindi 3 array che a loro volta contengono 2 array

→

3)introduco char data [dz] in memoria ho quindi 3 array che a loro volta contengono 2 array che a loro

→

volta ne contengono 4

Quindi… come rappresento il pixel?

Il pixel è un colore che viene codificato mediante il formato RGB (red, blue, green)

Red, Green, Blue)

Il modello di colore RGB (acronimo di rappresenta le immagini combinando diverse intensità

dei tre colori primari: rosso, verde e blu per rappresentare e visualizzare immagini a colori nei dispositivi

elettronici.

Ogni componente assume un valore da 0 a 255 (8 bit per canale, 24 bit totali per pixel).

Struttura fatta da 3 campi intesi come char per una questione di memoria: non è necessario rappresentare

tantissime sfumature di colore (l’ occhio umano non sarebbe in grado di percepire) poiché ogni canale

→

occupa 1 byte e un pixel è composto da 3 canali (rosso, verde e blu), l'intero pixel occupa 3 byte.​

unsigned char

Utilizzare un tipo di dato come consente di risparmiare spazio in memoria senza sprechi,

int (che occuperebbero 4 byte per canale, char→ 8 bit, int→32 bit)

rispetto a tipi come char

Inoltre, i valori per i colori RGB non superano mai 255, quindi un tipo è sufficiente per memorizzarli

senza sprecare memoria.

Che cos’è una struct?

struct

In C, una (abbreviazione di "structure") è un tipo di dato che permette di raggruppare variabili di

diversi tipi sotto un unico nome. È utile per creare tipi di dati complessi, come per esempio rappresentare una

persona con nome, età e altezza, o un punto in uno spazio tridimensionale con coordinate.

In memoria, in base al tipo della variabile viene occupato uno spazio diverso

Una struttura può essere utilizzata anche con la sintassi seguente. !! va dichiarata prima del main

Typedef struct

array=dati omogenei

strutture=dati non omogenei

!uso gli indici se voglio memorizzare più dati in un singolo campo

Il typedef mi permette di creare un nuovo tipo di dato. In fase di dichiarazione nel main, al posto di scrivere

int numero; scriverò record numero;

Esempio

// Definisco un nuovo tipo chiamato "Punto"

typedef struct {

int x;

int y;

} Punto;

int main() {

// Uso il nuovo tipo Punto

Punto p1; punto=int=char…

p1.x = 10;

p1.y = 20;

printf("Punto: (%d, %d)\n", p1.x, p1.y);

return 0;

}

Posso usare un typedef dentro un altro. Per esempio:

Per l'inserimento dei dati, accedo a ogni posizione nel seguente modo:

&dati[i].a.y

&dati[i].b.y

…

Funzioni

Esempio: voglio calcolare il coefficiente binomiale di un numero

Parto dalla formula, e osservo che all’ interno è contenuto il fattoriale di n, di k e di n-k.

Dovrei scrivere 3 volte il codice per il calcolo del fattoriale. Per risparmiare codice utilizzo

una funzione.

In C, le funzioni sono blocchi di codice che eseguono un compito specifico. Sono utili per rendere il codice più

organizzato, riutilizzabile e leggibile.

Per definire una funzione: .h)

Scrivere il