Laboratorio di Calcolo1 AA 2006/2007Canale A Prof. G.Ciapetti Testi consigliati: Programmazione...

Laboratorio di Calcolo 1

Laboratorio di CalcoloAA 2006/2007Canale A

Prof. G.Ciapetti

Testi consigliati:

Programmazione scientifica – Barone, Marinari, Organtini, Ricci-Tersenghi – Pearson education

C-Didattica e programmazione. – Kelley & Pohl - Addison e Wesley

Programmare in C. – M.Liverani – Progetto Leonardo

Struttura del corso:

~ 20 h lezioni

~ 28 h esercitazioni in laboratorio ( 8 esercitazioni x 3.5 h – 14:15 18:00 - Classe Win e classe Linux). Valutazione alla fine dell’esercitazione.

Max assenze 2. Ultime 2 (realizzazione programma) valutate anche come prove in itinere.

Prova finale (se prove in itinere non OK) con realizzazione di un programma.

Sito: www.roma1.infn.it/people/ciapetti/labcalc/index.htm


Sistemi Informatici

•Struttura generale (dai PC ai grandi Mainframes):

•Hardware (componenti fisici del sistema)

•Firmware ( microprogrammi permanenti )

•Software ( programmi eseguiti dal sistema)

•Software:

•Sistemi operativi

•Software di comunicazione

•Programmi applicativi

•Hardware:

•CPU

•Memoria centrale

•Periferiche (tastiera, mouse, video, dischi, stamp….)


•Architettura hardware:

•Basata sul modello della macchina di Von Neumann (Priceton, 1946).• “IAS machine” a valvole. Programma in memoria.

Central Processing Unit: svolge operazioni logiche e aritmetiche, gestisce il trasferimento dei dati fra memoria centrale, registri di calcolo e memorie periferiche

Memoria Centrale: contiene (parte) delle istruzioni che i processori della CPU devono eseguire e i dati locali

Intrefaccia periferiche: gestisce tutto il traffico di informazioni in ingresso/uscita ( I/O )

Bus di sistema

CPU Memoria centrale

Interfaccia periferiche

Memorie di massa

Terminali Stampanti

Unita’ logico-aritmetica

Reti di connessione


Home computer 2004 da rivista 1954


Portatile –The next generation


CPU Memoria Centrale

Funzionamento Memoria


CODIFICA DEI NUMERI

Sistema “posizionale”:

•Numero sequenza di simboli il cui valore dipende dalla posizione

Noi utilizziamo un sistema di numerazione posizionale “arabico” (10 simboli: 0,1,………9)

Alternativa; Sistema additivo:

•Numero sequenza di simboli il cui valore dipende dalla somma dei simboli

•Numeri romani: I, V, X, L, C, D, M 3000 MMM

Sistemi posizionali: caratterizzati dalla base p ( “p” simboli diversi)

Alfabeto: (p simboli)

Nbase p anan-1….a1a0 ai = generico simbolo ( )

m = n+1: numero delle cifre

Np = an pn + an-1 pn-1 +.......+ a1 p1 + a0 p0 = n0 i ai pi

Con m cifre pm numeri diversi da: 0 pm-1

SISTEMA ARABICO 10 simboli p=10

CODIFICA DELL’INFORMAZIONE


p=10 (decimale) (0,…….9)

33110 = (3*102 + 3*101 + 1*100)

p=2 (binario) (0,1)

1010010112 = (1*28 + 0*27 + 1*26 + 0*25 + 0*24 + 1*23 + 0*22 + 1*21 + 1*20)

= 33110

p=8 (ottale) (0,1,………..7)

5138 = (5*82 + 1*81 + 3*80) = 320 + 8 + 3 = 33110

p=16 (esadecimale) (0,1,………..9,A,B,C,D,E,F,)

14B16 = (1*162 + 4*161 + 1*160) = 33110

In un calcolatore la codifica è binaria Facile utilizzare (in elettronica) fenomeno fisico in due stati diversi:

Tensione (alta/bassa)Magnetizzazione (n/s)Luce-buio

Unità di informazione in codifica binaria: bit (0/1)Byte (8 bit)

Max n decimale rappresentabile con n bit (Con n cifre pm numeri diversi da: 0 pm-1 ): 8 bits -> 256-1 16 -> 65532-1 32 -> ~ 4.29 109

64 -> ~ 1.84 1019


DECIMALE0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

..

32

..

64

..

128

BINARIO0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

1011

1100

1101

1110

1111

10000

..

100000

..

1000000

..

10000000

OTTALE0

1

2

3

4

5

6

7

10

11

12

13

14

15

16

17

20

..

40

..

100

..

200

ESADECIMALE0

1

2

3

4

5

6

7

8

9

A

B

C

D

E

F

10

..

20

..

40

..

80


