Informatica per la I Facoltà

Informatica
per la I Facoltà
Esercitazione in Aula
14-15/04/2010
[email protected]
http://www.cad.polito.it/staff/grosso/Informatica
Esercizio 1
Data la seguente serie matematica detta serie
geometrica, convergente per |x| < 1 al valore
riportato,
scrivere un programma in linguaggio C che
acquisisca da tastiera il valore x ed un valore di
N, dove la sommatoria deve essere troncata, e
calcoli la distanza della sommatoria calcolata dal
risultato esatto della serie.
1
Esercizio 1: soluzione
r = 1/(1-x)
Start
Leggi N
Leggi x
|x| < 1
V
k = 1, z = 1, y = 1
F
Non conv!
k <= N
F
d = |r - z|
V
y=y*x
Stampa N
z=z+y
Stampa d
k ++
Stop
Esercizio 2
Scrivere un programma in linguaggio C che,
acquisito da tastiera un vettore di 10 numeri, ne
ruoti circolarmente il contenuto (verso destra o
verso sinistra) di num posizioni e visualizzi la
configurazione finale. Il verso della rotazione ed il
valore di num sono richiesti come input.
Esempio:
Vettore iniziale: 1 2 3 4 5 6 7 8 9 10
Verso di rotazione? (1 = sinistra, 2 = destra): 1
Numero di shift => 2
Vettore finale (ruotato a sinistra di 2
posizioni):
3 4 5 6 7 8 9 10 1 2
2
Esercizio 2: soluzione
Start
Leggi vet
i=0
Leggi verso
i < num
V
Leggi num
verso == 1
V
F
[…]
F
rotaz a sx di 1
i ++
Stampa vet
Stop
Esercizio 2: soluzione
Start
temp
vet[0]
Leggi=vet
=0
Leggijverso
Leggi num
j<9 VF
verso
V == 1
vet[j] =Fvet[j+1]
[…]
j ++
vet[j] = temp
i=0
i < num
V
F
rotaz a sx di 1
i ++
Stampa vet
Stop
3
Esercizio 3
Si scriva un programma in linguaggio C in grado
di acquisire un vettore di N interi e stamparli in
ordine crescente.
Esercizio 3: traccia
Bubble Sort:
(ordinamento di vettore di N elementi)
scambio = 1;
while (scambio == 1)
{
scambio = 0; /* ipotesi: vettore già ordinato */
for (i = 0; i < N – 1 ; i++)
if (vettore[i] > vettore[i+1])
{
temp = vettore[i];
vettore[i] = vettore[i+1];
vettore[i+1] = temp;
scambio = 1; /* cambio ipotesi */
}
23, 8, 42, 16, 15, 4
8, 23, 42, 16, 15, 4
8, 23, 16, 42, 15, 4
8, 23, 16, 15, 42, 4
8, 23, 16, 15, 4, 42
8, 16, 23, 15, 4, 42
8, 16, 15, 23, 4, 42
8, 16, 15, 4, 23, 42
8, 15, 16, 4, 23, 42
8, 15, 4, 16, 23, 42
8, 4, 15, 16, 23, 42
4, 8, 15, 16, 23, 42
}
4
Esercizio 4
Scrivere un programma in linguaggio C che,
acquisita da tastiera una tabella (dimensione 3 x
3) di interi, ne metta in ordine crescente i valori
contenuti (a partire dall’elemento in alto a
sinistra) utilizzando l’algoritmo bubble sort.
Esempio:
15
37
8
9
42
9
18
1
12
1
9
18
8
12
37
9
15
42
Esercizio 5
Si consideri il seguente problema di matematica
ricreativa, dovuto al matematico russo Boris
Kordemsky:
Il gatto Purrer ha deciso di schiacciare un
pisolino, e subito sogna di essere circondanto da
13 topolini, 12 grigi e uno bianco; nel sogno il
padrone gli dice: “Purrer, devi mangiare ogni
tredicesimo topo, contando circolarmente
sempre nella stessa direzione; l'ultimo topo
mangiato deve essere quello bianco”. Da quale
topo deve cominciare Purrer?
5
Esercizio 5
[cont.]
Realizzare un programma in C che, fornito in
ingresso la posizione del topo bianco come
intero compreso tra 0 e 12, fornisca la sequenza
dei topi mangiati in modo che l'ultimo sia quello
bianco. Per sequenza dei topi s'intende quella
delle loro posizioni iniziali.
Esempio:
bianco = 10
Soluzione:
2, 3, 5, 8, 12, 7, 4,
6, 11, 0, 1, 9, 10
Esercizio 5: soluzione
#include <stdio.h>
#include <stdlib.h>
#define NUMTOPI 13
#define GIRO 13
#define TRUE 1
#define FALSE 0
int main(void)
{
int
int
int
int
int
int
int
mangiato[NUMTOPI]; /* vettore di stato dei topi */
seq[NUMTOPI];
/* sequenza risolutiva */
bianco;
/* indice del topo bianco */
iniz;
/* ipotesi su pos. di partenza */
pos_corrente;
mangiati = 0;
/* numero topi mangiati */
i;
printf("Qual e' la posizione iniziale del topo bianco? ");
scanf("%d", &bianco);
6
Esercizio 5: soluzione
[cont.]
for (iniz = 0; mangiati != NUMTOPI; iniz ++)
{
/* Inizializzazione per nuovo tentativo */
for (i=0; i<NUMTOPI; i++)
mangiato[i] = FALSE;
mangiati = 0;
pos_corrente = iniz;
while (mangiati != NUMTOPI && !mangiato[bianco])
{
/* conta 13 posizioni => da espandere
occorre incrementare pos_corrente
considerando i topi già mangiati */
mangiato[pos_corrente] = TRUE;
seq[mangiati] = pos_corrente;
mangiati ++;
} /* end while (mangiati != NUMTOPI ... */
} /* end for (iniz = 0... */
Esercizio 5: soluzione
[cont.]
for (iniz = 0; mangiati != NUMTOPI; iniz ++)
{
for (i=0; i<NUMTOPI; i++) mangiato[i] = FALSE;
mangiati = 0;
pos_corrente = iniz;
while (mangiati != NUMTOPI && !mangiato[bianco])
{
for (i = 0; i < GIRO; i++)
{
do
{
pos_corrente++;
if (pos_corrente == NUMTOPI) pos_corrente = 0;
}
while (mangiato[pos_corrente] == TRUE)
} /* end for (i = 0; ... */
mangiato[pos_corrente] = TRUE;
seq[mangiati] = pos_corrente;
mangiati ++;
} /* end while (mangiati != NUMTOPI ... */
} /* end for (iniz = 0... */
7
Esercizio 5: soluzione
[cont.]
/* stampa risultati */
printf("Sequenza: ");
for (i=0; i<NUMTOPI; i++)
printf("%d ", seq[i]);
printf("\n");
system("PAUSE");
return 0;
}
8