2012-11-30 – 18

I dieci Cavalieri della Tavola Rotonda (tanti furono in un certo periodo della storia) litigavano spesso per sedersi il più vicino possibile a re Artù.
Per risolvere il problema, decisero di adottare una regola di modifica automatica dei propri posti attorno alla Tavola Rotonda.
A ciascuno dei dieci Cavalieri fu assegnata una delle prime dieci lettere dell’alfabeto (da A a J).
Nella prima riunione, il Cavaliere A era seduto nel posto numero 1, B nel 2, C nel 3 e così di seguito ordinatamente I nel posto 9 e J nel 10.

La lista che descrive le posizioni iniziali è dunque:

L_PRIMA_RIUNIONE = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Nelle sedute successive, i Cavalieri avrebbero cambiato il proprio posto secondo la regola descritta nella lista di modifica dei posti:

[(1,7), (2,10), (3,8), (4,5), (5,6), (6,2), (7,9), (8,4), (9,3), (10,1)]

Chi in una riunione occupava il posto indicato dal primo numero di una coppia, nella seduta successiva si sarebbe seduto nel posto indicato dal secondo numero della coppia.

Per esempio: A che nella prima riunione era al posto 1, nella seconda si sarebbe seduto nel posto 7 e nella terza nel posto 9 e poi ordinatamente nei posti 3, 8, 4, 5, 6, 2, 10 per tornare infine al posto 1.

Trovare la lista L_OTTAVA_RIUNIONE che descrive ordinatamente (da A a J) le posizioni dei dieci Cavalieri quando si riuniscono per l’ottava volta.


Soluzione:


Seguo le posizioni dei 10 cavalieri fino all’ottava riunione

A 1 7 9 3 8 4 5 6
B 2 10 1 7 9 3 8 4
C 3 8 4 5 6 2 10 1
D 4 5 6 2 10 1 7 9
E 5 6 2 10 1 7 9 3
F 6 2 10 1 7 9 3 8
G 7 9 3 8 4 5 6 2
H 8 4 5 6 2 10 1 7
I 9 3 8 4 5 6 2 10
J 10 1 7 9 3 8 4 5
Categorie OII

2011-12-02 – 18

2011_12_lm_11Il seguente grafo stradale:

può essere descritto dal seguente insieme di termini (ciascuno dei quali definisce un arco tra due nodi del grafo con la indicazione della relativa distanza)

a(n1,n2,2), a(n2,n3,5), a(n3,n4,3), a(n4,n5,4), a(n5,n6,2), a(n6,n1,3), a(n1,n7,8), a(n2,n7,6), a(n3,n7,1), a(n4,n7,9), a(n5,n7,7), a(n6,n7,4)

Un percorso tra due nodi del grafo può essere descritto con la lista dei nodi che lo compongono ordinati dal nodo di partenza al nodo di arrivo.

Per esempio, la lista [n5, n7, n2, n1] descrive un percorso dal nodo n5 al nodo n1 di lunghezza K = 15.

Dato il grafo stradale corrispondente al seguente insieme di termini:

a(n7,n2,2), a(n2,n3,6),,a(n2,n4,3), a(n9,n3,5), a(n7,n8,5), a(n3,n7,7), a(n4,n7,9), a(n1,n5,10), a(n8,n9,4), a(n6,n8,7), a(n5,n4,6), a(n5,n6,3), a(n6,n7,1), a(n3,n8,15), a(n1,n2,2)

Trovare la lista L del percorso più lungo fra il nodo n1 e il nodo n9 e calcolarne la lunghezza K.

N.B. Un percorso non può mai passare più di una volta da uno stesso nodo.


Soluzione: L=[n1, n5, n4, n7, n6, n8, n3, n9], K=53.


L’esempio del testo corrisponde alla figura

2011_12_18_e

La soluzione del quesito corrisponde al percorso blu in figura

2011_12_18

Categorie OII

2012-11-30 – 19

Un treno merci delle Ferrovie Calabro-Lucane con un locomotore e cinque vagoni (denominati VagA VagB, VagC, VagD e VagE) si trova nella configurazione seguente:

Locomotore VagD VagE VagB VagC VagA

ed è situato nel Binario 1 della zona di manovra rappresentata in figura.