Codifica caratteriCodice ASCII (American Standard Code for Information Interchange).

7 bit 128 caratteri : caratteri di comando, alfanumerici, segni.

Ogni carattere 1 byte

Ottavo bit : bit di parita’ 0 o 1 in modo che il n di 1 nel byte sia pari (individuare errori di trasferimento).


Codifica immaginiImmagine suddivisa in punti (pixel). Per ogni punto n bit che definiscono il colore (o il tono di grigio). Risoluzione misurata in dpi (dot per inch).

Standard di codifica che possono permettere di ridurre le dimensioni dell’ immagine in memoria ( 1152*864 ~ 3 Mb usando 3 bytes per def. colore)

BMP

TIFF

JPEG

……


Programmazione.

Risolvere un problema in modo automatico. Trovare un “ algoritmo” che, dato un certo set di informazioni in input fornisca la soluzione del problema (output).

Algoritmo: insieme di istruzioni (basate su un “Linguaggio di programmazione”) che, esguite in un certo ordine, trasformano i dati di input nella soluzione.

Linguaggio di programmazione: istruzioni (“statements”) interpretabili dalla CPU della macchina per effettuare operazioni aritmetiche o logiche sui dati. Necessaria traduzione in “linguaggio macchina”.

Programma: insieme di algoritmi per risolvere problemi complessi.

Esiste una moltitudine di linguaggi con set di istruzioni differenti e con differenti “ livelli”

basso livello : vicino all’ hardware alto livello : vicino al linguaggio naturale

Linguaggio macchina : istruzioni (sequenze di bit) che possono essere eseguite direttamente dai circuiti ( CPU ) del calcolatore. Tre fasi : fetch (caricamento), interpretazione, esecuzione.

Istruzione

Operando/i : locazione/i di memoria contenente i dati su cui operare

Codice operativo: operazione da fare

Assembly : Codici operativi (istruzioni) sono rappresentati tramite stringhe alfanumeriche (LOAD, STOR, ADD, DIFF, MUL, DIV, JUMP,HALT …….). Necessita traduzione (triviale) in linguaggio macchina.


Linguaggi di alto livello: Algoritmo e’ realizzato utilizzando 5 tipi base di istruzioni:

dichiarazioni di variabili e costanti e del loro tipo (non in tutti i linguaggi) Es. : int a , float b ;

istruzioni di assegnazione (mettere in una locazione di memoria risultato di una espressione aritmetica /logica). Es: c=a+b;

istruzioni di input/output (ingresso/uscita dati) Es. printf (“ risultato = %d \n”, c);

istruzioni condizionali (ramificare il flusso delle istruzioni a seconda del valore di una variabile logica) Es. if (a > b) {istruzioni}

istruzioni di ciclo condizionale (ripetizione un certo gruppo di istruzioni condizionata da variabile) Es. for(i=0; i<100; i++) {istruzioni}

nei linguaggi OO (C++,Java) anche altre istruzioni base

Per eseguire un programma: preprocessore : esegue istruzioni per preparare la compilazione del programma compiler : traduzione istruzioni in linguaggio macchina (controllo sintassi e logica

istruzioni errori di compilazione)

linker : collegamento con altri programmi di utilita’ gia’ compilati contenuti in “librerie”

debugger : eliminazione di errori al livello di esecuzione


Tanti linguaggi a seconda della funzione:

Basic (Beginner All-purpose Instruction Code) : applicazioni didattico/scientifiche.

Cobol : applicazioni gestionali

Fortran, Pascal: applicazioni scientifiche (numeriche)

C : progetto di sistemi operativi e basi dati

C++, Java : applicazioni orientate ad oggetti

Lisp, Prolog: applicazioni di AI

.............................

.............................

Linguaggi


Grafi di flusso.

Progettazione simbolica degli algoritmi per via grafica. I simboli rappresentano i 5 tipi base di istruzioni.

Istruzione ciclo

Istruzione condizionale

Istruzione di assegnazione

Istruzione di input/output


Prodotto di 2 numeri interiSomma di 100 numeri

X x Y =

sommare X volte Y

Z = Y+Y+Y+Y........ X volte


Programmare in C

•Programma in C : insieme di funzioni (funzione speciale : main)

•Funzione : insieme di istruzioni.Puo’ ricevere o no dati dalla funzione chiamante. Alla fine dell’ esecuzione puo’ ritornare un solo dato. Il main viene chiamato dal sistema operativo. Le istruzioni operano su un inseme di variabili o costanti.

•Istruzioni:

-dichiarazioni: variabili usate devono essere definite , incluso il loro tipo.

tipo: int (interi), float/double (numeri razionali, detti anche in virgola mobile) , char (carattere)

qualificatori di tipo: signed, unsigned, short, long, const

-istruzioni di assegnazione, condizionali, di ciclo.

