Display a 7 segmenti

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

Quelo
Livello 7
Livello 7
Messaggi: 716
Iscritto il: ven giu 16, 2006 3:34 pm

Display a 7 segmenti

Messaggio da Quelo »

Prendiamo un display a 7 segmenti, di quelli classici che si usavano per gli orologi digitali.
Immaginiamo che ad ogni segmento sia collegato un interruttore che permette di accenderlo o spegnerlo.
Partendo dal display spento, visualizzare tutte le cifre da 0 a 9, con il minor numero di manovre sugli interruttori.
Ad esempio per passare da 1 a 2 servono 5 manovre (1 segmento va spento e altri 4 accesi), mentre per passare da 1 a 3 bastano 3 manovre.
Qual è il numero minimo di manovre e quali sono le sequenze ottimali?

Display.png
Display.png (7.35 KiB) Visto 1273 volte
La sequenza qui rappresentata comporta 34 manovre.
[Sergio] / $17$

Pasquale
Livello 12
Livello 12
Messaggi: 2831
Iscritto il: mer mag 25, 2005 2:14 am

Re: Display a 7 segmenti

Messaggio da Pasquale »

Per il momento parto con una sequenza da 22 accensioni/spegnimenti:
.
.
Numeri.jpg
Numeri.jpg (13.72 KiB) Visto 1257 volte
.
.

Segue altra sequenza da 20 (se non è il minimo, dovrebbe esservi abbastanza vicino):
.
.


Numeri 2.jpg
Numeri 2.jpg (14.07 KiB) Visto 1256 volte
_________________

\text {   }ciao Immagine ciao
E' la somma che fa il totale (Totò)

Quelo
Livello 7
Livello 7
Messaggi: 716
Iscritto il: ven giu 16, 2006 3:34 pm

Re: Display a 7 segmenti

Messaggio da Quelo »

Bravo Pasquale, ci sei abbastanza vicino.
Ci sono 2 sequenze che danno la soluzione minima, una di queste non usa nessun passaggio da 3 manovre
[Sergio] / $17$

Bruno
Livello 10
Livello 10
Messaggi: 1899
Iscritto il: lun nov 21, 2005 6:07 pm
Località: Bologna

Re: Display a 7 segmenti

Messaggio da Bruno »

Un ulteriore passetto verso la meta (19):

B5 - 7 segmenti.jpg
B5 - 7 segmenti.jpg (8.55 KiB) Visto 1249 volte
(Bruno)

...........................
Invisibile un vento
l'ha apena sfioragia
sospension d'un momento;
e la bola iridessente gera 'ndagia.
{Biagio Marin}
................................................................
Meglio soluzioni sbagliate che risposte esatte.
{Rudi Mathematici}

Bruno
Livello 10
Livello 10
Messaggi: 1899
Iscritto il: lun nov 21, 2005 6:07 pm
Località: Bologna

Re: Display a 7 segmenti

Messaggio da Bruno »

Diciotto:

B5 - 7 segmenti (18).jpg
B5 - 7 segmenti (18).jpg (8.81 KiB) Visto 1233 volte
(Bruno)

...........................
Invisibile un vento
l'ha apena sfioragia
sospension d'un momento;
e la bola iridessente gera 'ndagia.
{Biagio Marin}
................................................................
Meglio soluzioni sbagliate che risposte esatte.
{Rudi Mathematici}

Quelo
Livello 7
Livello 7
Messaggi: 716
Iscritto il: ven giu 16, 2006 3:34 pm

Re: Display a 7 segmenti

Messaggio da Quelo »

Ancora un paio di piccoli passi...
[Sergio] / $17$

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1459
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Display a 7 segmenti

Messaggio da Gianfranco »

Complimenti a tutti, ero rimasto al 19 di Bruno.
Ho visto che si sta consolidando l'inizio 1, 7, 3, ... ma vorrei proporre una soluzione da 19 che parte da 0, 8, 6, ... anche se il costo iniziale di 0 è più elevato di quello di 1.
Allego la figura che ho costruito per giocare.
In ogni casella c'è il COSTO del passaggio dal numero-riga al numero-colonna e viceversa perché l'operazione è commutativa.
7led_1.png
7led_1.png (26.1 KiB) Visto 1229 volte
La sequenza è:
0, 8, 6, 5, 9, 4, 1, 7, 3, 2
Costo: 19

Attenzione: se ho fatto errori nell'assegnare i COSTI, la mia soluzione è da cestinare!
Pace e bene a tutti.
Gianfranco

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1459
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Display a 7 segmenti

Messaggio da Gianfranco »

Se non sbaglio, questo dovrebbe avere costo 17
7led_3.png
7led_3.png (25.49 KiB) Visto 1228 volte
4, 1, 7, 3, 9, 5, 6, 8, 0, 2
...
Credo che si possa arrivare a 16, partendo dal numero 1.

...

Nel caso voleste fare delle prove con questo schema (o correggerlo)
7led_0.png
7led_0.png (21.98 KiB) Visto 1224 volte
Pace e bene a tutti.
Gianfranco

Quelo
Livello 7
Livello 7
Messaggi: 716
Iscritto il: ven giu 16, 2006 3:34 pm

Re: Display a 7 segmenti

Messaggio da Quelo »

Confermo che il minimo è 16.
Io ci sono arrivato a mano con questo procedimento:
- prima ho individuato tutti i passaggi con costo 1 ma non si poteva completare la sequenza
- quindi ho aggiunto i passaggi a costo 2 e realizzato un grafo
- a questo punto mi sono reso conto che ci sono alcuni passaggi obbligati (vuoto --> 1, 1 --> 7 --> 3 oppure 1 --> 4 --> 9, ecc...) e ho trovato il percorso da 16

Grafo display.png
Grafo display.png (40.85 KiB) Visto 1205 volte

Per verificarlo ho eseguito una ricerca con il metodo branch & bound e ho scoperto che esiste un altro percorso con costo 16 che però ammette un passaggio da 3
Per scrivere l'algoritmo ho ragionato in questo modo:
- considero il display come un numero binario di 7 bit, dove ogni segmento corrisponde a 1 bit (che può essere acceso o spento)
- confronto ogni possibile coppia di numeri con un'operazione XOR, il numero di bit a 1 del risultato corrisponde al numero di manovre (es 1=0010010, 2=1011101, 1 XOR 2 = 1001111, 5 manovre)
- a questo punto calcolo il costo di ogni possibile percorso, aggiornando di volta in volta il valore minimo
- se durante la somma il valore del percorso supera il minimo tutte le altre possibilità che hanno in comune la stessa prima parte, vengono automaticamente scartate
Ultima modifica di Quelo il dom apr 17, 2022 5:29 pm, modificato 1 volta in totale.
[Sergio] / $17$

Bruno
Livello 10
Livello 10
Messaggi: 1899
Iscritto il: lun nov 21, 2005 6:07 pm
Località: Bologna

Re: Display a 7 segmenti

Messaggio da Bruno »

Fantastico :D
(Bruno)

...........................
Invisibile un vento
l'ha apena sfioragia
sospension d'un momento;
e la bola iridessente gera 'ndagia.
{Biagio Marin}
................................................................
Meglio soluzioni sbagliate che risposte esatte.
{Rudi Mathematici}

Pasquale
Livello 12
Livello 12
Messaggi: 2831
Iscritto il: mer mag 25, 2005 2:14 am

Re: Display a 7 segmenti

Messaggio da Pasquale »

Anch'io sono arrivato a mano alla sottostante sequenza, leggibile anche all'inverso, considerando il primo numero come già acceso (da provare se si può ancora calare):
.
.

..............2.......1........2........2.......2......1.......2........2........1 = 15
Numeri.jpg
Numeri.jpg (14.23 KiB) Visto 1199 volte
Per quanto concerne il quesito originale, ho trovato la sequenza da 16: 1-7-3-2-8-0-6-5-9-4 che è la stessa di cui sopra, letta all'incontrario, ma con partenza dall' 1 e legando poi alla fine i primi tre saltati, cioè 5-9-4
_________________

\text {   }ciao Immagine ciao
E' la somma che fa il totale (Totò)

Quelo
Livello 7
Livello 7
Messaggi: 716
Iscritto il: ven giu 16, 2006 3:34 pm

Re: Display a 7 segmenti

Messaggio da Quelo »

Bravo Pasquale, hai trovato la sequenza corretta, per l'altra da 16 basta scambiare lo 0 con l'8, si perde una manovra da 2 a 0 ma la si gudagna da 8 a 6
Nella tua sequenza da 15 se sposti il 6 in fondo, diventa 14.

Complimenti anche agli altri.
Interessante il metodo di Gianfranco, che lavora direttamente sulla matrice.
Segnalo solo che per il passaggio da 2 a 4 e viceversa sono 5 manovre.

In calce vi lascio il mio algoritmo

Grafo display 16-1.png
Grafo display 16-1.png (39.88 KiB) Visto 1191 volte
Grafo display 16-2.png
Grafo display 16-2.png (38.57 KiB) Visto 1191 volte

Codice: Seleziona tutto

OPTION BASE 0
LET n=10

! dispongo gli interruttori in linea e considero il display un numero binario di 7 bit
! alto, alto-sinistra, alto-destra, centro, basso-sinistra, basso-destra, basso
DATA "1110111" ! 0
DATA "0010010" ! 1
DATA "1011101" ! 2
DATA "1011011" ! 3
DATA "0111010" ! 4
DATA "1101011" ! 5
DATA "1101111" ! 6
DATA "1010010" ! 7
DATA "1111111" ! 8
DATA "1111011" ! 9
DATA "0000000" ! spento