2012_13_ss_19_0Per effettuare una singola operazione di modifica di configurazione, il locomotore deve spostarsi all’indietro dal Binario 1 al Binario 2 oppure al Binario 3 e successivamente ritornare avanti fino al Binario 1.
La modifica di configurazione consiste nello sganciare tutti o parte dei vagoni agganciati al locomotore una volta arrivato
al Binario 2 o al Binario 3, oppure nell’agganciare tutti o parte dei vagoni già presenti sul Binario 2 o sul Binario 3.

Se si vuole riconfigurare il treno perché abbia la seguente configurazione:

Locomotore VagA VagB VagC VagD VagE

Quale è il numero minimo di operazioni necessarie?

  1. 3 operazioni
  2. 5 operazioni
  3. 7 operazioni
  4. 9 operazioni

NOTA: per errore la risposta esatta non compare tra quelle proposte…


Soluzione: 6


Soluzione

Situazione iniziale

2012_13_ss_19_0

I 6 passi necessari

2012_13_ss_19_1

2012_13_ss_19_2

2012_13_ss_19_3

2012_13_ss_19_4

2012_13_ss_19_5

2012_13_ss_19_6

Categorie OII

2012-11-30 – 20

Per descrivere un algoritmo, possiamo utilizzare uno pseudo-linguaggio di programmazione, dove il simbolo ← rappresenta l’istruzione che impone di assegnare al nome simbolico che lo precede il valore calcolato dall’espressione che lo segue

Per esempio: i ← i+1 significa incrementa di 1 il valore associato al nome simbolico i e associa a i il valore incrementato.
Se a i era associato il valore 5, dopo l’esecuzione dell’istruzione a i sarà associato il valore 6.

In questa ipotesi, scegliere la condizione e la istruzione mancanti nel seguente algoritmo in modo che scriva su video il quadrato s di un numero intero n ≥ 0 letto da tastiera:

  1. condizione: i < n
    istruzione: x ← x+2
  2. condizione: i ≤ n
    istruzione: x ← x*2
  3. condizione: x < n
    istruzione: x ← x+2
  4. condizione: i ≤ n
    istruzione: x ← i*2+1

Soluzione: a.


Prova…

n i < n
x ← x+2
i ≤ n
x ← x*2
x < n
x ← x+2
i ≤ n
x ← i*2+1
0 0<0? no!
0
0≤0? sì
s ← 1
x ← 2
i ← 1
1≤0? no!
1
1<0? no!
0
0≤0? sì
s ← 1
x ← 1
i ← 1
1≤0? no!
1
1 0<1 sì
s ← 1
x ← 3
i ← 1
1<1? no!
1
1<1? no!
1
2 0<2 sì
s ← 1
x ← 3
i ← 1
1<2? sì
s ← 4
x ← 5
i ← 2
2<2? no!
4
1<2? sì
s ← 1
x ← 3
i ← 1
3<2? no!
1

Per n=0 falliscono b. e d.
Per n=2 fallisce c.

Categorie OII

2013-11-21 – 17

201314_ss_17_0Un campo di gara per robot ha la forma di un foglio a quadretti o celle; le celle possono contenere ostacoli che impediscono al robot di attraversarle, oppure dei premi; una cella contiene un tesoro.

Con riferimento alla figura, il robot (indicato con una sagoma umana) si trova nella cella individuata dalle coordinate di riga e di colonna (1,1).
Il tesoro, rappresentato da una coppa, è nella cella (8,8).
Il campo contiene ostacoli, individuati da quadrati neri posti in 13 celle.
Altre celle contengono dei premi: ad esempio 8 nella cella di coordinate (4,2) e 10 nella cella (6,4).
Il robot può spostarsi di una cella verso destra o verso l’alto, cioè ad ogni passo solo una delle sue coordinate può aumentare di una unità.

Trovare il numero N di percorsi diversi disponibili al robot per raggiungere il tesoro, la somma massima SMAX e la somma minima SMIN di premi raccoglibili percorrendo questi percorsi.


Soluzione: N=5 – SMAX=50 – SMIN=29


Soluzione

Osserva tutti i percorsi

201314_ss_17_1 201314_ss_17_2 201314_ss_17_3 201314_ss_17_4 201314_ss_17_5

Categorie OII