-assegnazione: operano su variabili o su costanti e assegnano risultato a nuova variabile.

nome_variabile = numero ;

nome_variabile = espressione ;

-condizionale: se una certa condizione e’ vera o falsa eseguire differenti istruz.

-ciclo: ripetere blocco di istruzioni fino a che una certa condizione e’ vera/falsa


Costanti e variabili.

Il programma attribuisce un nome e un valore ad ogni costante o variabile che appare nelle dichiarazioni (attribuisce un indirizzo in memoria e alloca un certo numero di bit a seconda del tipo definito nella dichiarazione).

Nome: deve iniziare con carattere alfabetico. Lunghezza arbitraria ma definito dai primi 31 caratteri. Caratteri possono essere maiusc/minusc., numerici, simboli (non usare: -, /, $, %, &. Att. alle parole risevate (vedi libro).

Tipo:

int

Numeri

short

Floating Interi

longfloat double Long double

float a ; double b;...... short i; int j;


Struttura funzione:

tipo (di ritorno) nome-funzione (argomenti in ingresso)

/* se non ritorna nulla tipo = void. Argomenti forniti dal chiamante; se non ci sono : ( ) */

// commenti contenuti in una sola linea

{ dichiarazioni (terminano SEMPRE con ; )

istruzioni (terminano SEMPRE con ; )

return (valore) ; (valore puo’ mancare) }

/* Programma Base */

#include <stdio.h>

#include <math.h>

#define PIGRECO 3.14159/* -------------------------------------------------*/ int main( ) {/* dichiarazione e assegnazione variabili*/ int a, b , c=180 , d;/* ingresso dati */ ……………;/* istruzioni per effettuare l’ algoritmo */ d=(a+b)/c;/* stampa risultato algoritmo */ ……………; return 0; }

•Direttive al preprocessore


•Direttive al preprocessore: iniziano con # ; in genere poste all’ inizio del programma.

#define nome valore tutte le volte che nel codice appare nome viene sostituito con valore

#define SUMQ(a,b) ((a*a)+(b*b)) tutte le volte che appare nel codice SUMQ(...) viene sostituito

con ((a*a)+(b*b)) Macro

es. c = SUMQ(7,4) c = 49 + 16

#include <nome.h>

#include “miofile.h” (il file deve essere contenuto nella stessa directory dove risiede il codice)

nome.h : header file. Contiene lista (i prototipi) di funzioni delle librerie del C ed eventuali macro.

stdio.h : funzioni I/O

math.h : funzioni e macro matematiche

string.h : funzioni per manipolare stringe di caratteri

stdlib.h : funzioni di utilita’

time.h : manipolazione ora/data

#if , #ifdef , #ifndef , #endif , #undef servono ad inserire o meno parti di codice nel programma (vedi dopo)


Istruzioni di dichiarazione.

int nome1, nome2 ;

float nome3 = 12.314 ;

int x = y = z = 0 ;

Istruzioni di assegnazione.

nome_variabile = espressione ;

espressione : costante num., altra variabile, risultato operazione fra variabili (con operatori aritmetici)

a = pigreco ;

a = 1.234 ;

a = b + c/d*e ;

k = k+1;

Nota : se tipo variabile a destra diverso da sinistra viene effettuata conversione

Operatori aritmetici (binari).

+ , - , * , / , %

Note : % solo ad interi (resto divisione). Operatori * , / , % precedenza su +, -

Se operandi tipo diverso si converte a precisione superiore.


Operatori aritmetici (unari).

- , & , * & : restituisce indirizzo operando ( &a : indirizzo in memoria di a)

* : valore contenuto nell’ indirizzo ( *p : valore contenuto in indirizzo p)

- : cambiamento di segno

Operatori incremento e decremento: ++ , --Possono essere prefissi o suffissi

w = x++ - y w = ++x – y

w = x – y x = x + 1

x = x + 1 w = x - y

Operatori di assegnazione abbreviata : += , -= , *= , /= Quando operando e’ anche la variabile risultato:

x += 3 y /= 3

x = x + 3 y = y / 3

Operatore aritmetico (ternario) ?

( a > b ) ? ( max = a ) : ( max = b )

max = ( a > b ) ? a : b


Altri operatori

Operatore di cast (o conversione).

Serve a modificare temporaneamente il tipo di una variabile. Istruzione: (new type) nome-variabile

int i=3; double a; a = (double) i / 2;

Operatore di sizeof(dimensione di ).

Serve a sapere le dimensioni (in n di bytes) di una espressione o di un generico oggetto :

n = sizeof(…….);

n = sizeof(int);

n = sizeof(a);

int x[99];

n = sizeof(x); (n sara’ uguale a 99 x 4 = 396 bytes)


VARIABILI E OPERATORI LOGICI (Algebra di Boole)

Variabile logica : vero falso

(1) (0)

Operazioni logiche:

a AND b (2 operandi) = vero se ambedue operandi veri

a OR b (2 operandi) = vero se almeno 1 operando vero

NOT a (1 operando) = cambia valore operando

AND OR NOT

(b) 0 1 (a) 0 1

0 0 0 0 0 1 0 1

1 0 1 1 1 1 1 0

&& AND

|| OR

! NOT


Operatori di relazione

a < b : se vera ritorna valore 1 (vero) altrimenti 0 (falso)

a <= b : se vera ritorna valore 1 (vero) altrimenti 0 (falso)

> maggiore

>= maggiore o uguale

= = uguale

!= diverso

Confronto di due espressioni; ritorna valore 1 se vera altrimenti 0. Creano delle condizioni logiche.

Operatori di relazione hanno precedenza su operatori logici .


Istruzioni di ciclo

while

Servono a far ripetere un gruppo di istruzioni fino a quando non si verificano certe condizioni.

for

while (condizione) { istruzioni ; }

Analogo al while ma usato per cicli basati su una variabile che aumenta/diminuisce ad agni iterazione. Stop quando raggiunge un certo valore.

for ( espress1; espress2; espress3)

{

istruzioni ;

} espress1 : variabile di ciclo

espress2 : se vera continua ciclo

espress3 : modo di modifica della variabile di ciclo

Es. : for( k=0; k<=10; k++ ) { istruzioni; }

Fino a che condizione e’ vera il blocco di istruzioni fra graffe viene ripetuto.


do/while Analogo al while solo che il controllo viene effettuato alla fine del

ciclo.

do { istruzioni; } while (condizione)

break

Per saltare la corrente iterazione del ciclocontinue

Per uscire da un ciclo


#include <stdio.h> #include <math.h> #include <stdlib.h> float gauss(float,float);//---------------------------------------------------------------------- int main() {int i,j,nevent=20;float x,mu,sigma;

/* Inserimento parametri da parte dell'utente */printf ("mu sigma= ");scanf ("%f %f", &mu, &sigma);

for(i=0;i<=nevent;i++){x=gauss(mu,sigma);

printf("mu = %f, sigma = %f x = %f \n",mu,sigma,x); } return (0);}

