Gioco delle N lampadine tutte spente (come fare?)
Ciao a tutti.
Ho cercato qualcosa di attinente alle lampadine sul forum ma ciò che ho trovato (le mille rane, le n lampadine in cerchio, le 100 lampadine, ecc.) non mi hanno fornito alcuno spunto alla soluzione del mio problema.
Ho N lampadine accese/spente a caso. Ho N interruttori con ciascun interruttore che cambia lo stato di M lampadine predefinite contemporaneamente. Trovare la sequenza del minimo numero di interruttori da premere in modo che tutte le lampadine si spengano.
Facciamo un esempio con N=6:
Sia lo stato iniziale (1=accesa e 0=spenta) delle 6 lampadine (da 1 a 6 da sx verso dx):
1 0 1 0 1 1
Di seguito il comportamento dei 6 interruttori:
1: 1 6 (ossia commuta contemporaneamente da acceso a spento e viceversa lo stato delle lampadine 1 e 6)
2: 2 5 (ossia commuta contemporaneamente da acceso a spento e viceversa lo stato delle lampadine 2 e 5)
3: 3 5 (ossia commuta contemporaneamente da acceso a spento e viceversa lo stato delle lampadine 3 e 5)
4: 3 4 6 (ossia commuta contemporaneamente da acceso a spento e viceversa lo stato delle lampadine 3, 4 e 6)
5: 2 5 (ossia commuta contemporaneamente da acceso a spento e viceversa lo stato delle lampadine 2 e 5)
6: 3 4 6 (ossia commuta contemporaneamente da acceso a spento e viceversa lo stato delle lampadine 3, 4 e 6)
Ora ragionandoci un pochino è lampante che per spegnere tutte le lampadine basta premere gli interruttori 1 e 3 perchè:
stato iniziale:
1 0 1 0 1 1
premendo l'interruttore 1 si cambia lo stato delle lampadine 1 e 6 e si passa a:
0 0 1 0 1 0
premendo l'interruttore 3 si cambia lo stato delle lampadine 3 e 5 e si passa a:
0 0 0 0 0 0
portando le lampadine ad essere tutte spente
Ma se abbiamo N lampadine con N interruttori che commutano M lampadine generate casualmente come posso impostare la ricerca della soluzione con un algoritmo?
Voi come impostereste la ricerca della soluzione a questo problema?
Grazie,
Giovanni.
Ho cercato qualcosa di attinente alle lampadine sul forum ma ciò che ho trovato (le mille rane, le n lampadine in cerchio, le 100 lampadine, ecc.) non mi hanno fornito alcuno spunto alla soluzione del mio problema.
Ho N lampadine accese/spente a caso. Ho N interruttori con ciascun interruttore che cambia lo stato di M lampadine predefinite contemporaneamente. Trovare la sequenza del minimo numero di interruttori da premere in modo che tutte le lampadine si spengano.
Facciamo un esempio con N=6:
Sia lo stato iniziale (1=accesa e 0=spenta) delle 6 lampadine (da 1 a 6 da sx verso dx):
1 0 1 0 1 1
Di seguito il comportamento dei 6 interruttori:
1: 1 6 (ossia commuta contemporaneamente da acceso a spento e viceversa lo stato delle lampadine 1 e 6)
2: 2 5 (ossia commuta contemporaneamente da acceso a spento e viceversa lo stato delle lampadine 2 e 5)
3: 3 5 (ossia commuta contemporaneamente da acceso a spento e viceversa lo stato delle lampadine 3 e 5)
4: 3 4 6 (ossia commuta contemporaneamente da acceso a spento e viceversa lo stato delle lampadine 3, 4 e 6)
5: 2 5 (ossia commuta contemporaneamente da acceso a spento e viceversa lo stato delle lampadine 2 e 5)
6: 3 4 6 (ossia commuta contemporaneamente da acceso a spento e viceversa lo stato delle lampadine 3, 4 e 6)
Ora ragionandoci un pochino è lampante che per spegnere tutte le lampadine basta premere gli interruttori 1 e 3 perchè:
stato iniziale:
1 0 1 0 1 1
premendo l'interruttore 1 si cambia lo stato delle lampadine 1 e 6 e si passa a:
0 0 1 0 1 0
premendo l'interruttore 3 si cambia lo stato delle lampadine 3 e 5 e si passa a:
0 0 0 0 0 0
portando le lampadine ad essere tutte spente
Ma se abbiamo N lampadine con N interruttori che commutano M lampadine generate casualmente come posso impostare la ricerca della soluzione con un algoritmo?
Voi come impostereste la ricerca della soluzione a questo problema?
Grazie,
Giovanni.
Risposte
Dove hai trovato questo "gioco" ?
ps: IMHO è un problema di informatica, non un gioco: se fosse così, fallo spostare nella stanza di INFORMATICA, che trovi in ALTRE DISCIPLINE, e mostra i tuoi tentativi di soluzione.
Un indizio: XOR.
ps: IMHO è un problema di informatica, non un gioco: se fosse così, fallo spostare nella stanza di INFORMATICA, che trovi in ALTRE DISCIPLINE, e mostra i tuoi tentativi di soluzione.
Un indizio: XOR.
@gimasci99
Conosci un po' di algebra lineare?
Conosci un po' di algebra lineare?
"veciorik":
Dove hai trovato questo gioco ?
E' un classico anche all'interno dei puzzlegames.
"veciorik":
Dove hai trovato questo "gioco" ?
ps: IMHO è un problema di informatica, non un gioco: se fosse così, fallo spostare nella stanza di INFORMATICA, che trovi in ALTRE DISCIPLINE, e mostra i tuoi tentativi di soluzione.
Ciao veciorik.
Sono nuovo del forum e se il moderatore ritiene opportuno spostarlo nella sezione informatica per me va benissimo. Infatti in pricipio io stesso ero indeciso se inserire tale domanda in questa sezione o nella sezione informatica. Poi ho scelto questa perchè mi è stato proposto come gioco da un amico a cui non ho chiesto dove l'abbia trovato.
Dopodichè hai ragione, la soluzione passerà da un'implementazione informatica. Quindi rimetto la decisione sul posto più appropriato al moderatore.
"veciorik":
Un indizio: XOR.
So bene cos'è un XOR ma potresti essere un tantino più specifico sull'eventuale soluzione che ti è venuta in mente?
Grazie,
Giovanni.
"Bokonon":
@gimasci99
Conosci un po' di algebra lineare?
Ciao Bokonon.
Sì la conosco bene. Tu come la applicheresti al problema?
Grazie,
Giovanni.
"Bokonon":
[quote="veciorik"]Dove hai trovato questo gioco ?
E' un classico anche all'interno dei puzzlegames.[/quote]
Sono d'accordo con te. Oggi anche i più classici dei giochi (anche solo di logica pura) passano per implementazioni informatiche nel momento in cui li si va a generalizzare. Come dicevo a veciorik io stesso ero indeciso se postarla qui o nella sezione informatica. Ad ogni modo lascio al moderatore la decisione.
Grazie in anticipo per eventuali suggerimenti per impostarne la soluzione.
Qualcosa non mi quadra nell'impostazione del quesito. Se il sistema è dato, nessuno mi assicura che la combinazione di comandi sia compatibile con il raggiungimento di una soluzione.
Ad esempio, ci potrebbe essere una lampadina (accesa) non collegata ad alcun interruttore, o due lampadine (con stato iniziale opposto) comandate da un unico interruttore, o altre combinazioni parimenti impossibili.
A meno che il quesito non sia proprio "come collegheresti interruttori a lampadine per minimizzare i comandi necessari a spegnerle tutte, qualunque sia il loro stato iniziale?"
Ad esempio, ci potrebbe essere una lampadina (accesa) non collegata ad alcun interruttore, o due lampadine (con stato iniziale opposto) comandate da un unico interruttore, o altre combinazioni parimenti impossibili.
A meno che il quesito non sia proprio "come collegheresti interruttori a lampadine per minimizzare i comandi necessari a spegnerle tutte, qualunque sia il loro stato iniziale?"
Io suggerirei all'OP di postare per intero ed esattamente il testo del problema originale; così com'è scritto anche a me sembra un po' vago … IMHO
Cordialmente, Alex
Cordialmente, Alex
Comunque, a naso, dal punto di vista informatico, visto che le N lampadine forniscono N informazioni elementari, saranno necessari almeno N interruttori (ovvero la possibilità di modificare il sistema in almeno N modi diversi) cui corrispondono fino ad N operazioni per garantire in ogni caso lo spegnimento.
Aumentando il numero di interruttori potrà diminuire il numero massimo di operazioni necessarie, fino a diventare una sola, se gli interruttori sono in numero pari (e corrispondono) a tutte le combinazioni acceso/spento possibili (2^n).
...A meno di voler contare sulla possibilità di fulminare le lampadine accendendole e spegnendole per migliaia di cicli, in tal caso basta un interruttore generale e stare per settimane a lavorarci.
Aumentando il numero di interruttori potrà diminuire il numero massimo di operazioni necessarie, fino a diventare una sola, se gli interruttori sono in numero pari (e corrispondono) a tutte le combinazioni acceso/spento possibili (2^n).
...A meno di voler contare sulla possibilità di fulminare le lampadine accendendole e spegnendole per migliaia di cicli, in tal caso basta un interruttore generale e stare per settimane a lavorarci.
per ribadire i dubbi, nell'esempio fornito se le lampadine inizialmente accese sono la 1 e la 4 non c'è soluzione, perché gli interruttori 5 e 6 sono collegati senza criterio (duplicano gli interruttori 2 e 4).
L'OP si è dileguato 2 giorni dopo aver inserito il suo primo ed unico post, non avendo avuto quello che cercava urgentemente: un algoritmo per risolvere il suo problema.
Lo ha mascherato da gioco per scongiurare domande sui suoi tentativi di soluzione.
Naturalmente l'algoritmo può non trovare la sequenza richiesta se questa non esiste, perché gli interruttori sono generati casualmente.
Tanto per giocare:
Lo ha mascherato da gioco per scongiurare domande sui suoi tentativi di soluzione.
Naturalmente l'algoritmo può non trovare la sequenza richiesta se questa non esiste, perché gli interruttori sono generati casualmente.
Tanto per giocare:
"andomito":
per ribadire i dubbi, nell'esempio fornito se le lampadine inizialmente accese sono la 1 e la 4 non c'è soluzione, perché gli interruttori 5 e 6 sono collegati senza criterio (duplicano gli interruttori 2 e 4).
Ciao andomito.
La tua osservazione è corretta ma nella generazione dello stato iniziale delle lampadine e delle lampadine che vengono accese/spente da ciascun interruttore viene data certezza che la soluzione esiste ed è unica.
Quindi non ci si deve preoccupare che la soluzione esista ma solo di capire come impostare l'algoritmo che porti dallo stato iniziale a quello finale con tutti 0 accendendo o spegnendo gli interruttoti in una certa sequenza.
Grazie,
Carlo.
"veciorik":
L'OP si è dileguato 2 giorni dopo aver inserito il suo primo ed unico post, non avendo avuto quello che cercava urgentemente: un algoritmo per risolvere il suo problema.
Lo ha mascherato da gioco per scongiurare domande sui suoi tentativi di soluzione.
Naturalmente l'algoritmo può non trovare la sequenza richiesta se questa non esiste, perché gli interruttori sono generati casualmente.
Tanto per giocare:
Gent.mo veciorik.
Non so perchè le mie risposte non vengono pubblicate ma ho sia dato risposta a ciascuno di voi che mi ha risposto (spero che almeno questa venga pubblicata), sia continuo a seguire le vostre risposte sperando che qualcuno abbia un valido suggerimento. Per quanto riguarda l'urgenza non so invece da dove si evinca nel mio post. La soluzione a questo problema cerco di trovarla per mio diletto e non per lavoro o altro. Quindi la soluzione non è un mio problema e tantomeno è urgente. Se si è in grado e si vogliono proporre delle soluzioni come generalmente si fa nei forum è bene altrimenti grazie comunque.
Giovanni.
Il metodo più semplice ed efficace è codificare gli interruttori in una matrice nel campo Z/2.
E poi operare una riduzione con Gauss-Jordan.
Data la matrice M degli interruttori di dimensione (nxm) composta da "uni" e zeri e di rango $1<=k<=m$
a) se la matrice estesa con lo stato delle lampadine ha rango (k+1) allora non c'è soluzione.
b) se hanno il medesimo rango allora ci sarà un'unica soluzione se $k=m$ oppure soluzioni multiple se k
Se dovessi programmare il tutto farei così.
1) data la matrice estesa M+, richiamo la routine per gauss-jordan.
2) se $rk(M+)>rk(M)$ allora l'output è "nessuna soluzione"
altrimenti "posta il vettore delle soluzioni"
Per la verità, volendo, si potrebbe anche decidere di scartare tutti gli interruttori che sono combinazioni lineari degli altri (trovare una base) e poi risolvere come sopra ottenendo o 1 o nessuna soluzione.
E poi operare una riduzione con Gauss-Jordan.
Data la matrice M degli interruttori di dimensione (nxm) composta da "uni" e zeri e di rango $1<=k<=m$
a) se la matrice estesa con lo stato delle lampadine ha rango (k+1) allora non c'è soluzione.
b) se hanno il medesimo rango allora ci sarà un'unica soluzione se $k=m$ oppure soluzioni multiple se k
Se dovessi programmare il tutto farei così.
1) data la matrice estesa M+, richiamo la routine per gauss-jordan.
2) se $rk(M+)>rk(M)$ allora l'output è "nessuna soluzione"
altrimenti "posta il vettore delle soluzioni"
Per la verità, volendo, si potrebbe anche decidere di scartare tutti gli interruttori che sono combinazioni lineari degli altri (trovare una base) e poi risolvere come sopra ottenendo o 1 o nessuna soluzione.
Ecco un esempio prendendo quello proposto dal OP.
$ M+=( ( 1 , 0 , 0 , 0 , 0 , 0 , 1 ),( 0 , 1 , 0 , 0 , 1 , 0 , 0 ),( 0 , 0 , 1 , 1 , 0 , 1 , 1 ),( 0 , 0 , 0 , 1 , 0 , 1 , 0 ),( 0 , 1 , 1 , 0 , 1 , 0 , 1 ),( 1 , 0 , 0 , 1 , 0 , 1 , 1 ) ) $
Dopo Gauss diventa:
$( ( 1 , 0 , 0 , 0 , 0 , 0 , 1 ),( 0 , 1 , 0 , 0 , 1 , 0 , 0 ),( 0 , 0 , 1 , 1 , 0 , 1 , 1 ),( 0 , 0 , 0 , 1 , 0 , 1 , 0 ),( 0 , 0 , 0 , 0 , 0 , 0 , 0 ),( 0 , 0 , 0 , 0 , 0 , 0 , 0 ) ) $
Da cui $rk(M+)=rk(M)$ e una soluzione minimale è data dall'ultima colonna, ovvero interruttori 1 e 3.
$ M+=( ( 1 , 0 , 0 , 0 , 0 , 0 , 1 ),( 0 , 1 , 0 , 0 , 1 , 0 , 0 ),( 0 , 0 , 1 , 1 , 0 , 1 , 1 ),( 0 , 0 , 0 , 1 , 0 , 1 , 0 ),( 0 , 1 , 1 , 0 , 1 , 0 , 1 ),( 1 , 0 , 0 , 1 , 0 , 1 , 1 ) ) $
Dopo Gauss diventa:
$( ( 1 , 0 , 0 , 0 , 0 , 0 , 1 ),( 0 , 1 , 0 , 0 , 1 , 0 , 0 ),( 0 , 0 , 1 , 1 , 0 , 1 , 1 ),( 0 , 0 , 0 , 1 , 0 , 1 , 0 ),( 0 , 0 , 0 , 0 , 0 , 0 , 0 ),( 0 , 0 , 0 , 0 , 0 , 0 , 0 ) ) $
Da cui $rk(M+)=rk(M)$ e una soluzione minimale è data dall'ultima colonna, ovvero interruttori 1 e 3.
Ciao e grazie a tutti.
Finalmente ho capito come rispondere ossia col pulsante "Rispondi" e non quello "Cita".
Scusate quindi la mia assenza. Non mi sono dileguato e tantomeno disinteressato altrimenti avrei evitato di postare.
Ringrazio quindi:
Tuttavia a questo approccio sugli XOR preferisco quello suggerito su Gauss-Jordan perchè per 10 lampadine magari la cosa è fattibile, per 100 o 1000 ecc. potrebbe diventare inefficiente crescendo credo esponenzialmente il numero dei tentativi da fare.
Quindi proverò prima ad implementare:
Vi tengo informati.
Grazie mille.
Finalmente ho capito come rispondere ossia col pulsante "Rispondi" e non quello "Cita".
Scusate quindi la mia assenza. Non mi sono dileguato e tantomeno disinteressato altrimenti avrei evitato di postare.
Ringrazio quindi:
"veciorik":
Gli interruttori operano in XOR sugli stati;...L'algoritmo banale consiste nell'applicare allo stato iniziale gli interruttori prima uno alla volta, poi a due a due, poi a tre a tre, e via dicendo finché non si ottiene una stringa di bit tutti a zero.
Tuttavia a questo approccio sugli XOR preferisco quello suggerito su Gauss-Jordan perchè per 10 lampadine magari la cosa è fattibile, per 100 o 1000 ecc. potrebbe diventare inefficiente crescendo credo esponenzialmente il numero dei tentativi da fare.
Quindi proverò prima ad implementare:
"Bokonon":
Il metodo più semplice ed efficace è codificare gli interruttori in una matrice nel campo Z/2. E poi operare una riduzione con Gauss-Jordan. Data la matrice M degli interruttori di dimensione (nxm) composta da "uni" e zeri e di rango $ 1<=k<=m $
Vi tengo informati.
Grazie mille.
Meraviglioso !
Non conoscevo questa tecnica per risolvere un sistema di N equazioni di primo grado in N incognite.
Come si fa per applicarlo nel caso in cui tutti i numeri sono binari e l'addizione tra monomi è sostituita da xor ?
Puoi spiegarlo in questo caso, dove bisogna premere tutti gli interruttori :
Non conoscevo questa tecnica per risolvere un sistema di N equazioni di primo grado in N incognite.
Come si fa per applicarlo nel caso in cui tutti i numeri sono binari e l'addizione tra monomi è sostituita da xor ?
Puoi spiegarlo in questo caso, dove bisogna premere tutti gli interruttori :
$ M+=((1,0,0,1,1,1 ),(1,1,0,1,0,1),(1,1,1,0,0,1),(0,1,1,0,1,1),(0,0,1,1,1,1)) $
@veciorik
Beh più che una tecnica è LA tecnica. L'algebra lineare serve a risolvere i sistemi lineari.
Il teorema che fra le righe ho applicato è quello di Rouchè-Capelli.
Per usare l'algebra lineare in un sistema binario, basta imporre (come ho fatto) che il campo di riferimento abbia caratteristica 2 (in questo caso Z/2).Tradotto, significa che tutti i numeri interi dispari sono congrui (=equivalenti) a 1, mentre tutti i numeri pari sono congrui a zero (sto usando usando una definizione allargata di numeri pari e dispari per includere anche i negativi).
Per esempio, vediamo come opera il PC con la matrice che hai scritto, evidenziandone due passaggi.
Usando Gauss-Jordan ma usando i numeri interi, la matrice M+ diventa la matrice triangolare superiore:
$ ( ( 1 , 0 , 0 , 1 , 1 , 1 ),( 0 , 1 , 0 , 0 , -1 , 0 ),( 0 , 0 , 1 , -1 , 0 , 0 ),( 0 , 0 , 0 , 1 , 2 , 1 ),( 0 , 0 , 0 , 0 , -3 , -1 ) ) $
che è congrua a $ ( ( 1 , 0 , 0 , 1 , 1 , 1 ),( 0 , 1 , 0 , 0 , 1 , 0 ),( 0 , 0 , 1 , 1 , 0 , 0 ),( 0 , 0 , 0 , 1 , 0 , 1 ),( 0 , 0 , 0 , 0 , 1 , 1 ) ) $
Ovviamente sia l'umano e soprattutto il PC arrivano direttamente alla seconda forma se ad ogni somma rimpiazzano sempre 0 ed 1 applicando il modulo-2. Ma fondamentalmente non è necessario, si pososno fare tutti questi calcoli e anche i successivi con i numeri interi e solo alla fine effettuare la "traduzione".
La matrice triangolare già mi dice un sacco di cose. Tutti i pivot sono diversi da zero ed essendo M una matrice 5x5, significa che le sue colonne sono una base completa: pertanto so già che non esistono stati finali che non possano essere raggiunti da una combinazione degli interruttori. Tradotto, il sistema ha sempre una e una sola soluzione.
Ora umano e PC continuano con Gauss-Jordan e usano i pivot per annullare tutto ciò che sta sopra la diagonale e ottengono la matrice (già tradotta) $ ( ( 1 , 0 , 0 , 0 , 0 , 1 ),( 0 , 1 , 0 , 0 , 0 , 1 ),( 0 , 0 , 1 , 0 , 0 , 1 ),( 0 , 0 , 0 , 1 , 0 , 1 ),( 0 , 0 , 0 , 0 , 1 , 1 ) ) $
L'ultima colonna è la soluzione, ovvero bisogna cliccare una volta tutti gli interruttori.
Beh più che una tecnica è LA tecnica. L'algebra lineare serve a risolvere i sistemi lineari.
Il teorema che fra le righe ho applicato è quello di Rouchè-Capelli.
Per usare l'algebra lineare in un sistema binario, basta imporre (come ho fatto) che il campo di riferimento abbia caratteristica 2 (in questo caso Z/2).Tradotto, significa che tutti i numeri interi dispari sono congrui (=equivalenti) a 1, mentre tutti i numeri pari sono congrui a zero (sto usando usando una definizione allargata di numeri pari e dispari per includere anche i negativi).
Per esempio, vediamo come opera il PC con la matrice che hai scritto, evidenziandone due passaggi.
Usando Gauss-Jordan ma usando i numeri interi, la matrice M+ diventa la matrice triangolare superiore:
$ ( ( 1 , 0 , 0 , 1 , 1 , 1 ),( 0 , 1 , 0 , 0 , -1 , 0 ),( 0 , 0 , 1 , -1 , 0 , 0 ),( 0 , 0 , 0 , 1 , 2 , 1 ),( 0 , 0 , 0 , 0 , -3 , -1 ) ) $
che è congrua a $ ( ( 1 , 0 , 0 , 1 , 1 , 1 ),( 0 , 1 , 0 , 0 , 1 , 0 ),( 0 , 0 , 1 , 1 , 0 , 0 ),( 0 , 0 , 0 , 1 , 0 , 1 ),( 0 , 0 , 0 , 0 , 1 , 1 ) ) $
Ovviamente sia l'umano e soprattutto il PC arrivano direttamente alla seconda forma se ad ogni somma rimpiazzano sempre 0 ed 1 applicando il modulo-2. Ma fondamentalmente non è necessario, si pososno fare tutti questi calcoli e anche i successivi con i numeri interi e solo alla fine effettuare la "traduzione".
La matrice triangolare già mi dice un sacco di cose. Tutti i pivot sono diversi da zero ed essendo M una matrice 5x5, significa che le sue colonne sono una base completa: pertanto so già che non esistono stati finali che non possano essere raggiunti da una combinazione degli interruttori. Tradotto, il sistema ha sempre una e una sola soluzione.
Ora umano e PC continuano con Gauss-Jordan e usano i pivot per annullare tutto ciò che sta sopra la diagonale e ottengono la matrice (già tradotta) $ ( ( 1 , 0 , 0 , 0 , 0 , 1 ),( 0 , 1 , 0 , 0 , 0 , 1 ),( 0 , 0 , 1 , 0 , 0 , 1 ),( 0 , 0 , 0 , 1 , 0 , 1 ),( 0 , 0 , 0 , 0 , 1 , 1 ) ) $
L'ultima colonna è la soluzione, ovvero bisogna cliccare una volta tutti gli interruttori.
che nostalgia di Geometria I (mio unico 30 e lode)
e che tristezza nel constatare che mi sono dimenticato quasi tutto
e che tristezza nel constatare che mi sono dimenticato quasi tutto
"veciorik":
L'OP si è dileguato 2 giorni dopo aver inserito il suo primo ed unico post, non avendo avuto quello che cercava urgentemente: un algoritmo per risolvere il suo problema.
Lo ha mascherato da gioco per scongiurare domande sui suoi tentativi di soluzione.
Naturalmente l'algoritmo può non trovare la sequenza richiesta se questa non esiste, perché gli interruttori sono generati casualmente.
Tanto per giocare:
Ciao, sono nuovo del forum e anche io mi sto imbattendo in questo stesso problema.
Frequento l'università di informatica e questo quesito è del corso di Algoritmi e Strutture dati e non so come risolverlo, qualcuno saprebbe una soluzione implementativa?
Per ora ho ipotizzato delle combinazioni di tasti in base allo stato iniziale restringendo l'analisi su 3 soli tasti (visto che 3 sono le lampadine che attivano quando un tasto è premuto). Ovvero la mia idea era analizzare in generale la soluzione e poi attuare la ricorsione nodo per nodo, ipotizzo qui di agire su un pulsante centrale (radice) che ha due figli (sx e dx). Se premo un pulsante cambia lo stato di tutti e 3
sx r dx cosa premere
0 0 0 nulla
0 0 1 dx+1 (ovvero non più a dx del destro attuale)
0 1 0 sx+r+dx
0 1 1 dx
1 0 0 sx+1
ecc...
Questo il testo del problema: http://lonati.di.unimi.it/algopig/1819/ ... iu2019.pdf
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo