Piccioni viaggiatori
Moderatori: Gianfranco, Bruno
Questo forum è una sezione del PORTALE DI BASE CINQUE
Piccioni viaggiatori
Ecco a voi un problemino che mi sono inventato in questi giorni e che ho scoperto essere più complesso di quanto immaginassi:
Sia data una striscia di carta suddivisa in $n$ caselle quadrate ($n$ naturale positivo $>1$). La distanza tra due caselle contigue è per definizione unitaria. Tutte le caselle sono numerate progressivamente, da $1$ ad $n$.
Il gioco è il seguente, massimizzare la lunghezza aggregata ($l$) degli $n-1$ segmenti che congiungono i centri di tutte le $n$ caselle, partendo da uno di essi a piacere e tracciando il segmento che termina in un'altra casella, considerare dunque quest'ultima casa come punto di partenza per il secondo segmento e farlo terminare in una delle restanti $22$ caselle ancora libere. Il gioco termina i centri di tutte le case sono stati origine e/o punto terminale di un segmento.
Esempio: $n=2$-->$l=1$, $n=3$-->$l=3$, $n=4$-->$l=7$,...
Qual'è la regola generale?
Sia data una striscia di carta suddivisa in $n$ caselle quadrate ($n$ naturale positivo $>1$). La distanza tra due caselle contigue è per definizione unitaria. Tutte le caselle sono numerate progressivamente, da $1$ ad $n$.
Il gioco è il seguente, massimizzare la lunghezza aggregata ($l$) degli $n-1$ segmenti che congiungono i centri di tutte le $n$ caselle, partendo da uno di essi a piacere e tracciando il segmento che termina in un'altra casella, considerare dunque quest'ultima casa come punto di partenza per il secondo segmento e farlo terminare in una delle restanti $22$ caselle ancora libere. Il gioco termina i centri di tutte le case sono stati origine e/o punto terminale di un segmento.
Esempio: $n=2$-->$l=1$, $n=3$-->$l=3$, $n=4$-->$l=7$,...
Qual'è la regola generale?
Re: Piccioni viaggiatori
marcokrt ha scritto:.... $n=4$-->$l=7$,...
io avrei detto $n=4$-->$l=6$.
o forse ho non ho capito il problema
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: Piccioni viaggiatori
in effetti il testo è alquanto oscuro.
il termine "striscia" fa pensare a elementi in fila
il termine "suddivisa" fa pensare ad una partizione del piano che non lasci spazi tra le caselle, ma
si parla di "distanza tra caselle contigue", nel senso che contigue significa "attaccate", o solo "vicine" ?
si può passare più volte nello stesso punto centrale?
si può intersecare il percorso?
davvero si cerca il percorso più lungo?, o il più corto?
il termine "striscia" fa pensare a elementi in fila
il termine "suddivisa" fa pensare ad una partizione del piano che non lasci spazi tra le caselle, ma
si parla di "distanza tra caselle contigue", nel senso che contigue significa "attaccate", o solo "vicine" ?
si può passare più volte nello stesso punto centrale?
si può intersecare il percorso?
davvero si cerca il percorso più lungo?, o il più corto?
Enrico
Re: Piccioni viaggiatori
Ciao Enrico,
Grazie del commento... passo subito alle risposte chiarificatrici:
1 2 3 4 5 6 ... n-3 n-2 n-1 n
La situazione di partenza è quella che ho scritto sopra. Ogni cella può essere considerata un numero naturale da 1 a n; la lunghezza di un segmento è pertanto data dal valore assoluto della differenza tra il punto di partenza e quello di arrivo (insomma, il valore della cella in cui cade l'estremo più a destra.
Siamo in un contesto "monodimensionale", quindi sì... toccherà passare per forza (n>2) sulla stessa cella più volte, ma una volta che un estremo si colloca su una data cella, essa non può più essere usata come punto di arrivo per un segmento successivo (essa costituirà solo il punto di partenza per il successivo segmento e poi verrà "cancellata"). L'ultima cella sarà chiaramente solo un punto di arrivo e il gioco terminerà lì.
Si cerca il percorso più lungo
Grazie del commento... passo subito alle risposte chiarificatrici:
1 2 3 4 5 6 ... n-3 n-2 n-1 n
La situazione di partenza è quella che ho scritto sopra. Ogni cella può essere considerata un numero naturale da 1 a n; la lunghezza di un segmento è pertanto data dal valore assoluto della differenza tra il punto di partenza e quello di arrivo (insomma, il valore della cella in cui cade l'estremo più a destra.
Siamo in un contesto "monodimensionale", quindi sì... toccherà passare per forza (n>2) sulla stessa cella più volte, ma una volta che un estremo si colloca su una data cella, essa non può più essere usata come punto di arrivo per un segmento successivo (essa costituirà solo il punto di partenza per il successivo segmento e poi verrà "cancellata"). L'ultima cella sarà chiaramente solo un punto di arrivo e il gioco terminerà lì.
Si cerca il percorso più lungo
Re: Piccioni viaggiatori
(Il percorso minimo è facile da calcolare... $l=n-1$).
Re: Piccioni viaggiatori
franco ha scritto:marcokrt ha scritto:.... $n=4$-->$l=7$,...
io avrei detto $n=4$-->$l=6$.
o forse ho non ho capito il problema
Credo tu abbia capito bene... questa è la strategia che ho utilizzato io per il problema dei nove punti esteso... eppure (per n>=4) si può fare di meglio... esempio pratico: n=6-->l=17 (anziché 15).
1 2 3 4 5 6
Segmento 1: 3-->5 (lunghezza=2)
Segmento 2: 5-->1 (lunghezza=4)
Segmento 3: 1-->6 (lunghezza=5)
Segmento 4: 6-->2 (lunghezza=4)
Segmento 5: 2-->4 (lunghezza=2)
Lunghezza totale=17.
Re: Piccioni viaggiatori
potrebbe essere: $l_{n+1} = l_n+n+MOD(n,2)$
_________________
$\text { }$ciao ciao
E' la somma che fa il totale (Totò)
$\text { }$ciao ciao
E' la somma che fa il totale (Totò)
Re: Piccioni viaggiatori
Va beh... direi che più o meno ci dovremmo essere.
La mia soluzione è $floor(n^2/2)-1$... può essere scritta anche come l(n) = l(n-1)+n-1+(n-1 mod 2), per ogni n>2.
La mia soluzione è $floor(n^2/2)-1$... può essere scritta anche come l(n) = l(n-1)+n-1+(n-1 mod 2), per ogni n>2.
Re: Piccioni viaggiatori
si, è uguale: MOD(n,2) = (n mod 2) e se:
n=n+1, dalla tua si passa alla mia; la tua funzione però è più pratica essendo solo funzione di n (FLOOR = INT giusto?)
n=n+1, dalla tua si passa alla mia; la tua funzione però è più pratica essendo solo funzione di n (FLOOR = INT giusto?)
Ultima modifica di Pasquale il ven gen 10, 2014 11:41 pm, modificato 1 volta in totale.
_________________
$\text { }$ciao ciao
E' la somma che fa il totale (Totò)
$\text { }$ciao ciao
E' la somma che fa il totale (Totò)
Re: Piccioni viaggiatori
Sì, infatti.
Con "Floor" indico l'operatore "arrotonda all'intero precedente" (esempio, Floor(4)=4 e Floor(3.98=3)).
Con "Floor" indico l'operatore "arrotonda all'intero precedente" (esempio, Floor(4)=4 e Floor(3.98=3)).