Ogni esercizio deve essere realizzato
come un programma a sé stante, ossia in un file separato, con un
proprio main. Si deve consegnare Esercizio 1,2,3 e 4.
Esercizio -1:
- Lanciare DevCPP usando il suo icone
che si trova sul DeskTop
- Aprire un nuovo file di sorgente (File-New-Source File)
- Copiare il codice del programma prova
nel DevCPP
- Salvare il file a qualche parte con nome prova.c
- Compilare il programma (Execute-Compile)
- Eseguire il programma (Execute-Run)
Esercizio
0:
Si definisca una funzione:
int maxintero()
che determina il massimo intero di una sequenza di interi inseriti da tastiera. L'utente inserisce il valore 0 per terminare la sequenza. Gli interi vengono letti mediante la funzione scanf.
Il programma contiene il main che richiama la funzione maxintero e ne stampa il risultato
mediante la printf.
Esercizio
1: Ordinamento basato su selezione
Ordinare un vettore di interi in modo non descrescente (non si esclude infatti che vi siano riptezioni).
ALGORITMO SELECTIONSORT:
Metodo: dato un vettore v[0..n-1] di interi per i=0..n-1, si cerca ripetutamente il minimo del sottovettore v[i..n-1] e lo si scambia con v[i] se diverso da v[i];
Realizzare le due funzioni:
int minimo(int a[], int
start, int limite)
determina l'indice del minimo elemento di tra le posizioni start e limite-1
void ordina(int a[], int
limite)
ordina a tra la positione 0 e la posizione limite-1
Il main del programma deve contenere lettura di un vettore di interi
dall'input, suo ordinamento e stampa del risultato.
Esercizio
2: ricerca binaria
Dato un vettore v[0..n-1] di interi ordinato in modo non decrescente, ed un intero m, stabilire se m occorre nel vettore in tempo O(log n). Si ritorni un indice i tale che v[i] = m se m è in v; -1 altrimenti.
ALGORITMO DI RICERCA BINARIA: per cercare m in v[i..j] sia k == (i + j)/2 il punto medio dell'intervallo i..j. Se i > j allora l'intervallo i..j è vuoto e si ritorna -1; altrimenti si distinguono tre casi:
v[k] == m: allora si ritorna k;
v[k] > m: allora si procede ricorsivamente su v[i..k-1];
v[k] < m: allora si procede ricorsivamente su v[k+1..j].
Il prototipo della funzione sarà:
int ricbin (int v[], int
i, int j, int m);
Il main del programma deve contenere lettura di un vettore di interi
dall'input, lettura del valore da cercare, stampa dell'esito della ricerca
Esercizio
3: sottostringhe
Una stringa s è sottostringa di una stringa t se esistono le stringhe s1 ed s2 (eventualmente vuote), tali che t = s1+s+s2 (dove + rappresenta la concatenazione).
Si realizzi una funzione sottostringa che verifica se una stringa pattern è sottostringa di una stringa testo.
Metodo: Diciamo che s è un prefisso di t se esiste una stringa s1 eventualmente vuota, tale che t=s+s1.
Per realizzare la funzione per ogni posizione i di t si controlla se s è un prefisso di t a partire dalla posizione i.
bool sottostringa (char
pattern[], char testo[]);
La funzione restituisce un valore booleano (TRUE o FALSE) a seconda
che che pattern sia una sottostringa di testo oppure no. Il main del programma
chiede di inserire due stringhe e stampa il risultato di sottostringa.
Definire opportunamente le costanti TRUE e FALSE.
Esercizio 4:
operazioni su insiemi
Si realizzino le seguenti funzioni dati due vettori di interi che
rappresentano due insiemi
(gli elementi non sono ordinati e non compaiono nel vettore più
di una volta):
int unione(int insieme1[],
int insieme2[], int risultato[]);
La funzione costruisce l'unione insiemistica di insieme1 e insieme2 (mette gli
elementi comuni una volta sola) in risultato e restituisce il numero
di elementi contenuti in risultato.
int intersezione(int
insieme1[], int insieme2[], int risultato[]);
La funzione costruisce l'intersezione insiemistica di insieme1 e insieme2 in risultato
e restituisce il numero di elementi contenuti in risultato.
int differenza (int insieme1[], int insieme2[], int risultato[]);
La funzione costruisce la differenza insiemistica di insieme1 e insieme2 in risultato
e restituisce il numero di elementi contenuti in
risultato.