Indovinello algoritmico.

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

Moderatori: Gianfranco, Bruno

Rispondi
Bruno
Livello 9
Livello 9
Messaggi: 1529
Iscritto il: lun nov 21, 2005 6:07 pm
Località: Bologna

Indovinello algoritmico.

Messaggio da Bruno »

In una libreria mi è capitato fra le mani un testo molto gradevole, si tratta di "Breve e universale storia degli algoritmi" di Luigi Laura, docente di Machine Learning e Analisi dei Big Data alla Luiss e responsabile tecnico e scientifico delle Olimpiadi Italiane di Informatica.

Si tratta di un volume pubblicato lo scorso anno, scritto con particolare chiarezza e uno stile coinvolgente, anche per chi ha esigue esperienze nel campo degli algoritmi e dell'informatica in genere (come me).

Si scoprono cose curiose. Come quando, a causa dell'interazione di due algoritmi, un libro venduto su Amazon a un prezzo iniziale di appena cento dollari, a un certo punto è venuto a costare ventiquattro milioni di dollari :o

Alla fine di ogni capitolo viene proposto un indovinello algoritmico, appunto, e di seguito ne trascrivo uno.

Guardiamo lo schema:

Laura_IndAlg.jpg
Laura_IndAlg.jpg (4.36 KiB) Visto 3436 volte

Domanda 1.
Considerate i numeri da 1 a 6. Riuscite a disporli nelle precedenti celle rispettando i versi?

Domanda 2.
Riuscite a inventare un algoritmo che, data una qualsiasi lista di numeri (tutti distinti tra di loro) e una serie di celle da riempire, riesca a mettere i numeri nelle celle rispettando i versi?

Limitiamoci a carta e penna :wink:
Invisibile un vento
l'ha apena sfioragia
sospension d'un momento;
e la bola iridessente gera 'ndagia.
(Biagio Marin)

franco
Livello 8
Livello 8
Messaggi: 1192
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Re: Indovinello algoritmico.

Messaggio da franco »

Mi sembra che la domanda 1 abbia svariate soluzioni valide:
1<5>3<4<6>2
2<4>1<5<6>3
3<6>2<4<5>1
4<5>1<2<6>3
....
Il numero uno deve essere in prima, terza o sesta posizione.
Il numero sei in seconda o quinta.
Per il resto ci sono tante possibilità.

Per la domanda 2 devo pensare a un approccio ...
Franco

ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician

gnugnu
Livello 4
Livello 4
Messaggi: 147
Iscritto il: dom set 07, 2014 2:00 pm

Re: Indovinello algoritmico.

Messaggio da gnugnu »

Come dice Franco vi sono molte disposizioni accettabili. Sarebbe interessante trovare un algoritmo per contare quante siano in generale.
Uno per disporre correttamente i numeri, a mano e senza pretesa di ottimizzare la rapidità di esecuzione, potrebbe essere l'adattamento di quello usato per bilanciare le parentesi in un'espressione:
Si inizia da uno degli estremi etichettando la prima casella di quel lato con un numero arbitrario , si prosegue passando alla casella contigua associando a questa il numero della casella precedente aumentato/diminuito di $ 1 $ in modo da rispettare la relazione fra le due e si itera fino all'etichettatura dell'ultima casella.
A questo punto basta individuare le(la) caselle con l'etichetta più grande, farcirle (a caso se sono più di una) con i ripieni più consistenti e ripetere il procedimento diminuendo di uno il valore dell'etichetta, iterando fino alla fine del compito.
Ciao

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

Re: Indovinello algoritmico.

Messaggio da Bruno »

Gnugnu, per rendere il tuo ragionamento più chiaro (soprattutto a me) puoi applicarlo intanto (passo passo, se ti è possibile) al caso proposto con la prima domanda?

Grazie :D
Invisibile un vento
l'ha apena sfioragia
sospension d'un momento;
e la bola iridessente gera 'ndagia.
(Biagio Marin)

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

Re: Indovinello algoritmico.

Messaggio da Gianfranco »

Ecco una proposta, da dimostrare e implementare.
Algoritmo:
1) Scrivo nell'ordine i numeri 1, 2, 3, ... nelle caselle seguite dal segno "<"
2) Scrivo nell'ordine i numeri n, n-1, n-2,... nelle restanti caselle.

Se i numeri dati non sono 1, 2, 3, ..., n, dapprima li metto in ordine crescente, poi li indicizzo, poi scrivo i vari n(i) nelle caselle i-esime.

Aggiornamento.
Ecco l'implementazione in BASIC.

Codice: Seleziona tutto

!'Numero dei dati (indici)
DATA 10
!'Sequenza di relazioni
DATA "<",">",">",">",">","<",">",">","<"
!'Inizializzazione variabili
RESTORE
READ n
DIM a(n)
DIM r$(n-1)
LET magg=0
LET mino=0
!'Algoritmo
FOR i=1 TO n-1
   READ a$
   LET r$(i)=a$
   IF a$="<" THEN
      LET mino=mino+1
      LET a(i)=mino
   END IF
   IF a$=">" THEN
      LET magg=magg+1
      LET a(i)=n-magg+1
   END IF
