Homework 6 - Nelle ore di Filosofia (o Diritto...)

Vedi anche: DomandeHomework6, SoluzioneHomework6, RisultatiHomework6.



Tutti gli studenti delle superiori, annoiandosi a morte durante lunghe spiegazioni, hanno almeno una volta preso un foglio a quadretti, disegnato un quadrato (di norma 10x10) e hanno cominciato a riempirlo di numeretti, 1, 2, 3 e cosi' via, sperando almeno una volta di arrivare a 100 (a questo ci sono arrivati solo pochi fortunati... o qualche genietto), seguendo la seguente regola: ci si puo' spostare in orizzontale o verticale lasciando libere due caselle e in diagonale lasciando libera una casella. Eccovi un esempio (fortunato, o abile!) di un quadrato 5x5.

  1 16  6 23 13
  8 21  3  9 20
  5 24 12 17 25
  2 15  7 22 14
 11 18  4 10 19

Ora pero' siete all'Universita' e state studiando Informatica... perche' non scrivere un programma che fa questo sporco lavoro per voi, cosi' potrete seguire le lezioni di Programmazione 1 a mente sgombra, senza chiedervi quale sia la strategia migliore per riempire quel maledetto quadrato!

Si tratta di costruire un programma che legge un input un intero n e cerca di riempire il quadrato n x n seguendo la regola sopra descritta. La strategia da utilizzare va sotto il nome di backtrack: semplicemente si comincia a mettere il numero 1 in una posizione arbitraria e poi il 2 e cosi' via. Quando ci si accorge che non si puo' andare avanti (e non si e' raggiunta una soluzione), si torna all'ultimo punto in cui avevate una scelta per fare l'ultima mossa e si prova con la mossa successiva (SUGGERIMENTO: date un ordine alle 8 possibili mosse).

La struttura generale delle procedure di backtrack, puo' essere vista nel programma che risolve il problema delle 8 regine (visto a lezione e riportato qui sotto nella pagina: a voi interessa la procedura

tenta(int, int [])
).

Il quadrato 5x5 mostrato sopra e' stato ottenuto con un programmino. Per avere un'intuizione di come funziona il backtrack, sotto potete trovare la sequenza di punti in cui il programma ha dovuto tornare indietro, perche' aveva imboccato una strada che non portava alla soluzione (ATTENZIONE: il vostro output dovra' generare SOLO la matrice con la soluzione migliore trovata).

Per valori sufficienti bassi (ad esempio 4) il problema non ha soluzione: in questo caso il vostro programma dovra' fornire in output la migliore soluzione trovata, cioe' la matrice con la sequenza piu' lunga. (Nel caso di un quadrato 4x4 si puo' arrivare a infilare 8 numeri nella matrice... come si fa?).

Evitate di provare per valori troppo alti... gia' 10 potrebbe impegnare il vostro computer per ore...

Se il vostro programma e' strutturato bene, una semplice modifica (cambiare la procedura che sceglie la prossima mossa da fare) potrebbe permettervi di risolve un altro celeberrimo gioco legato al mondo degli scacchi: passare su tutte le caselle di una scacchiera una sola volta muovendosi come un cavallo...

Scadenza

L'esercizio va consegnato entro la mezzanotte di domenica 21 Dicembre .

Consegna degli esercizi

  • Attenzione: viste numerose richieste, ho deciso di prorogare la scadenza dell'homework 4 a mercoledì 22 dicembre sempre alle 23:59.
  • La scadenza dell'Homework 5 è stata (ri)fissatta per venerdì 14 gennaio 2005 sempre alle 23:59.
  • Dovete essere iscritti a twiki
  • Dovete aver mostrato un documento di identità a Ivano Salvo (oppure mandatemene una scansione per email)
  • Vi devo aver abilitato (controllate in StudentiProg1Group o ArchitettureUnoGroup )
  • Gli esercizi vanno consegnati esclusivamente usando la pagina di consegna: ATTENZIONE in questo momento sono attive due pagine, una per l'homework 4 e una per l'homework 5.
Evitate di fare confusione!

    • Io registro/abilito nuovi iscritti e aggiorno password solo fino al venerdì sera
    • quindi fate una prova durante la settimana per controllare che tutto vi funzioni!
  • Non verranno accettati esercizi consegnati per email
  • Ora sono le 19:52

-- IvanoSalvo - 12 Dic 2003

Topic attachments
I AttachmentSorted descending History Action Size Date Who Comment
C source code filec ottoReg.c r2 r1 manage 3.2 K 2003-12-11 - 18:04 IvanoSalvo  
Texttxt Esempio.Bactrack.txt r1 manage 0.5 K 2003-12-11 - 18:03 IvanoSalvo  
Edit | Attach | Watch | Print version | History: r6 < r5 < r4 < r3 < r2 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r6 - 2003-12-30 - AndreaSterbini






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback