darkmax
13-05-2005, 11:20
2. Selection sort
Scrivere un programma che legge un vettore x[] di al piu` MAXDIM=100 numeri interi da tastiera e lo ordina.
L'algoritmo di ordinamento da implementare e` il Selection Sort; questo algoritmo cerca iterativamente il minimo elemento nella parte non ordinata del vettore e lo scambia con l'elemento in prima posizione della stessa parte.
Esempio. Sia dato il vettore x[]={5,3,4,9,2}. L'algoritmo lo ordina come segue.
Iter. 1 5 3 9 4 2 => 2 3 9 4 5
Iter. 2 2 3 9 4 5 => 2 3 9 4 5
Iter. 3 2 3 9 4 5 => 2 3 4 9 5
Iter. 4 2 3 4 9 5 => 2 3 4 5 9
(l'iterazione 5 e` superflua)
Definire le funzioni
void ordina(int a[], int limite): ordina le prime limite posizioni (da 0 a limite-1) del vettore a[].
int minimo(int a[], int start, int end): cerca il minimo elemento di a[] tra quelli nelle posizioni da start a end-1 e ritorna la posizione di questo elemento.
void scambia(int a[], int i, int j): scambia gli elementi in posizione i e j nel vettore a[].
La funzione ordina() richiama correttamente e iterativamente la minimo() e la scambia().
Il programma deve presentare un menu con tre opzioni:
Lettura del vettore (dimensione e elementi).
Ordinamento.
Uscita.
L'opzione 2 causa, in sequenza, la stampa del vettore non ordinato, il suo ordinamento e la stampa del vettore ordinato.
3. Cerca e cancella
Scrivere un programma che permette di cercare la prima occorrenza di una sottostringa p[] all'interno di un'altra stringa q[], e creare una nuova stringa s[] corrispondente a una copia di q[] dalla quale sia stata cancellata p[]. Il programma deve chiedere in sequenza q e p. Se p non e` una sottostringa di q il programma lo segnala, altrimenti crea s come richiesto e la stampa.
Si assuma che tutte le stringhe abbiano dimensione massima MAXSTR=128.
Esempio di elaborazione.
Introduci la stringa: topolino
Introduci la sottostringa da cancellare: lin
Cancellando lin da topolino si ottiene topoo
oppure
Introduci la stringa: topolino
Introduci la sottostringa: pippo
Errore: pippo non e` sottostringa di topolino.
Definire il tipo Bool e le costanti TRUE e FALSE come visto a lezione.
Definire le seguenti funzioni.
Bool cerca_e_cancella(char p[], char q[], char s[]): cerca q[] in p[]; se la trova genera s[] come da specifiche, e ritorna TRUE; se p[] non e` sottostringa di q[] ritorna FALSE.
void copia(char s[], char t[], int k, int n): copia s[] in t[], saltando i caratteri di s[] nelle posizioni da k a n (incluse). La funzione deve essere "autonoma", cioe` controllare la coerenza di k e n, e non modificare t se gli estremi specificati non sono validi (es: k<n, oppure n corrisponde ad una posizione non appartenente a s,...).
Scrivere un programma che legge un vettore x[] di al piu` MAXDIM=100 numeri interi da tastiera e lo ordina.
L'algoritmo di ordinamento da implementare e` il Selection Sort; questo algoritmo cerca iterativamente il minimo elemento nella parte non ordinata del vettore e lo scambia con l'elemento in prima posizione della stessa parte.
Esempio. Sia dato il vettore x[]={5,3,4,9,2}. L'algoritmo lo ordina come segue.
Iter. 1 5 3 9 4 2 => 2 3 9 4 5
Iter. 2 2 3 9 4 5 => 2 3 9 4 5
Iter. 3 2 3 9 4 5 => 2 3 4 9 5
Iter. 4 2 3 4 9 5 => 2 3 4 5 9
(l'iterazione 5 e` superflua)
Definire le funzioni
void ordina(int a[], int limite): ordina le prime limite posizioni (da 0 a limite-1) del vettore a[].
int minimo(int a[], int start, int end): cerca il minimo elemento di a[] tra quelli nelle posizioni da start a end-1 e ritorna la posizione di questo elemento.
void scambia(int a[], int i, int j): scambia gli elementi in posizione i e j nel vettore a[].
La funzione ordina() richiama correttamente e iterativamente la minimo() e la scambia().
Il programma deve presentare un menu con tre opzioni:
Lettura del vettore (dimensione e elementi).
Ordinamento.
Uscita.
L'opzione 2 causa, in sequenza, la stampa del vettore non ordinato, il suo ordinamento e la stampa del vettore ordinato.
3. Cerca e cancella
Scrivere un programma che permette di cercare la prima occorrenza di una sottostringa p[] all'interno di un'altra stringa q[], e creare una nuova stringa s[] corrispondente a una copia di q[] dalla quale sia stata cancellata p[]. Il programma deve chiedere in sequenza q e p. Se p non e` una sottostringa di q il programma lo segnala, altrimenti crea s come richiesto e la stampa.
Si assuma che tutte le stringhe abbiano dimensione massima MAXSTR=128.
Esempio di elaborazione.
Introduci la stringa: topolino
Introduci la sottostringa da cancellare: lin
Cancellando lin da topolino si ottiene topoo
oppure
Introduci la stringa: topolino
Introduci la sottostringa: pippo
Errore: pippo non e` sottostringa di topolino.
Definire il tipo Bool e le costanti TRUE e FALSE come visto a lezione.
Definire le seguenti funzioni.
Bool cerca_e_cancella(char p[], char q[], char s[]): cerca q[] in p[]; se la trova genera s[] come da specifiche, e ritorna TRUE; se p[] non e` sottostringa di q[] ritorna FALSE.
void copia(char s[], char t[], int k, int n): copia s[] in t[], saltando i caratteri di s[] nelle posizioni da k a n (incluse). La funzione deve essere "autonoma", cioe` controllare la coerenza di k e n, e non modificare t se gli estremi specificati non sono validi (es: k<n, oppure n corrisponde ad una posizione non appartenente a s,...).