NEXT i
LET a(n)=n-magg
!'Stampa
FOR i=1 TO n-1
   PRINT a(i);r$(i);
NEXT i
PRINT a(n)
END
Pace e bene a tutti.
Gianfranco

franco
Livello 8
Livello 8
Messaggi: 1192
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Re: Indovinello algoritmico.

Messaggio da franco »

Interpretando l'ipotesi di Gnugnu e applicandola al nostro caso A<B>C<D<E>F potrebbe essere così (passo passo):
- associo arbitrariamente il "valore di riferimento" VR=0 alla casella A
- B è maggiore quindi gli assegno un VR=1
- C con lo stesso criterio è nuovamente VR=0
- D assume VR=1, E -> VR=2 e F -> VR=1
- alla fine mi trovo così: 0<1>0<1<2>1

Sulla casella con il valore di riferimento più alto (VR=2) metto il numero 6, su quelle successive (VR=1) metto i numeri successivi, 5-4-3 (a caso, tanto va bene comunque) e infine metto sulle caselle con VR=0 gli ultimi due numeri 2-1
Quindi per finire 1/2<3/4/5>2/1<4/5/3<6>5/3/4

Ipotizzando un mix di caselle diverso:
A>B>C>D<E<F mi porta a 0>-1>-2>-3<-2<-1 e quindi 6>5/4>3/2>1<2/3<4/5

Evidentemente, questo sistema trova soluzioni valide ma ce ne possono essere anche di diverse; nel secondo esempio funziona anche 4>3>2>1<5<6
Franco

ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician

gnugnu
Livello 4
Livello 4
Messaggi: 147
Iscritto il: dom set 07, 2014 2:00 pm

Re: Indovinello algoritmico.

Messaggio da gnugnu »

@Bruno
Decido di partire da sinistra con l'etichetta "5" (è del tutto indifferente, ma così evito i negativi), aumentando di uno quando transito per un "<" e diminuendo di uno nel caso opposto, ottengo, nell'ordine:
$ [5,6,5,6,7,6]$
queste etichette rispettano le relazioni d'ordine volute; alcune si ripetono, ma questo indica semplicemente che vi sono, sicuramente, più soluzioni.
Cerco il(i) massimo delle etichette: $ 7 $, in quella casella scrivo il maggiore dei numeri proposti $ 6 $.
Cerco le caselle marchiate con $ 6 $, son tre, in queste scrivo i tre maggiori numeri proposti restanti $ 3,4,5 $, non importa in quale ordine.
Cerco le caselle etichettate con $ 5 $, sono due, vi scrivo i numeri restanti. Ottenendo ad esempio:
$[1,3,2,4,6,5]$, ma anche $[2,5,1,3,6,4]$, oppure $[1,4,2,5,6,3]$..........

Se avessi iniziato da destra, poniamo con l'etichetta $ 2 $, avrei ottenuto:
$[1,2,1,2,3,2]$ che differiscono dalle etichette trovate prima per una costante ($4$) e questo si dimostra facilmnte.
NB Le $ 6 \cdot 2=12 $ permutazioni generate con questo algoritmo sono, generalmente, lungi dall'esaurire quelle possibili.
Ciao

gnugnu
Livello 4
Livello 4
Messaggi: 147
Iscritto il: dom set 07, 2014 2:00 pm

Re: Indovinello algoritmico.

Messaggio da gnugnu »

@Franco
sottoscrivo (hai postato mentre scrivevo)
Ciao

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

Re: Indovinello algoritmico.

Messaggio da Bruno »

Capito :D
Invisibile un vento
l'ha apena sfioragia
sospension d'un momento;
e la bola iridessente gera 'ndagia.
(Biagio Marin)

gnugnu
Livello 4
Livello 4
Messaggi: 147
Iscritto il: dom set 07, 2014 2:00 pm

Re: Indovinello algoritmico.

Messaggio da gnugnu »

@Gianfranco
molto bello il tuo algoritmo; semplicissimo ed efficiente.
Ciao

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

Re: Indovinello algoritmico.

Messaggio da Gianfranco »

Bruno ha scritto:
gio mar 05, 2020 5:37 pm
Domanda 2.
Riuscite a inventare un algoritmo che, data una qualsiasi lista di numeri (tutti distinti tra di loro) e una serie di celle da riempire, riesca a mettere i numeri nelle celle rispettando i versi?

Limitiamoci a carta e penna :wink:
Cari amici, limitandoci all'uso di carta e penna e al fatto che la domanda chiede solo una soluzione (non tutte), la cosa secondo me è molto più semplice di quanto appare a prima vista. O non ho capito qualcosa?
La mia proposta di algoritmo applicata a un esempio con 9 numeri.
algo1.png
algo1.png (1.9 KiB) Visto 3392 volte
---
1)Scrivo nell'ordine i numeri 1, 2, 3, ... nelle caselle seguite dal segno "<"
In questo modo ho scritto tutti i numeri che sono minori di altri numeri. Tutti i numeri che mi restano da scrivere sono sicuramente maggiori di quelli che ho scritto.
Poiché li ho scritti in ordine crescente, sono sicuro che non ci sono inversioni.
algo2.png
algo2.png (4.21 KiB) Visto 3392 volte
---
2) Scrivo nell'ordine i numeri n, n-1, n-2,... nelle restanti caselle.
In questo modo ho scritto tutti i numeri che sono maggiori dei numeri già scritti. Poiché li ho scritti in ordine decrescente sono sicuro che non ci sono inversioni.
algo3.png
algo3.png (4.79 KiB) Visto 3392 volte
---
Se invece vogliamo trovatre tutte le soluzioni, allora il problema si complica (forse).
Pace e bene a tutti.
Gianfranco

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

Re: Indovinello algoritmico.

Messaggio da Bruno »

Bravi!
Il metodo di Gianfranco potrebbe essere riformulato così:
1. ordino i numeri della lista data;
2. guardo il segno di disuguaglianza alla destra della prima cella:
$\;\;$ se è ">", prendo il massimo della lista e lo scrivo nella prima cella, eliminandolo dalla lista,
$\;\;$ se è "<", prendo il minimo della lista e lo scrivo nella prima cella, eliminandolo dalla lista;
3. ripeto l'operazione per ogni cella successiva, fino a collocare l'ultimo numero nella cella rimasta vuota.

Esempio:

[] > [] < [] < [] > [] > [] > [] < [] < []
{1,2,3,4,5,6,7,8,9}

[9] > [] < [] < [] > [] > [] > [] < [] < []
{1,2,3,4,5,6,7,8}

[9] > [1] < [] < [] > [] > [] > [] < [] < []
{2,3,4,5,6,7,8}

[9] > [1] < [2] < [] > [] > [] > [] < [] < []
{3,4,5,6,7,8}

[9] > [1] < [2] < [8] > [] > [] > [] < [] < []
{3,4,5,6,7}

[9] > [1] < [2] < [8] > [7] > [] > [] < [] < []
{3,4,5,6}

[9] > [1] < [2] < [8] > [7] > [6] > [] < [] < []
{3,4,5}

[9] > [1] < [2] < [8] > [7] > [6] > [3] < [] < []
{4,5}

[9] > [1] < [2] < [8] > [7] > [6] > [3] < [4] < []
{5}

[9] > [1] < [2] < [8] > [7] > [6] > [3] < [4] < [5]
Invisibile un vento
l'ha apena sfioragia
sospension d'un momento;
e la bola iridessente gera 'ndagia.
(Biagio Marin)

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

Re: Indovinello algoritmico.

Messaggio da Gianfranco »

gnugnu ha scritto:
ven mar 06, 2020 4:11 pm
@Gianfranco
molto bello il tuo algoritmo; semplicissimo ed efficiente.
Grazie gnugnu. Questa mattina viaggiavo in treno, in uno scompartimento quasi vuoto, alle prese con questo problema: grafici che andavano su e giù ma senza scendere sotto zero, procedure di backtracking e così via. A un certo punto ho pensato che Bruno lo ha definito "indovinello" e dopo un po' mi è venuta in mente una soluzione semplicissima.
Pace e bene a tutti.
Gianfranco

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

Re: Indovinello algoritmico.

Messaggio da Gianfranco »

Bruno ha scritto:
ven mar 06, 2020 5:08 pm
Bravi!
Il metodo di Gianfranco potrebbe essere riformulato così:
1. ordino i numeri della lista data;
2. guardo il segno di disuguaglianza alla destra della prima cella:
$\;\;$ se è ">", prendo il massimo della lista e lo scrivo nella prima cella, eliminandolo dalla lista,
$\;\;$ se è "<", prendo il minimo della lista e lo scrivo nella prima cella, eliminandolo dalla lista;
3. ripeto l'operazione per ogni cella successiva, fino a collocare l'ultimo numero nella cella rimasta vuota.
In effetti, quando ho implementato l'algoritmo in BASIC ho fatto proprio così. In questo modo i numeri si collocano tutti in un unico passaggio.
Ho collocato solo gli indici (1, 2, 3, ...), perché se i numeri dati vengono dapprima ordinati in un vettore a(1), a(2), a(3), ... basta collocare il numero a(i) al posto dell'indice i.

Questo problema è bello perché si può proporre anche alle scuole medie come gioco matematico.
Ed è interessante perché è focalizzato più sull'algoritmo che sul "coding".
Da tempo nella scuola di base si dà troppo risalto al coding rispetto alla creazione di algoritmi, e questo è un errore (grave).
A questo proposito segnalo il bell'articolo:
Speak math, not code, basato su un intervento di Leslie Lamport alla Singapore Management University (SMU), 14 gennaio 2020.
(https://phys.org/news/2020-03-math-code.html)
Pace e bene a tutti.
Gianfranco

Rispondi