Oggi sono andato a svolgere la selezione scolastica delle olimpiadi d’informatica.
Ero un po’ preoccupato, dato che pensavo dovessimo fare subito quello che si fa dalle selezioni regionali in poi, ovvero danno il testo di un problema che noi dobbiamo risolvere scrivendo un programma adatto, eppure per questa selezione scolastica il ritrovo era in un’aula senza computers, il che mi aveva portato a pensare che dovessimo fare qualche oscenità tipo scrivere il programma in penna su un foglio di carta :|.
Vado comunque insieme al mio compagno nell’aula (io e il mio compagno gli unici due di terza, l’altra ventina di ragazzi era di quarta), ed una volta lì ricomincio a sperare in un qualcosa di serio, dato che il prof che gestiva il tutto è davvero uno molto in gamba e capace. Ed effettivamente la prova mi è piaciuta molto. Era divisa in due parti: una logico-matematica ed una di programmazione.
Gli esercizi logico-matematici erano esercizi del tipo:
C’è una paninoteca nella quale fanno scegliere al cliente quali ingredienti mettere nei panini. Ci sono 5 ingredienti, ognuno dei quali può essere messo nel panino o meno indipendentemente dagli altri, basta che nel panino ci sia sempre almeno un ingrediente.
Quanti panini diversi si possono creare?
Se pensiamo che ogni ingrediente può essere messo o meno, possiamo associare subito quest’idea al sistema binario. Ogni bit indica un ingrediente, 1 indica che l’ingrediente è presente, 0 che non è presente.
Le diverse combinazioni possibili saranno quindi:
00000
00001
00010
00011
00100
00101
.. e così via, per un totale di 2^5 combinazioni, ovvero 32. Ma dato che ci deve essere sempre almeno un ingrediente dobbiamo scartare 00000, le combinazioni possibili sono quindi 31.
gli esercizi di programmazione erano invece principalmente esercizi nei quali bisognava comprendere cosa faceva un determinato programma o una funzione, per esempio:
si consideri la funzione:
int foo(int x) {
if ( x == 1): return 1;
else: return foo(x - 1) + 2*x -1
}
Cosa ritorna la chiamata foo(10)?
In questo esempio la funzione ricorsiva non fa altro che calcolare il quadrato di un numero, per cui ritornerà 100.
(infatti, se consideriamo y come il nostro argomento possiamo dire che: y = x + 1 -> y^2 = x^2 + 2x + 1 = x^2 + 2 * (y - 1) + 1 = x^2 + 2y - 1, ovvero esattamente la formula della funzione, come vedete non è magia ;))
Io il mio compagno ed un altro che non conosco eravamo gli unici ad eseguire la prova per il linguaggio C/C++ (poiché siamo autodidatti), mentre tutti gli altri hanno scelto Pascal, dato che è l’unico linguaggio che insegnano a scuola, ed non avevano ancora fatto la ricorsione: per questo noi autodidatti eravamo molto avantaggiati :D
Penso la prova mi sia andata molto bene, non ho trovato nessun problema particolarmente difficile, anche perchè i quesiti logico-matematici erano molto simili a quelli che faccio ogni anno, da ormai 4 anni, delle olimpiadi di matematica.
Alle fasi regionali passano i primi due, spero di essere tra quei due.
Di seguito vi scrivo qualche altro quesito che mi ricordo con le relative soluzioni.
- Piero oggi compie gli anni. La zia lo vede ed esclama: “Come sei diventato alto” - “già, sono alto, in centimetri, 12 volte la mia età, e pensa che 3 anni fa ero alto 13 volte la mia età, e nel frattempo sono cresciuto di 24 centimetri”. Quanti anni compie oggi Piero?
- Marco si mette a contare sulle dita nel seguente modo: 1 sul pollice, 2 sull’indice, 3 sul medio, 4 sull’anulare, 5 sul mignolo, 6 sull’anulare, 7 sul medio, 8 sull’indice, 9 sul pollice, 10 sull’indice e così via. Su che dito si troverà il numero 2008?
Soluzioni:
1: 15. Si poteva impostare matematicamente il problema nel seguente modo: rappresentiamo l’altezza con y e l’età con x:
y = 12x;
y - 24 = 13(x-3) -> 12x - 24 = 13x - 39 -> x = 15.
infatti: 15 * 12 = 180
12 * 13 = 156
180 - 156 = 24
2: sull’indice. Per trovare su che dito si troverà un qualsiasi numero basta dividere il numero per 8 e guardare il resto: se è 1 il dito è il pollice, se è 2 o 0 l’indice, se 3 o 7 il medio, se 4 o 6 l’anulare, se 5 il mignolo.
N.B. Le soluzioni sono mie soluzioni che ho trovato oggi, molto probabilmente sono corrette, ma ci potrebbe essere qualche errore o magari non ho compreso bene il testo del problema, quindi potrebbero anche essere sbagliate.
