Programmazione 1 - Esercitazione

Università di Napoli Federico II – Facoltà di ingegneria

Corso di laurea in Ingegneria informatica

Corso di Programmazione I

Tutorato

Allievi CAQ-E e F-O

Tutori: Ing. C. di Flora, Ing. A. Fasolino

Esercitazione n. 1 - Algoritmi di ricerca e ordinamento

Testo del problema (OrdRic)

Lo studente progetti e implementi un programma che:

• Costruisca una sequenza di elementi di tipo T (interi, caratteri, reali...) attraverso l'input da tastiera;
• Ordini tale sequenza utilizzando l'algoritmo "selection sort" (versione ricorsiva);
• Richieda in input da tastiera un ulteriore elemento (x) dello stesso tipo T della sequenza, e ricerchi l'elemento (x) nel lista ordinata utilizzando l'algoritmo di ricerca binaria (versione ricorsiva), visualizzando infine un messaggio che riporti il risultato della ricerca.

Indicazioni operative

1. Lo studente costruisca un progetto composto dai seguenti files:

• OrdRic.h header file
• Utente.cpp contenente il main
• Funzioni.cpp contenente tutte le funzioni necessarie alla risoluzione del problema

2. Lo studente esamini il codice seguente (compreso i commenti).

Esso deve essere utilizzato come guida per il completamento della soluzione.

#include <iostream.h>

#include <stdlib.h>

// ricerca binaria versione ricorsiva

// la sequenza di elementi deve essere ordinata in senso crescente

// l'array di elementi e' allocato dinamicamente

/* Definizioni di Tipo e prototipi di Funzione */

typedef int T;

int BinSearch(const T *, const int, const int, const T, int &);

void Ordina(T* , const int, const int);

void MinimoSottoelenco(const T*, const int, const int, T &, int &);

void ordina(const T *, const int);

void leggivet(T*, const int);

int main() {

int n, pos=-1;

T x;

// ....inserire qui la dichiarazione di A (vedi sotto)

cout << "\n inserisci la dimensione del vettore: ";

cin >> n;

// allocazione dinamica del vettore

// i cui elementi sono di tipo T

// la cardinalità è n

//..........posto per la allocazione dinamica ....................