Algoritmi e Programmazione Avanzata - Esercizi propedeutici

arrayInsert.c

/*

Algoritmi e Programmazione Avanzata

Tutore: Sergio Porcu

Argomento: inserimento di un elemento in un vett ore

Si implementi in C la seguente funzione:

int insert (int vet[VET_SIZE], int *elemN, int k ey);

che inserisce un elemento intero key in un vetto re vet

ordinato in ordine crescente. Si noti che il vet tore

deve essere mantenuto ordinato e che *elemN indi ca il

numero di elementi effettivamente presenti (e si gnificativi)

nel vettore e va opportunamente aggiornato. In c aso di

vettore pieno l'elemento di valore maggiore può essere

eliminato dal vettore e venire perduto. La funzi one

restituisce 1 se l'inserimento non causa la perd ita di dati

e 0 in caso contrario.

Esempio.

Vettore prima dell'inserzione (VET_SIZE = 5): 1 2 3 4 5

Vettore dopo l'inserzione di key = 4: 1 2 3 4 4

*/

#include <stdio.h>

#include <stdlib.h>

#define VET_SIZE 6

#define SUCCESS 1

#define FAILURE 0

int insert (int vet [VET_SIZE], int *elemN, int key );

int

main (

void

)

{

int key , i , elemN;

int vet [VET_SIZE];

elemN = 0;

do {

fprintf (stdout , "Elemento da inserire (<0 per terminare): " );

scanf ("%d" , &key );

if (key >=0) {

insert (vet , &elemN, key );

fprintf (stdout , "Vettore risultante:\n" );

for (i =0; i <elemN; i ++) {

fprintf (stdout , "%d " , vet [i ]);

}

fprintf (stdout , "\n" );

}

} while (key >=0);

-1-

arrayInsert.c

return (SUCCESS);

}

/*

* Per gestire in maniera univoca il caso di vetto re pieno

* memorizzo un elemento effettivo in meno ... per do un elemento

* del vettore

*/

int

insert (

int vet [VET_SIZE],

int *elemN,

int key

)

{

int i , retValue ;

i =*elemN;

while (i >0 && vet [i -1]>key ) {

vet [i ] = vet [i -1];

i --;

}

vet [i ] = key ;

if ((*elemN) < VET_SIZE-1) {

retValue = SUCCESS;

*elemN = *elemN + 1;

} else {

retValue = FAILURE;

}

return (retValue );

}

-2-

binaryNumber.c

/*



Argomento: visualizzazione di un numero binario di n bit

Si scriva una funzione ricorsiva che riceva come parametro

un numero intero n e generi e visualizzi su video tutti i

numeri binari di n bit.

*/

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

void binaryNumberIte (int n);

void binaryNumberRic (int i, int *vet, int n);

int

main (

void

)

{

int n, *vet;

fprintf (stdout, "Numero di bit: ");

scanf ("%d", &n);

vet = (int *) malloc (n * sizeof (int));

if (vet==NULL) {

fprintf (stderr, "Errore di allocazione.\n");

exit (1);

}

fprintf (stdout, "Numeri Iterativo:\n");

binaryNumberIte (n);

fprintf (stdout, "Numeri Ricorsivo:\n");

binaryNumberRic (0, vet, n);

return (1);

}

void

binaryNumberIte (

int n

)

{

int i, j, k, nDec, bit;

nDec = pow (2, n);

for (i=0; i<nDec; i++) {

k = i;

for (j=0; j<n; j++) {

bit = k%2;

/*k = k/2;*/

k = k >> 1;

fprintf (stdout, "%d", bit);

}

-1-

binaryNumber.c

fprintf (stdout, "\n");

}

return;

}

void

binaryNumberRic (

int i,

int *vet,

int n

)

{

int j;

if (i>=n) {

for (j=0; j<n; j++) {

fprintf (stdout, "%d", vet[j]);

}


return;

}

vet[i] = 0;

binaryNumberRic (i+1, vet, n);

vet[i] = 1;

binaryNumberRic (i+1, vet, n);

return;

}

-2-

listInsert.c

/*



Argomento: inserzione in lista ordinata

Sia data la seguente struttura:

- key (numero intero)

- nome (stringa di massimo 30 caratteri)

- puntatore auto-referenziante

Si:

a. definisca tale struttura in linguaggio C

b. implementi in C la funzione che, ricevendo qu ali parametri

key, nome e il puntatore pHead a una lista su pposta ordinata

secondo il campo key, inserisce un elemento d i tale tipo

nella lista contenente i parametri indicati.

*/

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <ctype.h>

