Indovinello algoritmico.
Moderatori: Gianfranco, Bruno
Questo forum è una sezione del PORTALE DI BASE CINQUE
Indovinello algoritmico.
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
Alla fine di ogni capitolo viene proposto un indovinello algoritmico, appunto, e di seguito ne trascrivo uno.
Guardiamo lo schema:
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
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
Alla fine di ogni capitolo viene proposto un indovinello algoritmico, appunto, e di seguito ne trascrivo uno.
Guardiamo lo schema:
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
(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}
...........................
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}
Re: Indovinello algoritmico.
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 ...
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
ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician
Re: Indovinello algoritmico.
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
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
Re: Indovinello algoritmico.
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
Grazie
(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}
...........................
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}
-
- Supervisore del sito
- Messaggi: 1747
- Iscritto il: ven mag 20, 2005 9:51 pm
- Località: Sestri Levante
- Contatta:
Re: Indovinello algoritmico.
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.
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
Gianfranco
Re: Indovinello algoritmico.
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
- 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
ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician
Re: Indovinello algoritmico.
@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
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
Re: Indovinello algoritmico.
@Franco
sottoscrivo (hai postato mentre scrivevo)
Ciao
sottoscrivo (hai postato mentre scrivevo)
Ciao
Re: Indovinello algoritmico.
Capito
(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}
...........................
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}
Re: Indovinello algoritmico.
@Gianfranco
molto bello il tuo algoritmo; semplicissimo ed efficiente.
Ciao
molto bello il tuo algoritmo; semplicissimo ed efficiente.
Ciao
-
- Supervisore del sito
- Messaggi: 1747
- Iscritto il: ven mag 20, 2005 9:51 pm
- Località: Sestri Levante
- Contatta:
Re: Indovinello algoritmico.
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.
---
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. ---
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. ---
Se invece vogliamo trovatre tutte le soluzioni, allora il problema si complica (forse).
Pace e bene a tutti.
Gianfranco
Gianfranco
Re: Indovinello algoritmico.
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]
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]
(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}
...........................
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}
-
- Supervisore del sito
- Messaggi: 1747
- Iscritto il: ven mag 20, 2005 9:51 pm
- Località: Sestri Levante
- Contatta:
Re: Indovinello algoritmico.
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
- Messaggi: 1747
- Iscritto il: ven mag 20, 2005 9:51 pm
- Località: Sestri Levante
- Contatta:
Re: Indovinello algoritmico.
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.Bruno ha scritto: ↑ven mar 06, 2020 5:08 pmBravi!
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.
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
Gianfranco