Buona sera, scrivo qui poiché avevo dei dubbi riguardo dei esercizi scritti in questa prova scolastica (Prove scolastiche febbraio 2021), chiedo se si può, di rispondere alle mie domande e se necessario anche una piccola spiegazione.
Esercizio 3
La successione di Fibonacci, i cui primi numeri sono 1, 1, 2, 3, 5, 8, 13, . . . si ottiene in base alla seguente
definizione ricorsiva:
Fib(1) = 1
Fib(2) = 1
Fib(n) = Fib(n-2) + Fib(n-1) se n maggiore di 2
Si consideri invece la successione
1, 2, 11, 50, C
ottenuta in base alla seguente definizione ricorsiva:
Gib(1) = 1
Gib(2) = 2
Gib(n) = A × Gib(n-2) + B × Gib(n-1) se n maggiore di 2
A, B e C sono numeri di cui dovete desumere il valore. Quanto vale C?
Il mio dubbio è: Qual è la definizione di A,B,C e n?
Esercizio 5
Ad una festa sono stati invitati diversi amici, si sa che a 10 di questi piacciono i treni, a 10 piacciono le macchine
da corsa e a 10 gli aerei. Ogni amico pu`o avere anche pi`u di una passione!
Si sa inoltre:
• solo uno ha la passione per tutti 3 i mezzi
• a 7 amici piacciono i treni ma non gli aerei
• a 5 amici piacciono solo le macchine
• a 8 amici piacciono gli aerei ma non le macchine
Quanti sono gli amici in tutto?
Con quale relazione si può risolvere questo esercizio?
Esercizio 9
1: variable m: integer[][][]
2: variable v: integer[]
3: variable i: integer
4: variable j: integer
5: variable k: integer
6: variable t: integer
7: v ← [4, 13, 14, 25, 72]
8: i ← 0
9: while i < 100 do
10: j ← 0
11: while j < 100 do
12: k ← 0
13: while k < 100 do
14: if i × j = k then
15: m[i][j][k] ← 1
16: else
17: m[i][j][k] ← 0
18: end if
19: k ← k + 1
20: end while
21: j ← j + 1
22: end while
23: i ← i + 1
24: end while
25: k ← 0
26: while k < 5 do
27: t ← 0
28: i ← 0
29: while i < 100 do
30: j ← 0
31: while j < 100 do
32: t ← t + m[i][j][v[k]]
33: j ← j + 1
34: end while
35: i ← i + 1
36: end while
37: k ← k + 1
38: output t
39: end while
Non ho capito come risolvere questo esercizio, perciò per chi la capito potrebbe cortesemente spiegarmelo?
Esercizio 10
1: function f(x: integer) → integer
2: if x mod 2 = 0 then
3: return 0
4: else
5: return 1 + f((x − 1) / 2)
6: end if
7: end function
8: function g(x: integer) → integer
9: if x > 250 or x ≤ 0 then
10: return 0
11: else
12: return max(f(x), g(x / 2))
13: end if
14: end function
Cosa s’intende con la funzione Max?
Esercizio 12
Descrizione:
Il seguente programma cerca, all’interno di un array v di n interi, il sottoarray (contiguo) che pu`o essere
partizionato in due sottoarray non vuoti tale per cui la somma della prima parte, meno la somma della seconda
parte `e massima. Il programma usa la costante Infinity, che `e pi`u grande di ogni numero intero (integer).
1: variable i: integer
2: variable j: integer
3: variable k: integer
4: variable l: integer
5: variable s1: integer
6: variable s2: integer
7: variable x: integer
8: x ← −Infinity
9: i ← 0
10: while i < n − 1 do
11: j ← i + 1
12: while j < n do
13: k ← i + 1
14: while k < j do
15: s1 ← 0
16: s2 ← 0
17: l ← i
18: while l < k do
19: s1 ← s1 + v[l]
20: l ← l + 1
21: end while
22: while l ≤ j do
23: s2 ← s2 + v[l]
24: l ← l + 1
25: end while
26: if s1 − s2 > x then
27: x ← s1 − s2
28: end if
29: k ← k + 1
30: end while
31: j ← j + 1
32: end while
33: i ← i + 1
34: end while
35: output x
In questo codice c’è un errore nella riga 14, ma in c’è un errore anche nella 10 dato che si compara i con n che non è stata dichiarata?
Esercizio 14
Quattro gondole A, B, C e D sono ormeggiate sulla riva sinistra di un canale. Un gondoliere deve portare le
quattro gondole sulla riva destra.
Essendo di differente grandezza, le gondole impiegano tempi diversi per attraversare il canale: la gondola A
impiega 2 minuti, la gondola B 4 minuti, la gondola C 9 minuti e la gondola D 13 minuti.
Il gondoliere pu`o condurre una sola gondola alla volta, ma pu`o agganciare alla gondola su cui si trova una
seconda gondola e trainarla, impiegando in questo caso il tempo di quella pi`u lenta.
Qual `e il tempo minimo necessario al gondoliere per trasferire le 4 gondole da una riva all’altra?
Domande: Non capisco, il gondoliere può trasportare 2 gondole (contando la sua 3) o può solo condurre 1(contando la sua 2)?
Poi in caso, impiega il tempo di quella più lenta nel senso, se conduce A e D il tempo totale è quello di D?
Esercizio 15
Poldo `e un famoso mangiatore di panini. Il dottore ha provato a prescrivergli varie diete per convincerlo a
mangiare meno, ma Poldo trova sempre dei modi ingegnosi per aggirare le regole e mangiare quanti pi`u panini
possibile.
Per questo motivo il dottore ha prescritto a Poldo una nuova dieta: potr`a infatti mangiare esattamente K
panini, a patto che l’impatto calorico sia il minimo possibile.
Definiamo impatto calorico la differenza di peso (in grammi) tra il panino pi`u pesante mangiato e quello pi`u
leggero.
Oggi Poldo pu`o mangiare esattamente K = 3 panini. Aiutalo a trovare il minimo impatto calorico possibile,
sapendo che i panini disponibili hanno i seguenti pesi (in grammi):
48, 24, 29, 17, 21, 33, 35, 44, 41
Con quale relazione si può risolvere questo esercizio?
Esercizio 16
Considerate una piramide di numeri, come quella mostrata nella figura che segue. Definiamo una discesa come
una sequenza di numeri ottenuti partendo dalla cima della piramide e giungendo alla base, passando ogni volta
per uno dei due numeri sottostanti. Inoltre, il valore di una discesa `e definito come la somma dei numeri
della discesa. La discesa massima di una piramide `e quella che ha il massimo valore tra tutte le discese della
piramide.
Nell’esempio seguente `e stata evidenziata la discesa ottenuta partendo dalla cima scendendo prima a sinistra e
poi sempre a destra fino alla base. I numeri che compongono tale discesa sono (1, 2, 7, 11) e la loro somma vale
21, che `e il valore di questa discesa.
1
2 9
2 7 5
8 4 11 6
Sia Min il valore della discesa di somma minima, Max il valore della discesa di somma massima. Quanto vale
Min+Max?
Secondo i miei calcoli la discesa minore è (1,2,2,4)=7
e la maggiore (1,9,5,11)=26 la loro somma è 33 però nelle soluzioni l’esercizio invece fa 37, com’è possibile?
Esercizio 17
Avete un insieme di numeri di cui volete calcolare la somma totale. Potete sommare due numeri alla volta,
inserendo il risultato nell’insieme di numeri, fino ad arrivare ad avere un numero solo, pari alla somma totale.
Il costo di una somma `e pari al valore della somma stessa. Ad esempio, se volete sommare i numeri 2,3 e 7,
possiamo ad esempio sommare 2 e 3, con costo 5, e poi sommare 5 e 7, con costo 12. Il costo totale `e quindi
5+12=17. In alternativa, sommando prima 3 e 7 (costo 10) e poi 2 e 10 (costo 12), il costo totale per arrivare
alla somma `e 10+12=22.
Se i numeri da sommare sono i seguenti:
7, 11, 4, 8, 21, 15
qual `e il costo minimo per sommarli tutti tra di loro?
Secondo i miei calcoli il costo della somma di queste cifre è sempre uguale a 66 e non mi varia mai, anche cambiando gli addendi(costo=somma). Però nelle soluzioni mi compare 162, sto sbagliando qualcosa?
poiché lei nel suo procedimento utilizza la gondola meno esosa, se provassi ad utilizzare B,C,D come lei a utilizzato A, avrei numeri più grandi di 28. Quindi rimane un qualche modo, uno scambio di gondole, che mi fa risparmiare un solo minuto. Possibile sia un errore delle soluzioni?