#define MAXC 30

#define SUCCESS 1

#define FAILURE 0

typedef struct nodo {

int key ;

char nome[MAXC];

struct nodo *next ;

} nodo_t ;

nodo_t *inserisci (nodo_t *headP, int key , char *nome);

void stampaLista (nodo_t *headP);

void

stampaLista (

nodo_t *headP

)

{

fprintf (stdout , "Lista:\n" );

while (headP != NULL) {

fprintf (stdout , "%d %s\n" , headP->key , headP->nome);

headP = headP->next ;

}

return;

}

nodo_t

*inserisci (

nodo_t *headP,

int key ,

char *nome

)

-1-

listInsert.c

{

nodo_t *p, *p0, *p1;

p = (nodo_t *) malloc (sizeof (nodo_t ));

if (p==NULL) {

fprintf (stderr , "Errore di allocazione.\n" );

exit (1);

}

p->key = key ;

strcpy (p->nome, nome);

/* Lista vuota */

if (headP == NULL) {

p->next = NULL;

return (p);

}

/* Inserimento in testa */

if (key < headP->key ) {

p->next = headP;

return (p);

}

/* Inserimento in mezzo o in coda. Percorrimento co n doppio puntatore:

p0 e p1 puntano a due nodi consecutivi, al mom ento dell'inserimento

p0 punta al nodo precedente, p1 al successivo

*/

p0 = headP; p1 = headP->next ;

/* cerca posizione - eventualmente fine lista (p1 = = NULL) */

while ((p1 != NULL)&&(p1->key <key )) {

p0 = p1;

p1 = p1->next ;

}

/* inserisce */

p0->next = p;

p->next = p1;

/* headP non viene modificato */

return (headP);

}

int

main (

void

)

{

nodo_t *headP;

int key ;

char riga [MAXC], nome[MAXC];

headP = NULL;

do {

fprintf (stdout , "(f)ine: " );

scanf ("%s" , riga );

if (riga [0] != 'f' ) {

fprintf (stdout , "Key: " );

-2-

listInsert.c

scanf ("%d" , &key );

fprintf (stdout , "Nome: " );

scanf ("%s" , nome);

headP = inserisci (headP, key , nome);

stampaLista (headP);

}

} while (riga [0] != 'f' );

return (SUCCESS);

}

-3-

multiFusione.c

/*



Argomento: fusione di array

Fusione di N_VET vettori ordinati di dimensione N_EL

*/

#include <stdio.h>

#define N_VET 5

#define N_EL 3

#define N N_VET*N_EL

void minimo (int mat[N_VET][N_EL], int vet_i[N_VET], int vet[N_VET*N_EL],

int *k);

char fine (int vet_i[N_VET]);

main ()

{

char flag;

int i, j, k, l, mat[N_VET][N_EL], vet_i[N_VET], vet[N];

/* ciclo di lettura dei vettori */

for (i=0; i<N_VET; i++) {

fprintf (stdout, "INTRODUCI IL VETTORE %d (ordinato):\n", i);

for (j=0; j<N_EL; j++) {

fprintf (stdout, "vet%1d[%d] = ", i, j);

scanf ("%d", &mat[i][j]);

if (j>0) {

if (mat[i][j]<mat[i][j-1]) {

fprintf (stderr, "!!! VETTORE NON ORDINATO !!!");

exit(1);

}

}

}


}


for (l=0; l<N; l++) {

fprintf (stdout, "[%2d]", l);

}



vet_i[i] = 0;

}

k = 0;

flag = 0;

while (!flag) {

minimo (mat, vet_i, vet, &k);

flag = fine (vet_i);

-1-

multiFusione.c

for (l=0; l<k; l++) {

fprintf (stdout, " %2d ",vet[l]);

}


}

flag = 0;

for (i=0; (i<N_VET)&&(!flag); i++) {

if ( vet_i[i]<(N_EL-1) ) {

while ( vet_i[i]<N_EL ) {

vet[k] = mat[i][vet_i[i]];

k++; vet_i[i]++;

}

flag = 1;

}

}

/* stampa vettore */

fprintf (stdout, "\nRISULTATO :\n");

for (l=0; l<N; l++) {

fprintf (stdout, " %2d ",vet[l]);

}


return;

}

/* Determina se tutti i vettori, tranne uno, sono terminati */

char

fine (

int vet_i[N_EL]

)

{

char flag;

int i;

flag = 0;


if ( vet_i[i]<N_EL ) {

flag++;

}

}

if (flag==1) {

return (1);

} else {

return (0);

}

}

