OII 2021-02-23 – 19

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 è 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 è 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 è 10+12=22.

Se i numeri da sommare sono i seguenti: 7, 11, 4, 8, 21, 15 qual è il costo minimo per sommarli tutti tra di loro?

Risposta: 162

Ciascuna somma parziale deve essere minima per ottenere il costo finale minimo.
A ogni passo bisogna scegliere la coppia di numeri più piccoli.

Osserva la sequenza di somme

  1. 4+7 = 11
  2. 8+11 = 19
  3. 11+15 = 26
  4. 19+21 = 40
  5. 26+40 = 66

Costo minimo = 11+19+26+40+66 = 162

Categorie OII

OII 2021-02-23 – 20

Il pirata Barbagialla trova un’antica mappa che spiega come raggiungere un favoloso tesoro.
La mappa ha la forma di una matrice di celle; le celle possono essere vuote, contenere ostacoli che impediscono a Barbagialla di attraversarle, oppure premi (costituiti da un certo numero di ghinee d’oro); una cella contiene il tesoro.

Con riferimento alla figura, il pirata Barbagialla (la sagoma umana) si trova nella cella individuata dalle coordinate (1,1).
Il tesoro, rappresentato da una coppa, è nella cella (8,8); il campo contiene ostacoli, individuati da quadrati neri posti in 13 celle.
Nove celle contengono dei premi: ad esempio 8 ghinee d’oro nella cella di coordinate (4,2) e 13 nella cella (6,4).
Barbagialla però può spostarsi solo di una cella verso destra o verso l’alto, cioè ad ogni passo solo una delle sue coordinate può aumentare di una unità.
Esistono diversi percorsi disponibili per Barbagialla per raggiungere il tesoro; siano, rispettivamente, MAX il numero massimo e MIN il numero minimo di ghinee d’oro che Barbagialla potrà raccogliere percorrendo questi percorsi.

Quanto vale MAX+MIN?


Osserva tutti i percorsi possibili

Premi: 31, 29, 30, 50, 55

Soluzione:

  • MAX = 55
  • MIN = 29
  • MAX+MIN = 84
Categorie OII

OII 2021-02-23 – 5

Categorie OII

OII 2021-02-23

1

Si consideri la seguente somma, in cui alcune cifre sono state sostituite da X e Y (a lettera uguale corrisponde, naturalmente, cifra uguale)

Quanto vale la somma di X e Y?

2

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, 8, 28, 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?

4

Siano P, Q, R tre variabili booleane, ossia variabili che possono assumere solo uno dei due valori 1 (VERO) e 0 (FALSO).

Ricordiamo che gli operatori booleani sono:

  1. not A, che si indica con ¬A, vale VERO se A è FALSO, e FALSO se A è VERO;
  2. and B, che si indica con A  B, vale VERO se sia A sia B sono VERO, e FALSO in tutti gli altri casi;
  3. or B, che si indica con A  B, vale FALSO se sia A sia B sono FALSO, e VERO in tutti gli altri casi.

Si consideri la seguente tabella di verità per le due variabili booleane P e Q e l’espressione logica ¬ P ∨ Q

Considerate la seguente tabella di verità corrispondente all’espressione logica ¬ P ∨ (Q ∧ (¬ P))

Quale è la stringa, di otto caratteri zero e uno, che rappresenta l’espressione logica di questa tabella di verità (sempre leggendo dall’alto verso il basso)?

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ò avere anche più di una passione!

Si sa inoltre:

  • solo uno ha la passione per tutti 3 i mezzi
  • a 7 amici piacciano i treni ma non gli aerei
  • a 5 amici piacciono solo le macchine
  • a 8 amici piacciano gli aerei ma non le macchine

Quanti sono gli amici in tutto?

13

14

15

16

17

18

Consideriamo il seguente algoritmo, che prende in ingresso un intero positivo N:

  1. Se N vale 1, l’algoritmo termina.
  2. Se N è pari, dividi N per 2, altrimenti (se N è dispari) moltiplicalo per 3 e aggiungi 1.

Per esempio, applicato al valore N = 6, l’algoritmo produce la seguente sequenza (di lunghezza 9, contando anche il valore iniziale N = 6 e il valore finale 1): 6, 3, 10, 5, 16, 8, 4, 2, 1.

La congettura di Collatz, chiamata anche congettura 3N+1, afferma che l’algoritmo qui sopra termini sempre per qualsiasi valore N; in altre parole, se prendo un qualsiasi numero intero maggiore di 1, applicare la regola numero 2 conduce sempre al numero 1.

Considerando i numeri compresi tra 48 e 52 (estremi inclusi), qual è il valore minimo della lunghezza LUN della sequenza (calcolata usando l’algoritmo descritto qui sopra)?

19

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 è 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 è 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 è 10+12=22.

Se i numeri da sommare sono i seguenti: 7, 11, 4, 8, 21, 15 qual è il costo minimo per sommarli tutti tra di loro?

 20

Il pirata Barbagialla trova un’antica mappa che spiega come raggiungere un favoloso tesoro.
La mappa ha la forma di una matrice di celle; le celle possono essere vuote, contenere ostacoli che impediscono a Barbagialla di attraversarle, oppure premi (costituiti da un certo numero di ghinee d’oro); una cella contiene il tesoro.

Con riferimento alla figura, il pirata Barbagialla (la sagoma umana) si trova nella cella individuata dalle coordinate (1,1).
Il tesoro, rappresentato da una coppa, è nella cella (8,8); il campo contiene ostacoli, individuati da quadrati neri posti in 13 celle.
Nove celle contengono dei premi: ad esempio 8 ghinee d’oro nella cella di coordinate (4,2) e 10 nella cella (6,4).
Barbagialla però può spostarsi solo di una cella verso destra o verso l’alto, cioè ad ogni passo solo una delle sue coordinate può aumentare di una unità.
Esistono diversi percorsi disponibili per Barbagialla per raggiungere il tesoro; siano, rispettivamente, MAX il numero massimo e MIN il numero minimo di ghinee d’oro che Barbagialla potrà raccogliere percorrendo questi percorsi.

Quanto vale MAX+MIN?

Categorie OII

OII 2021-02-23

6

Data la seguente funzione

Qual è il valore minimo da passare ad F perché questa ritorni 5?

7

Dato il seguente programma

Qual è il valore dell’ultimo intero che viene stampato durante l’esecuzione di questo programma?

8

Dato il seguente programma

Cosa viene stampato al termine dell’esecuzione?

9

Date le seguenti funzioni:

Tenendo conto che la divisione restituisce un risultato intero (quindi, ad esempio, sia 4/2 che 5/2 restituiscono 2), qual è il massimo x tale per cui G(x)=2?

10

11

Dato il seguente programma:

Qual è l’ultimo valore che viene stampato dal programma?

Categorie OII