//------------------------------------------------------float gauss(float mu, float sigma){int i;float sum;

sum=0.;for (i=1;i<=12;i++) sum+=rand()/(RAND_MAX+1.);sum=(sum-6.)*sigma+mu;return(sum);}

//------------------------------------------------------

Esempio : GaussGen.c

Generare un numero con funzione di

distribuzione gaussiana ( , ).

Algoritmo:

sommare 12 numeri casuali con f(x) uniforme fra

0 e 1, sottrarre 6,moltiplicare per e aggiungere


/* while */ float radiant; int degree = 0; while (degree <= 360) { radiant = degree*PIG/180; printf(" %6d %9.6f \n" , degree,radiant) ; degree += 10 ; }/* for */ for (degree = 0 ; degree <= 360 ; degree += 10 ) { radiant = degree*PIG/180; printf(" %6d %9.6f \n" , degree,radiant) ; }/* do/while */ int degree = 0 do { radiant = degree*PIG/180; printf(" %6i %9.6f \n" , degree,radiant) ; degree += 10 ; } while (degree < 370 )


Algoritmo di Erone per calcolo radice quadrata

Supponiamo che a0 sia una approssimazione per eccesso di SQRT(x);

11

1

001

0

0

00

0

0

)(2

1

)(2

1

nnn

nnn

aaxa

a

xaa

a

xaa

xdidifettoperzioneapprossimaa

x

a

xx

xa

xa

a

x

xa


Array e puntatori

Int s[10], double x[100] ;

Definiscono in memoria vettori (array). Vanno utilizzati come:

x[ i ] ;

ATT: il primo elemento del vettore sara’: x[0].

Inizzializzazione: double x[100] = {1.,2.,3.,4.,……} ;

int s[10] = {0} ;

int s[ ] = {1,0,3,42}; ( dimensioni di s = 4)

for(k=0;k<=9;k++) s[k] = 99;

E’ possibile dichiarare la lunghezza del vettore:

#define LEN 10 int n = 3;

float x[LEN * 2]; float x[n];

NON e’ possibile leggere il valore di n a run time (ATT. non da errore di compilazione).

ATT. nessun controllo se indice eccede valore max delle dimensioni, risultato non prevedibile.

Array bidimensionali:

float a [ 2 ] [10] ; sinistra indice riga; destra indice di colonna. In memoria come vettore unidimensionale memorizzato per righe.

a(1,1) a(1,2) ……a(1,10) a(2,1)………a(2,10)


Per gestire array molto usati (in particolare per passare vettori a funzioni) i puntatori .

int a[10];

int *pa; (pa e’ un intero usato come puntatore)

pa = &a[ 0] ; (indirizzo in memoria di a [0] )

pa = a ; equivalente alla precedente. Il nome di variabile tipo vettore e’ interpretato come

l’indirizzo del suo primo elemento. Quindi &a[ i ] e (a+i) sono equivalenti.

x = *pa; (mette in x il valore di a [0] )

x = *(pa+3); (mette in x il valore di a [3] )

x = *(a+3); (equivalente alla precedente)

ATT. pa e’ una variabile a non lo e’; quindi pa = a pa++ corretto

a = pa a++ non corretto


Le funzioni

Algoritmo complesso puo’ essere suddiviso in sottoalgoritmi (funzioni) che vengono chiamati in una certa sequenza logica da uno “ steering”, cioe’ da una funzione principale (“ main”). Le funzioni possono a loro volta chiamare altre funzioni.

Una funzione ritornera’ un valore al programma chiamante e avra’ in ingresso uno o piu’ valori forniti dal chiamante.

Una funzione deve essere dichiarata prima del main (prototipo della funzione) e successivamente deve essere definita.

Dichiarazione:

tipo_ritorno nome_funz ( tipo_par1, tipo_par2,………)

es. float funz (int, double,double, ….);

NB. #include <aaaaa.h> inserisce una lista di prototipi delle funz. di libreria (anche macro e costanti)

Definizione:

tipo_ritorno nome_funz ( tipo_par1 par1, tipo_par2 par2,………) {

definizioni;

istruzioni;

return (valore);

}

Utilizzo (chiamata della funzione):

a = nome_funz( par1, par2, .......); se tipo ritorno e’ void nome_funz( par1, par2, .......);


Es. double area (float, float);

int main(){

float aa,h,b,s;

s = 2 * (b+h);

aa = area (b, h);

printf(“ perimetro = %f area = %f\n”, s,aa);

return (0);

}

double area ( float base, float altezza){

double s;

s = 0.5*(base*altezza);

return ( s ) ;

}

Le variabili di una funzione hanno visibilita’ “locale”. Si possono (!! ma e’ pericoloso!!) definire variabili “globali”, cioe’ visibili da tutte le funzioni del programma. Vanno dichiarate prima del main.

Il passaggio dei parametri avviene per “valore” . Se si vuole che la eventuale modifica degli argomenti sia “visibile” anche dalla funzione chiamante passare gli “indirizzi” delle variabili.

Se si vuole passare alla funzione un vettore in genere si trasmette l’ indirizzo dell’ elemento 0 del vettore.


Es. Funzione scambia (NO)

void scambia (float,float);

int main(){

float x,y;

x=16.;

y=8.;

scambia(x,y);

return (0);

}

void scambia(float a, float b){

float temp;

temp = a;

a = b;

b = temp;

return;

}

Es. Funzione scambia (OK)

void scambia ( float *, float *)

int main(){

float x,y;

x=16.;

y=8.;

scambia(&x,&y);

return (0);

}

void scambia(float *pa,float *pb){

float temp;

temp = *pa;

*pa = *pb;

*pb = temp;

return;

}


/* Vector handling I */

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#define NMAX 100

int leggiv(float *);

void stampav(float *,int);

//--------------------------------------------------------------

int main(){

int n,i;

float v[NMAX];

n=leggiv(v);

printf(" Il vettore di N= %d elementi:\n",n);

stampav(v,n);

return( 0);

}

//--------------------------------------------------------------

int leggiv(float x[]){

int i,nn;

printf("Inserire il n di componenti del vett:");

scanf("%d",&nn);

printf("Inserire le %d componenti del vett:\n",nn);

for (i=0;i<nn;i++) scanf("%f",&x[i]);

return (nn);

}

//------------------------------------------------------------------------------

void stampav(float x[],int n){

int i;

for (i=0;i<n;i++) printf("%f ",x[i]);

printf("\n");

return;

}

//------------------------------------------------------------------------------

Passaggio vettori a funzione


/* Vector handling II*/

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#define NMAX 100

int leggiv(float *);

void stampav(float *,int);

//-------------------------------------------------------------

int main(){

int n,i;

float v[NMAX];

n=leggiv(&v[0]);

printf(" Il vettore di N= %d elementi:\n",n);

stampav(&v[0],n);

return (0);

}

int leggiv(float *px){

int i,nn;

printf("Inserire il n di componenti del vett:");

scanf("%d",&nn);

printf("Inserire le %d componenti del vett:\n",nn);

for (i=0;i<nn;i++) scanf("%f",px+i);

return (nn);

//----------------------------------------------------------------------

}

void stampav(float *px,int n){

int i;

for (i=0;i<n;i++) printf("%f ",*(px+i));

printf("\n");

return;

}


Funzioni matematiche di libreria

( x tipo float); abs(x) se x int


Input/Output dei dati

printf Visualizza su schermo valori numerici di variabili e stringhe.

printf (“ strnga di controllo”,valore1,valore2,…..);

Stringa di controllo contiene testo e marcatori di controllo che definiscono il formato di uscita delle variabili.

printf(“var1= %f , var2=%i ,…” , var1, var2, ….);

I marcatori di conversione possono essere preceduti da specifiche di formato:

%5i %7.4f %.3e

La stringa di controllo termina con \ seguito da carattere (sequenza di escape) che controlla il comportamento della stampante ( \n : a capo).


scanf Serve per l’ immissione dei dati tramite la tastiera.

scanf (“%f %lf %i..”, &a, &b , &n , …….);

I valori letti ritornano alla funzione chiamante “ per indirizzo “.

La stringa di controllo contiene le specifiche di formato per la variabili da immettere. La scanf termina quando ha esaurito le specifiche di formato della stringa di controllo o quando c’ e’ inconsistenza fra specifica e valore digitato.


Un array di tipo char permette di gestire un insieme di caratteri (stringa):

char stringa[80];

printf(“Inserisci una frase”);

scanf(“%s”,stringa);

printf(“La frase inserita e’: %s \n”,stringa);

La stringa viene memorizzata come sequenza di caratteri terminata dal carattere nul ( \0 ); se si vogliono contare i caratteri contenuti nella stringa:

int i = 0;

while (stringa[i] != ‘\0’) i++ ;

printf( “Lunghezza frase %d caratteri \n”, i);

Se voglio aggiungere una seconda frase dentro stringa

scanf( “%s”,stringa2 );

for( i=0 ; stringa[i] != ‘\0’; i++) ;

for( j=0 ; stringa2[j] != ‘\0’ ; j++) stringa[i] = stringa2[j];

i++ ;

stringa[i] = ‘\0’ ;

Un altro modo per leggere/scrivere una stringa e’ uso di getchar()/putchar() :

for ( i=0 ; (stringa[i]=getchar() ) != ‘\n’; i++);

stringa[i] = ‘\0’ ;

for ( i=0 ; stringa[i]!= ‘\0’; i++) n = putchar(stringa[i]) ;

Stringhe


Per assegnare un valore a variabile di tipo char: caracter = ‘a’ ;

Per assegnare il contenuto ad una stringa: char line[] = “Nel mezzo del cammin di nostra vita”;

Non e’ possibile invece una assegnazione del tipo:

char line[100];

ERRATO line = “Nel mezzo del cammin di nostra vita”; (line e’ un puntatore!!!)

-------------------------------------------------------------------------------------------------------------------

Specificatori di formato per scanf e printf : %c (carattere) %s (stringa)

RICORDARE: scanf(“%s”,line); (line e’ un puntatore!!)

Per scrivere su una stringa : sprintf( line, “scrivereintero %d sustringa”,nn);

Per leggere da una stringa : sscanf(line,”%s %d %s”, str1,ii,str2);

Per convertire da stringa a numero: nn = atoi(stringa); aa = atof(stringa);

intero double


Funzioni di libreria( string.h ) per manipolazione stringhe :

strcpy ( stringa1 , stringa2) ;

strncpy (stringa1, stringa2, n); copia n caratteri di stringa2 su stringa1

strcat (stringa1 , stringa2) ; concatena stringa2 a stringa1

n = strcmp (stringa1 , stringa2) ; n=0 se uguali, +-1 se stringa1 >< stringa2

n = strlen (stringa); lunghezza della stringa (senza \0 )

Es.

int strlen (char s[] ) {

int i=0 ;

while ( i < MAX && s[i] != ‘\0’ ) i++ ;

return i ;

}

void converti (char s[] ){

int i = 0 ;

while ( i < MAX && s[i] != ‘\0’ ){

if ( s[i] >= 97 && s[i] <= 122) s[i] = s[i] - 32 ;

i++ ;

}

return;

}


I / O da file

Per scrivere/leggere dati da file (non da standard input/ output): definire un puntatore speciale di tipo FILE (che punta ad una “struttura” contenente informazioni sul file). associare al puntatore uno specifico file e definirne le modalita’ di apertura. chiudere il file alla fine del suo utilizzo.

FILE *fp1 ;FILE *fp2 ;

fp1 = fopen( “file1.dat”, “mode”) ;fp2 = fopen( “file2.dat”, “mode”) ;………………..fclose (fp1);fclose (fp2);Se ci sono problemi nell’ apertura del file fopen ritorna : NULL

mode:“r” solo lettura; “w” solo scrittura; se non esiste viene creato; il contenuto precedente viene perso“r+” lettura/scrittura; “w+” lettura/scrittura; se non esiste viene creato“a” solo scrittura; in append mode; se non esiste viene creato“a+” lettura/append; se non esiste viene creato


I / O formattato da file

Leggere/scrivere su file con formato definito da utente:

n = fprintf (fp, “specifica formato”,val1, val2, ……);

m = fscanf (fp, “specifica formato”, &val1, &val2, …..);

n : rappresenta il n di caratteri scritti o n negativo in caso di errore

m : numero di elementi letti o EOF in caso di fine del file di inputEs.int main() {FILE *fin;FILE * fout;float x1, y1 ;int n; fin = fopen( “filein.dat”, ”r” ); if(fin == NULL) {

printf(" error in input file\n"); return (0); }

fout = fopen( “/data/fileout.dat”, “w”);

while ( ( fscanf(fin, “ %f %f ”,&x1, &y1 ) != EOF) {

n = fprintf (fout, “%f, %f \n”, x1, y1) ;

} fclose(fin); fclose(fout); return( 0);

}


Histog.h

hh[nh*lmaxh]

0 100 200 300 400 ................................................................

np

nunder

npnover

nin


La ricorsione

Una funzione e’ ricorsiva se e’ in grado di richiamre se stessa. Non tutti i linguaggi permettono la ricorsione. Puo’ essere usata con formule ricorsive (es. fattoriale …..).


inserire il n di elementi della serie; <0 stop)20

i 0 fibonacci 0

i 1 fibonacci 1

i 2 fibonacci 1

i 3 fibonacci 2

i 4 fibonacci 3

i 5 fibonacci 5

i 6 fibonacci 8

i 7 fibonacci 13

i 8 fibonacci 21

i 9 fibonacci 34

i 10 fibonacci 55

i 11 fibonacci 89

i 12 fibonacci 144

i 13 fibonacci 233

i 14 fibonacci 377

i 15 fibonacci 610

i 16 fibonacci 987

i 17 fibonacci 1597

i 18 fibonacci 2584

i 19 fibonacci 4181

i 20 fibonacci 6765


Puntatori a funzioni

Se funzione deve poter operare su un’altra funzione (es. df(x)/dx ) e’ necessario poter indirzzare la generica funzione su cui operare

puntatore a funzione = variabile di tipo puntatore che contiene l’indirizzo in memoria in cui iniziano le istruzioni della funzione stessa.

void funfun(float (*)(int),double);

float funz (int);

float (*pfun)( );

pfun = funz; (non serve & ; analogo ai vettori)

la coppia di parentesi ( ) caretterizza il puntatore come puntante ad una funzione

ATT : int *pfun ( ); e’ il prototipo di una funzione pfun che ritorna un puntatore


Integrazione numerica

Se non esiste alcun metodo analitico per integrare la funzione f(x) o se la funzione e’ nota per punti metodo numerico di integrazione (approssimato).

Integrazione numerica: approssimazione, in “piccoli intervalli”, della funzione integranda mediante opportuni polinomi.

Detto pn(x) il polinomio di Lagrange di grado n interpolante f(x) tra i punti x0,x1,….xn (x0-xn :limiti di integrazione):

Formula del rettangolo


Formula del trapezio


Formula di Simpson

Integrazione numerica

0

100

200

300

400

500

600

2 2.1 2.2 2.3 2.4 2.5

x

exp(

x2)


1-Formula dei rettangoli

con xi = punto centrale di ogni intervallo

2

3

k

ABC

1

010 )()(......)()(

ki

iik

B

A

xfk

ABxfxf

k

ABdxxf

A B


2-Formula dei trapezi

2

3

2 k

ABC

1

1

)(2)()(2

)(ki

ii

B

A

afBfAfk

ABdxxf

A B


3-Formula di Simpson

con xi = punto centrale di ogni intervallo

4

5

3 k

ABC

1

1

1

0

)(4)(2)()(6

)(ki

i

ki

iii

B

A

xfafBfAfk

ABdxxf

A Bx0 Xk-1


4-Metodo di MonteCarlo

abxfbeafrauniformeonedistribuzilausasixfPer

xsN

dxxg

xf

xgxscalcolasixdivaloriNestraggonoSi

mediaxsEdistimaMiglior

dxxgdxxfxf

xgdxxfxsxsE

xf

xgxs

onedistribuzidifunzionedxxf

dxxg

N

ii

b

a

i

iii

b

a

b

a

b

a

b

a

b

a

1)()(

)(1

)(

)(

)()(

)]([

)()()(

)()()()]([

)(

)()(

1)(

)(

1

N

1


Esempio di integrazione MC multidimensionale: area di sovrapposizione fra cerchio e rettangolo

si generano coppie di numeri a caso in (A,B) e (C,D), cioe’ punti, con distrib. uniforme. Si conta il n di punti contenuti nella zona di sovrapposizione e, dalla densita’ di punti per unita’ di area generati si ottiene l’ area.

D

CBA

dydx


Strutture

In C si possono definire delle “strutture” ;

struttura = collezione di variabili elementari o di altre strutture definite precedentemente.

struct tipo_struttura {

tipo1 nome_elemento1;

tipo2 nome_elemento2;

………………………..;

};

Come si usa:

struct tipo_struttura nomeA,nomeB[n];

………………….

nomeA.nome_elemento1 = ……. (cioe’ si utilizza il “punto”per accedere ad un elemento della struttura)

Una struttura puo’ essere trasmessa ad una funzione.

Una struttura puo’ essere l’ argomento di ritorno di una funzione ed e’ possibile definire il puntatore ad una struttura.


Es.

-Nella grafica oggetto elementare e’ il punto caratterizzato da x,y e da un nome

struct point {

float x ;

float y ;

char s[20];

};

-Nella dichiarazione delle variabili:

struct point pt1, pt2,ptv[20];

pt1.x = 10.4;

pt2.y = 1.3;

ptv[2].x = 27. ;

-Le strutture possono essere nidificate:

struct rect {

struct point p1;

struct point p2;

};

struct rect rettangolo;

rettangolo.p1.x = 8.7 ; (coordinata x del primo punto della struttura rettangolo)


Es.

-Le strutture possono essere l’ argomento di ritorno di una funzione:

struct point makepoint(float x, float y) {

struct point punto;

punto.x = x ;

punto.y = y ;

return (punto);

}

-I puntatori alle strutture sono analoghi ai puntatori alle variabili ordinarie:

struct point *pp; (pp e’ il puntatore ad una struttura di tipo point)

-Se pp e’ un puntatore ad una struttura di tipo point, allora: ppx definisce il suo elemento x;

printf(“le coordinate sono: %f %f \n” , ppx , ppy );

Con il typdef e’ pssibile dare nome convenzionale a struttura (analogo al tipo per le variabili)

typedef struct volum{

float zmin;

float zmax;

float r;

int icolor;

} Vol;

Vol cilindro[4];


Algoritmo di ordinamento:

scorrere piu’ volte l’ array spostando verso la fine gli elementi piu’ “pesanti” e verso l’ inizio quelli piu’ “leggeri”

• flag = 1 ; k = n-1

• fino a che : flag = 1 e k > 0 ripeti:

• flag = 0

• per i = 0,…,k-1 ripeti:

• se a i > a i+1 scambia e poni flag = 1

• k = k - 1

SORT Bubble sort 8 7 9 3 1 4

7 8 8 9 3 9 1 9 4 9

7 8 3 1 4 9 7 8 3 8 1 8 4 8

7 3 1 4 8 9 3 7 1 7 4 7

3 1 4 7 8 9 1 3 3 4

1 3 4 7 8 9 1 3


Bubble_Sort(x,n)

return

si

no si

no

flag ==1 && k>0

flag=1k=n-1

0= i < k

x(i) > x(i+1)

scambia(x(i),x(i+1))

flag=1

flag=0

i++

si

no

sik--


SORT Insertion sort


• per i da 1 a n-1

• poni x = ai

• inserisci x nella posizione corretta nel sotto-array ordinato (a0,…,a i-1)

spostando in avanti gli elementi ak > x (0<= k < i)

Complessita’ dell’ algoritmo:

1 + 2 + ….+ (n-1) = n*(n-1)/2 ~ n2

0 1 2 3 4 5

i 18 19 14 11 15 12

1 18 19

2 14 18 19

3 11 14 18 19

4 11 14 15 18 19

5 11 12 14 15 18 19


Insert_Sort(x,n)

1 = i < n return

temp=x(i)i++

si

no

si

no

j = i-1

j >=0 && x(j)>temp

x( j+1)=x( j)

j--

x( j+1)=temp


SORT Quick sort


si sceglie un elemento p detto pivot e si mettono tutti gli elementi <= p in un sotto array e gli elementi > p in un secondo sotto array. Poi si ripete lo stesso algoritmo sui due sotto array fino ad ottenere n sotto array costituiti da un solo elemento. Riaggregando i sotto array si ottiene un array ordinato.

Complessita’ dell’ algoritmo (se l’ albero e’ bilanciato): n* log 2 n

4, 2, 6, 5, 7, 3, 1

6, 5, 7 2, 3, 1, 4

3, 41, 2 75, 6

41 32 65

Laboratorio di Calcolo1 AA 2006/2007Canale A Prof. G.Ciapetti Testi consigliati: Programmazione...

Documents

Transcript of Laboratorio di Calcolo1 AA 2006/2007Canale A Prof. G.Ciapetti Testi consigliati: Programmazione...