Lezione 6:Crivello Di Eratostene

Report
Crivello Di Eratostene
(fonte http://it.wikipedia.org/wiki/Crivello_di_Eratostene#Algoritmo)
Si scrivono tutti i naturali a partire da 2 fino n in un elenco detto setaccio
(in un array). Poi si cancellano (setacciano) tutti i multipli del primo
numero del setaccio (escluso lui stesso). Si prosegue così fino ad
arrivare in fondo. I numeri che restano sono i numeri primi minori od
uguali a n.
È come se si utilizzassero dei setacci a maglie via via più larghe: il primo
lascia passare solo i numeri non multipli di 2, il secondo solo i non
multipli di 3, e così via.
Nel caso n = 50, ad esempio, il procedimento di setacciatura si conclude
con il numero 7 perché 7 è il massimo primo il cui quadrato non supera
50 e si può provare che il procedimento di setacciatura per ricercare i
primi fino ad un certo numero n cessa sempre quando si supera la radice
quadrata di n.
Esempio
#include <stdio.h>
#include <math.h>
/*Libreria necessaria per poter usare la funzione sqrt()*/
#define DIM 1000
int main (void)
{
printf ("Crivello di Eratostene\n\n");
int v[DIM+1];
int p[DIM+1];
int i, j, k = 0;
for (i = 2; i <= DIM; i++)
{
v[i] = i; /* Inizializzo il vettore v con i valori del
suo indice; quindi contiene in modo sequenziale valori da 2
a 1000 */
}
for (i = 2; i <= sqrt(DIM); i++) /*la funzione sqrt(DIM) da
come valore la radice quadrata di DIM*/
{
for (j = i + 1; j <= DIM; j++)
{
if (v[j] % i == 0)
{
/*Verifico se il valore i-esimo del vettore
v possiede dei multipli, scorrendo tutti i suoi i-esimi valori
successivi */
v[j] = 0;
/*Se è vero allora "cancello" i
suoi multipli inserendo uno 0 */
}
}
}
/*Ora il vettore contiene tutti i numeri primi più gli
zeri, quindi occorre "compattare" il vettore eliminando gli
zeri */
for (i = 2; i <= DIM; i++)
{
if (v[i] != 0)
{ //Se l'elemento i-esimo del vettore v non è uno 0
p[k] = v[i];
/*Inserisco il valore nel vettore p
che conterrà solo i numeri (primi) senza gli 0 */
k++; /*Incremento la variabile k che servirà per
determinare la dimensione del vettore p di primi */
}
}
//Stampo a video
for (i = 0; i < k; i++)
{
printf ("%d\t", p[i]);
}
return 0;
}
Scrivere un programma che inizializza un vettore monodimensionale di interi e poi copia il
vettore in un altro vettore della stessa dimensione.
#include <stdio.h>
main()
{
int i;
int a[10]={1,2,3,4,5,6,7,8,9,10}; /* inizializzazione in fase di definizione */
int b[10];
/* stampa a[] */
printf("a[]= ");
for(i=0;i<10;i++) {
printf(" %d", a[i]); }
/* copio a[] in b[] */
printf("\ncopio a[] in b[]\n");
for(i=0;i<10;i++) b[i]=a[i];
/* stampa b[] */
printf("b[]= ");
for(i=0;i<10;i++) { printf(" %d,", b[i]); }
}
In una gara il punteggio di ciascun atleta è dato dal pubblico. I voti possono andare da 0 a 4.
Scrivere un programma che per ogni atleta rilevi il numero di occorrenze dei vari voti.
a. con switch…case; b. con i vettori
#include<stdio.h>
main()
{
int voto0 = 0, voto1=0, voto2=0, voto3=0, voto4=0;
int voto=0;
/* printf("Inserisci un voto (da 0 a 4, -1 per terminare"); scanf(); ..*/
while(voto!=-1) {
printf("Inserisci un voto (da 0 a 4)"); scanf("%d",&voto);
switch(voto) {
case 0: voto0++; break;
case 1: voto1++; break;
case 2: voto2++; break;
case 3: voto3++; break;
case 4: voto4++; break;
default: printf("Inserimento errato!!!!"); break; }
}
printf("%d %d %d %d %d", voto0, voto1,voto2, voto3, voto4);
return 0;
}
int voto[5]={0}, i=0,j=0;
for(j=0;j<=4;j++)
{
printf("Inserisci un voto per la mensa (tra 0 e 4):");
scanf("%d",&i);
voto[i]++;
}
Leggere, ed inserire in un array, una stringa di caratteri
formata solo da lettere minuscole e dallo
spazio e terminata da '$'. Quindi:
1- Per ogni carattere della stringa, mettere il carattere
alfabeticamente successivo;
2-Il carattere successivo della 'z' sarà la 'a';
3- il carattere successivo dello spazio, sarà '_'.
Per esempio, 'a' -> 'b' , 'g' -> 'h', 'z' -> 'a', ' ' -> '_'.
4- Stampare la stringa così codificata.
NOTA: assumiamo che l’utente inserisca tutti i caratteri in una
volta sola e quindi prema ENTER.
Usiamo il contatore per trovare la fine della stringa.
[azzera contatore i]
[leggi carattere]
while ([il carattere letto non è ‘$’]) {
[inserisci carattere nella posizione i-esima dell’array; incrementa i]
[leggi carattere] }
[azzera contatore i]
for ([per ogni cella dell’array, fino alla (i-1)-esima]) {
if ([il carattere è lo spazio]) {
[inserisci ‘_’ nell’array che conterrà il risultato] }
else if ([il carattere è minore di ‘z’]) {
[inserisci il carattere alfabeticamente successivo nell’array risultato] }
else {
[inserisci ‘a’ nell’array del risultato]
}
}
for ([per ogni cella dell’array, fino alla (i-1)-esima])
{ [scrivi carattere] }
#include <stdio.h>
void main()
{
const int MAX = 1000;
const char terminatore = '$';
char c, stringa[MAX], codifica[MAX];
int numCaratteri = 0, i;
printf ("Inserisci caratteri; termina con %c:", terminatore);
scanf ("%c", &c);
while (c != terminatore) {
stringa[numCaratteri] = c; numCaratteri++; scanf ("%c", &c); }
for (i = 0; i < numCaratteri; i++) {
if (stringa[i] == ' ‘) {
codifica[i] = '_‘; }
else if (stringa[i] < 'z‘) {
codifica[i] = stringa[i] + 1;}
else {
codifica[i] = 'a‘; }
}
printf ("\nStringa codificata: ");
for (i = 0; i < numCaratteri; i++) {printf ("%c", codifica[i]);
}

similar documents