Roba da informatici

Altro che rompicapi, questo è un problemino mica male.

Ve lo traduco alla buona come ne sono capace, prendendolo dal famoso sito Progetto Eulero, di cui ho parlato in un post precedente.

Sia T(n) il numero dei possibili percorsi in una scacchiera 4 x n che soddisfano le seguenti regole:

  1. Il percorso inizia sempre dalla casella in alto a sinistra
  2. Le mosse possono essere: su, giù, sinistra, destra di una casella
  3. Il percorso deve passare per tutte le caselle una sola volta
  4. Il percorso termina nella casella in fondo a sinistra

Sapendo che T(10) è 2329, quanto sarà T(100)?

Ho semplificato la richiesta per ragioni didattiche e altre ragioni (di cui diremo).

Il problema ha, ovviamente, interessanti risvolti matematici ma anche (forse di più) interesse informatico. In effetti deve essere possibile scrivere un prgrammino che risolve il problema.

Riporto il diagramma di esempio allegato al problema (speriamo che non abbia copyright). Il diagramma si riferisce ad un possibile percorso in una scacchiera 4×10.

Ricchi premi per i risolutori (che inviano anche la descrizione di come ci sono arrivati).

Esempio di percorso 4x10

Esempio di percorso 4x10

Advertisements
Questa voce è stata pubblicata in Algoritmi, Induzione, Informatica, Matematica e contrassegnata con , , , . Contrassegna il permalink.

2 risposte a Roba da informatici

  1. MenArosto ha detto:

    Figo sto blog!
    Stavo giusto cercando in rete informazioni sugli algortmi ricorsivi di backtracking e fatalità sono finito da queste parti. Sicuramente la crescita avverà in maniera esponenziale: se per un T(10) abbiamo 2329 percorsi, non voglio pensare a quanti saranno per un T(100).
    Sarebbe già interessante riuscire a relizzare un algoritmo che trova un possibile percorso, ma il problema vero qui è trovarli tutti al variare delle colonne della matrice.
    Comunque credo che per aver proposto un problema simile, un’ideauccia Bobcarr se la deve essere fatta. Qualche suggerimento di partenza da parte sua? A presto

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...