/* Determina il nuovo minimo, lo assegna e ripristina

i contatori */

void minimo (

int mat[N_VET][N_EL],

int vet_i[N_VET],

-2-

multiFusione.c

int vet[N],

int *k

)

{

char flag;

int i, j, min;

flag = 0;


if ( vet_i[i]<N_EL ) {

if (flag) {

if ( mat[i][vet_i[i]]<min ) {

j = i;

min = mat[i][vet_i[i]];

}

} else {

j = i;

min = mat[i][vet_i[i]];

flag = 1;

}

}

}

vet[*k] = min;

(*k)++;

vet_i[j]++;

return;

}

-3-

giocoVita.c

/*



Argomento: simulazione del gioco della vita

La configurazione inziale si introduce specifica ndo

indice di riga e di colonna di ciascun elemento.

Indice di riga e/o colonna negativi interrompono

la fase di input. L'evoluzione avviene sino a

interrompere il programma.

*/

#include <stdio.h>

#define DIM1 5 /* Righe Mat */

#define DIM2 5 /* Colonne Mat */

char mat[2][DIM1][DIM2];

/* vettori per il calcolo delle coordinate dei vici ni */

int a[8] = { 0, 1, 1, 1, 0, -1, -1, -1},

b[8] = { 1, 1, 0, -1, -1, -1, 0, 1};

/* prototipi */

void update (char flag );

void reset (char flag );

int alive (int x, int y, char flag );

int neighbour (int x, int y, char flag );

void display (char flag );

main ()

{

char c, flag =0;

int x, y;

printf ("Formato di Input:\n" );

printf (" IndiceRiga<spazio>IndiceColonna<return>\n" );

printf (" IndiceRiga = 0..%d\n" , DIM1);

printf (" IndiceColonna = 0..%d\n" , DIM2);

/* acquisizione della configurazione iniziale */

do {

printf ("IndiceRiga<spazio>IndiceColonna<return> : " );

scanf ("%d %d" , &x, &y);

if ((x>=0) && (y>=0)) {

mat[flag ][x][y] = 1;

}

} while ( (x>=0) && (y>=0) );

display (0);

/* ciclo infinito (di evoluzione) */

while (1) {

update (flag );

display (!flag );

printf ("\nBatti RETURN per continuare \n" );

-1-

giocoVita.c

c = getchar ();

flag = !flag ;

}

return;

}

/*

calcola di una nuova generazione

*/

void

update (

char flag

)

{

int i , j , n;

for (i =0; i <DIM1; i ++) {

for (j =0; j <DIM2; j ++) {

n = neighbour ( i , j , flag );

if ( alive (i , j , flag ) ) {

if ( (n == 2) || (n == 3) )

mat[!flag ][i ][j ] = 1;

} else {

if ( (n == 3) )

mat[!flag ][i ][j ] = 1;

}

}

}

reset (flag );

return;

}

/*

azzera la matrice relativa alla generazione futura

preparandola a contenere nuovi dati

*/

void

reset (

char flag

)

{

int i , j ;

for (i =0; i <DIM1; i ++)

for (j =0; j <DIM2; j ++)

mat[flag ][i ][j ] = 0;

return;

}

/*

determina se una casella e' viva

*/

-2-

giocoVita.c

int

alive (

int x,

int y,

char flag

)

{

if ( mat[flag ][x][y] )

return (1);

else

return (0);

}

/*

calcola il numero di vicini vivi all'elemento x, y

*/

int

neighbour (

int x,

int y,

char flag

)

{

int i , xx , yy , count =0;

for (i =0; i <8; i ++) {

xx = x + a[i ];

yy = y + b[i ];

if ( xx >= 0 && xx < DIM1 && yy >= 0 && yy < DIM2 )

if ( alive ( xx , yy , flag ) )

count ++;

}

return (count );

}

/*

visualizza una generazione

*/

void

display (

char flag

)

{

int i , j ;

printf ("\n" );

for (i =0; i <DIM1+2; i ++)

printf ("#" );

printf ("\n#" );

for (i =0; i <DIM1; i ++) {

for (j =0; j <DIM2; j ++)

if ( mat[flag ][i ][j ])

printf ("*" );

else

printf (" " );

-3-

giocoVita.c

printf ("#\n#" );

}

for (i =0; i <DIM1+1; i ++)

printf ("#" );

return;

}

-4-

Algoritmi e Programmazione Avanzata - Esercizi propedeutici

Education

Transcript of Algoritmi e Programmazione Avanzata - Esercizi propedeutici