Re: Gioco delle N lampadine tutte spente (come fare?)
Inviato: 18/09/2019, 21:46
veciorik ha scritto: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:Testo nascosto, fai click qui per vederloUn interruttore può essere rappresentato da una stringa di N bit, uno per lampadina. Così pure lo stato iniziale.
Gli interruttori operano in XOR sugli stati; poiché XOR è commutativo e associativo la sequenza cercata non è una sequenza ordinata ma un sottoinsieme.
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.
Naturalmente l'algoritmo banale è ridondante e si può ottimizzare in vari modi, sia per ridurre il numero di operazioni che per limitare il consumo di memoria.
Ma questo oltrepassa i requisiti minimi.
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