DIM d$(n) ! numeri sul display
MAT READ d$

DIM m(n,n) ! matrice delle manovre
DIM s$(n+1) ! array dei numeri rimanenti nel percorso
LET s$(1)="0123456789"

DIM p(n+1) ! puntatore di s$
LET p(1) = 1

DIM r(n) ! numero nel percorso
LET r(0)=10

LET tmin = 100

! confronto le coppie di numeri con XOR
FOR i = 0 TO 9
   FOR j = i TO 10
      FOR k = 1 TO 7
         IF mid$(d$(i),k,1)<>mid$(d$(j),k,1) THEN LET m(i,j)=m(i,j)+1
      NEXT K 
      LET m(j,i)=m(i,j)
   NEXT J 
NEXT I 
MAT PRINT m;

! calcolo il costo di ogni percorso
FOR i = 1 TO 10 ! posizione nella sequenza
   IF i = 0 THEN EXIT FOR
   IF q=1 THEN ! condizione per cui tutte le possibilità a valle sono state esplorate
      LET p(i) = p(i) + 1 ! incremento il puntatore di posizione
      IF p(i) > n-i+1 THEN
         IF i = 1 THEN EXIT FOR
         LET t = t - m(r(i-2),r(i-1))
         LET i = i - 2
      ELSE
         LET q=0
      END IF
   END IF
   IF q=0 THEN
      LET v$ = mid$(s$(i),p(i),1) ! numero in posizione i
      LET r(i) = VAL(v$)
      LET s$(i+1) = left$(s$(i),p(i)-1)&right$(s$(i),LEN(s$(i))-p(i))
      LET t = t + m(r(i-1),r(i))
      LET p(i+1) = 1
      IF i = 10 OR t > tmin THEN
         IF t <= tmin THEN
            LET tmin = t
            MAT PRINT r;
            PRINT t
         END if
         LET q = 1
         LET t = t - m(r(i-1),r(i))
         LET i = i - 1
      END IF
   END IF
NEXT I
END
Ultima modifica di Quelo il dom apr 17, 2022 5:31 pm, modificato 1 volta in totale.
[Sergio] / $17$

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1459
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Display a 7 segmenti

Messaggio da Gianfranco »

Quelo ha scritto:
lun gen 31, 2022 7:37 pm
Per verificarlo ho eseguito una ricerca con il metodo branch & bound e ho scoperto che esiste un altro percorso con costo 16 che però ammette un passaggio da 3
Per scrivere l'algoritmo ho ragionato in questo modo:
...
Complimenti Quelo, soluzione da professionista!
picardclap.jpeg
picardclap.jpeg (8.46 KiB) Visto 1190 volte
La soluzione con un passaggio di costo 3 dovrebbe essere questa, ricavata col tuo procedimento.
7led_quelo.png
7led_quelo.png (46.95 KiB) Visto 1190 volte
1. 7. 3, 2, 0, 8, 6, 5, 9, 4

Nel frattempo ha risposto anche Pasquale, bravissimo!
Pace e bene a tutti.
Gianfranco

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1459
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Display a 7 segmenti

Messaggio da Gianfranco »

Beh, già che ci siamo, diciamo pure i passaggi che richiedono il costo massimo.
Una soluzione potrebbe essere:
7led_max.png
7led_max.png (25.24 KiB) Visto 1189 volte
9, 2, 5, 7, 8, 1, 6, 4, 0, 3
Costo = 43
Pace e bene a tutti.
Gianfranco

Quelo
Livello 7
Livello 7
Messaggi: 716
Iscritto il: ven giu 16, 2006 3:34 pm

Re: Display a 7 segmenti

Messaggio da Quelo »

Quasi, il massimo è 44

8 1 5 2 4 0 3 6 7 9
8 1 5 7 6 3 0 4 2 9
8 1 6 3 0 4 2 5 7 9
8 1 6 7 5 0 3 4 2 9
8 1 6 7 5 2 4 0 3 9
8 1 6 7 5 2 4 3 0 9
8 1 6 7 5 3 0 4 2 9
8 3 0 4 2 5 1 6 7 9
8 3 0 4 2 5 7 6 1 9
8 7 5 1 6 3 0 4 2 9
8 7 5 2 4 0 3 6 1 9
8 7 6 1 5 0 3 4 2 9
8 7 6 1 5 2 4 0 3 9
8 7 6 1 5 2 4 3 0 9
8 7 6 1 5 3 0 4 2 9
8 7 6 3 0 4 2 5 1 9
[Sergio] / $17$

Rispondi