Esercizi in Laboratorio:
Dato un vettore di interi letti dall’input, costruire una sua permutazione casuale:
[cpp]
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#define N 10
int main(void)
{
int v[N] = { 0 };
printf("Inserisci %d interi: ",N);
for (int i=0; i<N; i++)
scanf("%d",&v[i]);
// stampiamo i numeri letti
for (int i=0; i<N; i++)
printf("%d,",v[i]);
printf("\n");
// ok permutiamo:
for (int i=0; i<=N-2; i++) {
int k = rand() % (N-1-i) +(i+1);
// scanbio v[i] con v[k]
int t = v[i];
v[i] = v[k];
v[k] = t;
}
// stampiamo il vettore permutato
for (int i=0; i<N; i++)
printf("%d,",v[i]);
printf("\n");
return 0;
}
[/cpp]
Crivello di Eratostene:
[cpp]
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#define N 1000
static inline int i2v(int n) { return 2*n+3; }
static inline int v2i(int n) { return (n-3)/2; }
int main(void)
{
// Ci serve un vettore di booleani
// v[i] == true -> i2v(i) e’ primo
// attenzione, a lezione abbiamo scritto bool v[N] = { 1 }
// pensando che tutti gli elementi vengano inizializzati ad 1.
// sbagliato! in quel modo si ha v[0]==1 e v[i]==0 per i restanti.
bool v[N];
for (int i=0; i<N; i++) v[i] = true; // inizializziamo v esplicitamente
// ci fermiamo alla radice di N.
// notare l’uso delle funzioni i2v e v2i per la trasformazione
// degli indici in valori e viceversa
int top = v2i(sqrt(i2v(N)));
// ok, si parte. ciclo esterno:
// invariante: v[i] == true e i2v(i) primo
// compito loop: cancello i multipli di tutti i primi
int i = 0;
do {
int k = i2v(i);
// ok, k fissato, devo cancellare tutti i suoi multipli
// cancelliamo i multipli dispari di k, 3k,5k,7k…
int l = 3;
int j = v2i(l * k);
while (j < N) {
v[j] = false;
l += 2; // +2 perche i pari sono già eliminati.
j = v2i(l * k);
}
// adesso il prossimo i, deve soddisfare l’invariante:
// ci spostiamo sul prossimo valore del vettore
// con v[i] == true;
do { i++; } while (v[i] == false);
} while (i<top);
// Fine: stampiamo i numeri primi.
for (int c=1,i=0; i<N; i++)
if (v[i]) {
printf("%4d ",i2v(i));
if (c++ % 11 == 0) printf("\n");
}
printf("\n");
return 0;
}
[/cpp]