C14 #12
Verso le olimpiadi
Piero Scotto - C14
1
Finalità del corso
Finalità del corso
Finalità del corso
Finalità del corso
Finalità del corso
Piero Scotto - C14
2
Allenarsi per le
Olimpiadi
Piero Scotto - C14
3
La selezione scolastica e la
selezione territoriale
Nella prima selezione – che si svolge nel proprio
istituto se partecipante – si risponde ad una
serie di quesiti logico matematici e si debbono
risolvere un gruppo di brevi programmi scritti in
C, dei quali, si deve capire il funzionamento e
fornire il risultato (test a risposta chiusa e aperta)
Piero Scotto - C14
4
La selezione scolastica e la
selezione territoriale
Si supera la prima selezione se si è i primi
dell’istituto, e se si è ottenuto un punteggio alto
sopra la media nazionale. Alcune scuole
classificano fino a 8 studenti. Per arrivare a
questi risultati occorre una specifica
programmazione
Piero Scotto - C14
5
La selezione scolastica e la
selezione territoriale
Nella seconda selezione – che si svolge
nell’istituto di riferimento territoriale (per
adesso a Carmagnola) – si debbono risolvere 3
problemi programmando in C/C++/Pascal
Il primo requisito è che i programmi risolvano i
problemi richiesti a seconda dei diversi dati
forniti, il secondo requisito si basa sulla
“velocità” di esecuzione del programma scritto
Piero Scotto - C14
6
La selezione scolastica e la
selezione territoriale
Piero Scotto - C14
7
La gestione dei file
Piero Scotto - C14
8
Nel sito www.olimpiadi-informatica.it
si trova un correttore e una serie di
esercizi delle selezioni passate su cui
lavorare
Piero Scotto - C14
9
Una caratteristica dei programmi
richiesti alle Olimpiadi è quella di
lavorare su un file di testo dato e
fornite i risultati su un secondo file
di testo prodotto.
(Anche molti temi d’esame dati al
Politecnico fanno uso di file)
Piero Scotto - C14
10
Codice segreto – territoriali 2005
Descrizione del problema
Chicco e Spillo comunicano con dei messaggi scritti in
codice per non essere scoperti. Il loro codice funziona così:
ogni vocale è rappresentata con la vocale successiva in
ordine alfabetico, e ogni consonante con la consonante
successiva. La Y, che è l’ultima vocale, è rappresentata in
codice dalla A, che è la prima vocale. Allo stesso modo, la Z
è rappresentata in codice dalla B.
Per le cifre il discorso è simile: ogni cifra è rappresentata
dalla successiva, e 9 è rappresentato da 0.
Il codice mantiene la distinzione maiuscole/minuscole. Gli
spazi e i segni d’interpunzione (compresi gli accenti) non
sono modificati dal codice segreto.
Aiutiamo Chicco e Spillo scrivendo un programma per
codificare i loro messaggi!
Piero Scotto - C14
11
Dati di input
Il file input.txt contiene un intero N nella prima riga. Le
successive N righe contengono del testo in chiaro, con al
più 80 caratteri per riga.
Dati di output
Il programma, leggendo il file di input, deve scrivere in
output N righe contenenti il corrispondente testo in
codice.
Ad es.
2
Quel ramo del lago di Como, che volge a mezzogiorno, tra
due catene non interrotte di monti, tutto a seni e a golfi, a
seconda dello sporgere e del rientrare di quelli, vien, quasi
a un tratto, a ristringersi, e a prender corso e figura di
Piero Scotto - C14
12
#include<stdio.h>
#include<ctype.h>
#include<string.h>
#include<stdlib.h>
int N;
char buffer[100];
char vocali[]="aeiouy"; /* notate questi vettori ! */
char vocaliCambiate[]="eiouya";
char consonanti[]="bcdfghjklmnpqrstvwxz";
char consonantiCambiate[]="cdfghjklmnpqrstvwxzb";
/* se non esiste una regola o non si riesce a trovarla si puo’
utilizzare una strategia come quella sopra che costruisce a
mano il codice. Con questo sistema potrei creare una
codifica piu’ difficile da decriptare */
Piero Scotto - C14
13
int vocale(char c) {
return (c=='a' || c=='e' || c=='i' || c=='o' || c=='u' ||
c=='y'); } /* vocale e’ una funzione che restituisce un intero diverso da zero se c è una vocale */
/* quelle che seguono sono due funzioni che fanno il cambio della vocale o della consonante */
char traduciVocali(char c) {
int i;
for (i=0; i<6; i++)
if (c==vocali[i]) return vocaliCambiate[i];
}
char traduciConsonanti(char c) {
int i;
for (i=0; i<20; i++)
if (c==consonanti[i]) return consonantiCambiate[i];
}
Piero Scotto - C14
14
int main()
{
FILE *in, *out;
int i,j;
in=fopen("input.txt","r"); /* senza controlli d’errore */
out=fopen("output.txt","w");
fscanf(in,"%d",&N); /* simile a scanf ma da file, leggo il numero di righe*/
fgets(buffer,81,in); /* La funzione fgets() legge una linea dallo stream immagazzinandola nel buffer
puntato da s. Sono letti al piu' (size - 1) caratteri, oppure fino al raggiungimento del carattere di new-line '\n' o di EOF.
Viene immagazzinato nel buffer anche l'eventuale carattere di new-line '\n' che venisse incontrato.
Dopo l'ultimo carattere letto, viene inserito nel buffer il carattere '\0' (terminatore della stringa ASCIIZ). */
for (j=0; j<N; j++) /* qui comincia la lettura delle N righe */
{ fgets(buffer,81,in);
for (i=0;buffer[i]!='\0';i++) /* leggo ogni carattere fino all’ultimo */
{
int flag=0; /* flag, temp e c sono variabili locali */
char temp, c=tolower(buffer[i]);
if (c!=buffer[i]) flag=1; /* allora il carattere in buffer[i] era maiuscolo */
Piero Scotto - C14
15
if (isalpha(c)) /* considero solo lettere, non altri caratteri */
{
if (vocale(c)) temp=traduciVocali(c); /* temp e’
il carattere
temporaneo */
else temp=traduciConsonanti(c); /* se non e’ una vocale */
if (flag) temp=toupper(temp); /* flag e’ a 1 se il carattere e’ maiuscolo.
L’uso di flag e le conversioni in minuscolo e poi in maiuscolo servono solo per non
utilizzare due vettori di conversione anche per le lettere maiuscole */
fprintf(out,"%c",temp);
}
else if (isdigit(c)) fprintf(out,"%d",((c-'0')+1)%10); /* se e’
un carattere che rappresenta un numero restituisco il
numero incrementato di 1, modulo 10. Es. 3 diventa 4, 9
diventa 10 quindi 0 */
else fprintf(out,"%c",c); /* per gli spazi, le virgole, ecc */
}}
return 0;
}
Piero Scotto - C14
16
Dati di input
Il file input.txt contiene un intero N nella prima riga. Le
successive N righe contengono del testo in chiaro, con al
più 80 caratteri per riga.
Dati di output
Il programma, leggendo il file di input, deve scrivere in
output N righe contenenti il corrispondente testo in
codice.
Ad es.
2
Quel ramo del lago di Como, che volge a mezzogiorno, tra
due catene non interrotte di monti, tutto a seni e a golfi, a
seconda dello sporgere e del rientrare di quelli, vien, quasi
a un tratto, a ristringersi, e a prender corso e figura di
Piero Scotto - C14
17
Dati di input
Il file input.txt contiene un intero N nella prima riga. Le
successive N righe contengono del testo in chiaro, con al
più 80 caratteri per riga.
Dati di output
Il programma, leggendo il file di input, deve scrivere in
output N righe contenenti il corrispondente testo in
codice.
Ad es.
2
Quel ramo del lago di Como, che volge a mezzogiorno, tra
due catene non interrotte di monti, tutto a seni e a golfi, a
seconda dello sporgere e del rientrare di quelli, vien, quasi
a un tratto, a ristringersi, e a prender corso e figura di
Piero Scotto - C14
18
Dati di input
Il file input.txt contiene un intero N nella prima riga. Le
successive N righe contengono del testo in chiaro, con al
più 80 caratteri per riga.
Dati di output
Il programma, leggendo il file di input, deve scrivere in
output N righe contenenti il corrispondente testo in
codice.
Ad es.
2
Quel ramo del lago di Como, che volge a mezzogiorno, tra
due catene non interrotte di monti, tutto a seni e a golfi, a
seconda dello sporgere e del rientrare di quelli, vien, quasi
a un tratto, a ristringersi, e a prender corso e figura di
Piero Scotto - C14
19
Piero Scotto - C14
20
Piero Scotto - C14
21
Piero Scotto - C14
22
Piero Scotto - C14
23
L’ordinamento. La
funzione qsort
Piero Scotto - C14
24
La funzione qsort (algoritmo di Quick sort)
Nel linguaggio C è presente la funzione qsort di libreria (stdlib.h) che
permette di ordinare un vettore di elementi a un costo O(N log N),
che quindi è sicuramente buono in termini di prestazioni.
La funzione ha il seguente prototipo:
int qsort(void *v, size_t dimV, size_t dimE,
int (*cmp)(const void *a,const void *b))
dove v è l’indirizzo del vettore da ordinare, dimV è la dimensione del
vettore, dimE è la dimensione di un singolo elemento del vettore e
cmp è la funzione che contiene il criterio con cui si può dire che un
elemento è minore, maggiore o uguale di un altro. La funzione è
progettata per poter agire su vettori contenenti qualsiasi tipo di
dato, anche quelli definiti dal programmatore, ad esempio attraverso
delle strutture, e quindi la sua interfaccia deve essere
sufficientemente generica per poterlo permettere.
Piero Scotto - C14
25
Come primo esempio supponiamo di voler ordinare un vettore di 10 interi: in
questo caso la chiamata alla funzione qsort, supponendo che il vettore si chiami
appunto vettore, sarà la seguente:
qsort(vettore,10,sizeof(int),cmp);
Ovviamente per realizzare l’ordinamento dovrà essere definita la funzione cmp,
che risulta essere la parte più “complicata”. La funzione cmp deve comportarsi
come la funzione strcmp di confronto tra stringhe nel C, cioè dovrà restituire un
valore positivo se il primo elemento da confrontare è maggiore del secondo,
minore di zero se il primo elemento è minore del secondo e uguale a zero se i
due elementi sono uguali. In questo caso la funzione cmp dovrà essere così
definita:
int cmp(const void *a, const void *b)
{
int primo = *(int *)a;
int secondo = *(int *)b;
if (primo > secondo) return 1;
if (primo < secondo) return -1;
return 0;
}
Piero Scotto - C14
26
Come si può facilmente notare la funzione fa esattamente quanto detto in
precedenza; qualche difficoltà di interpretazione la potrebbero dare le prime
due righe, che in effetti non fanno altro che assegnare i valori degli interi da
confrontare alle variabili primo e secondo, attraverso l’operatore di casting e la
dereferenziazione dei puntatori.
Se il vettore fosse ad esempio un vettore di double basterebbe sostituire alla
parola int la
parola double e tutto funzionerebbe senza altre modifiche. Se poi si volesse
ordinare in ordine discendente anziché ascendente basterebbe “invertire” la
definizione della funzione cmp.
Cosa succede se invece di voler ordinare un vettore formato da tipi predefiniti
(int, float, double, ecc.) ci fosse l’esigenza di ordinare un vettore di strutture dati
costruite ad hoc per il programma?
In realtà le modifiche da fare sono minime, una volta capito come funziona qsort
e la
funzione di comparazione. Se ad esempio fosse stata definita una struttura per
contenere i dati di peso e altezza di una persona in questo modo:
Piero Scotto - C14
27
struct persona{
int peso;
int altezza;
};
allora la chiamata di qsort risulterebbe fatta in questo modo
qsort(vettore,10,sizeof(persona),cmp);
e la funzione di comparazione avrebbe questa dichiarazione
int cmp(const void *a, const void *b) {
persona primo = *(persona *)a;
persona secondo = *(persona *)b;
if (primo.peso > secondo.peso) return 1;
if (primo.peso < secondo.peso) return -1;
if (primo.altezza > secondo.altezza) return 1;
if (primo.altezza < secondo.altezza) return -1;
return 0;
}
Piero Scotto - C14
28