Domande Homework 6 - Ore di Filosofia - backtrack

• Inserite le vostre domande usando la form in fondo alla pagina
• Vedi anche HomeWork6, SoluzioneHomework6, RisultatiHomework6.

---

---

2 Domande

1-Noi oltre alle varie funzioni in stile "8regine" dobbiamo anke farne una ricorsiva, per così dire "principale", in modo tale ke venga stampata alla fine solo la mossa finale?

2-Nel programma delle 8regine definiamo le colonne della matrice e poi giustamente la mettiamo come argomento delle varie funzioni. Ma qui come facciamo se nn sappiamo a priori quanto è grande la matrice, ovvero quante colonne ha? Se nella funzione metto "m[][]" mi da errore alla compilazione.

-- Comment added by DavidVulpetti on 12 Dec 2003

---

Inizio della ricerca e Output

Mi chiedevo se l'1 dovesse andare per forza nell'angolo in alto a sinistra o se potesse essere messo in un qualsiasi punto della matrice. In altre parole, dobbiamo considerare anche il fatto che l'1 possa cominciare in un punto arbitrario o lo si puo' far partire sempre dall'angolo superiore sinistro?

Inoltre io sono riuscito ad ottenere una matrice funzionante di 5x5, tuttavia è diversa da quella riportata nel testo dell'esercizio, quindi presumo che sia possibile ottenere una matrice completa in più modi differenti. Immagino che ogni "variazione sul tema" sia buona, giusto?

Ultima cosa: Nel testo dell'esercizio si dice che in una matrice 4x4 è possibile infilare 8 numeri, il mio codice ne trova solo 5, questo fatto è perchè il codice è sbagliato o il motivo risiede nella prima domanda che ho fatto? (ovvero in questo caso l'1 non deve partire dall'angolo superiore sinistro)

-- Comment added by StefanoNoffke on 13 Dec 2003

---

Gestione errori

Bisogna controllare in qualche modo l'input che legge la dimensione dellla matrice nxn? tipo non accettare valori negativi o sotto un certo numero (tipo n deve essere maggiore di 0)

-- Comment added by StefanoNoffke on 13 Dec 2003

---

Re: Gestione errori

Non gestite errori, viene letto un solo numero intero (la dimensione del lato quadrato)

Re: 2 Domande

1) non ho capito la domanda

2) Per indirizzare una matrice di cui non si conoscono le dimensioni si può usare un vettore di N^2 elementi e calcolare la posizione dell'elemento (x,y) calcolando l'indice (y*lato---+x).

Re: Inizio della ricerca e Output

Se leggi attentamente l'esercizio vedrai che c'e' scritto "si comincia da una posizione arbitraria"

Una qualsiasi matrice va bene.

-- Comment added by AndreaSterbini on 13 Dec 2003

---

Il vettore

Allora è necessario un vettore dinamico per gestire il campo. Come lo dichiaro se N lo prendo da tastiera? Non esiste allo stesso modo la possibilità di lavorare direttamente su una matrice dinamica?

-- Comment added by JacopoBusso on 15 Dec 2003

---

Non mi dica che la soluzione è usare una lista con i valori di ciascuna posizione perchè mi sembra sprecata una lista per una cosa del genere!

-- Comment added by JacopoBusso on 15 Dec 2003

---

Matrice

Come si fa a definire una matrice n x n dopo aver letto da input il valore di n? il compilatore mi dice che non si puo fare...

-- Comment added by MorenoDeVincenzi on 15 Dec 2003

---

Re: Il vettore

Lo dichiari come puntatore al tipo dell'elemento e usi malloc per allocarlo.

Re: Matrice

Vedi sopra (allocate un vettore di N^2 elementi)

-- Comment added by AndreaSterbini on 15 Dec 2003

---

Matrice

Scusi la persistenza. Ma lo stesso problema si crea quando vado ad inizializzare il vettore, n non e' ancora conosciuto.

-- Comment added by MorenoDeVincenzi on 15 Dec 2003

---

Output

l'output e' la stampa della matrice ma c'e' anche una newline sotto ad essa o no?

-- Comment added by MorenoDeVincenzi on 15 Dec 2003

---

Vari casi

Volevo chiedere se il comportamento con gli input
0, 1, 2, 3 è il seguente:

input 0: esco

input 1: stampo 1
    esco

input 2: stampo 1 0 (per esempio)
      0 0
    esco

input 3: stampo 0 0 1 (per esempio)
      0 0 0
      2 0 0
    esco

Volevo chiedere se devo ottimizzare il prog. se:

input>=7: non sono riuscito a controllare
     il funzionamento del programma
     perchè ci mette troppo a trovare la
     soluzione

Volevo far notare che:

input 4: si riescono a mettere 8 numeri solo
    se il primo viene messo in una posizione
    opportuna;
    credo quindi che la posizione di default
    migliore da scegliere sia una di quelle
    che vanno bene per l'input 4;

-- Comment added by EmanueleQuattrini on 15 Dec 2003

---

Output giusto

Il testo dell'esercizio dice che dobbiamo stampare la soluzione milgiore trovata, significa che in caso di riempimento completo del quadrato dobbiamo stampare obbligatoriamente una delle almeno 4 soluzioni in cui stono stati impiegati meno tentativi? o possiamo anche stamparne una qualunque basta che sia una soluzione

Grazie

-- Comment added by AlessioDiMauro on 16 Dec 2003

---

Re: Output giusto

basta stamparne una (chi ti tice che sono solo 4?)

Re: Output

stampa la matrice seguita da newline (e come senno'?)

Re: Matrice

Come ho detto prima, per allocare una matrice o vettore di dimensioni variabili si usa malloc.

-- Comment added by AndreaSterbini on 16 Dec 2003

---

Posizione iniziale

la prima cifra deve essere posizionata in modo arbitrario. giusto? ma arbitrariamente per me, cioe' io scelgo dove posizionarla? o devo usare una funzione random per posizionare "a caso" la prima cifra?

-- Comment added by MicheleFacecchia on 17 Dec 2003

---

Re: Posizione iniziale

Dovete cercare la posizione di partenza che vi dà il percorso che inserisce più valori.

Per cercare il numero massimo di valori inseriti bisogna alla peggio esaminare le posizioni che si trovano in uno degli 8 ottanti (dividete la matrice in 8 spicchi) della matrice. Quindi alla peggio N*N/8 (più le caselle sul bordo dello spicchio).

E' possibile ridurre il numero di caselle da cui partire in questo modo per ragioni di simmetria (è possibile ribaltare la matrice in 3 modi, lungo le 2 mediane e lungo una diagonale).

-- Comment added by AndreaSterbini on 17 Dec 2003

---

Esempio di caselle da esaminare

X	X	X
	X	X
		X

-- Comment added by AndreaSterbini on 17 Dec 2003

---

Non ho capito

Potrebbe rispiegare questo punto, non mi è stato molto chiaro. Cosa sono gli ottanti? Ma questa cosa va applicata sempre o solo per i valori inferiori uguali a quattro? Che significa esaminare? Ho il mal di testa

-- Comment added by JacopoBusso on 17 Dec 2003

---

Aspetti forse ho capito ma che il prog deve fare i tentativi partendo da tutte le caselle dello spicchio e stampare il caso migliore?!? E' così? Qualcuno ha moment!

-- Comment added by JacopoBusso on 17 Dec 2003

---

Flash MOB

Andate alla pagine FlashMob per sapere cos'è!!! Ps: Scusatemi tanto per OFF - TOPIC

-- Comment added by MatteoLaBella on 17 Dec 2003

---

Re: Non ho capito

Invece hai capito benissimo.

Re: Flash MOB

Peccato, a quell'ora sono a cena con amici.

-- Comment added by AndreaSterbini on 18 Dec 2003

---

Re: Flash Mob

Professore non si preoccupi appena posso gli racconto com'è andata....!!!

-- Comment added by MatteoLaBella on 18 Dec 2003

---

Non ho capito

La mia mente si rifiutava di capire

-- Comment added by JacopoBusso on 18 Dec 2003

---

Segmentation fault

Il dev-C---++ mi da un errore di segmentazione a questa riga: campo[j*n---+k] dove: campo è il vettore dinamico che funziona da matrice j e k contatori di riga e colonna. ho inserito l'istruzione in due cicli annidati per inizializzarla a 0 Non so se l'errore dipende da questo o da come ho inizializzato il vettore. Il vettore lo ho allocato con la malloc ed è della dimensione di lato*lato. A me questo sembra giusto ma non capisco perchè mi da errore quando sul mio fido IDE della Borland va tutto bene :(.

-- Comment added by JacopoBusso on 18 Dec 2003

---

Ci risiamo, segmentation fault

Penso che debba portare a Lourdes il mio pc. Ho scoperto che è un problema intermittente (prima funzionava, ora ricompilo - ovvio che non ho modificato il codice, ho solo aggiunto i commenti - ora no). E' solo uno sfogo...

-- Comment added by DanieleBernardi on 18 Dec 2003

---

FlashMob

Per la gioia del Prof. che non so se era una presa in giro, ho aggiornato la pagina dei FlashMob Quindi se volete fateci un salto

-- Comment added by MatteoLaBella on 18 Dec 2003

---

Re:Re:Output giusto

infatti ho detto una delle almeno 4 non una delle 4

volevo sapere però l'output va formattato in qualche maniera (oltre ovviamente a stampare un accapo alla fine di ogni riga) bisogna stampare uno spazio tra una colonna e l'altra o bisogna mettere il numero in un campo di ad esempio 3 caratteri?

grazie

-- Comment added by AlessioDiMauro on 18 Dec 2003

---

Re: Segmentation fault

le dimensioni corrette del blocco di memoria da allocare sono lato*lato*sizeof(int)

Re: Output giusto

Fate come nell'esempio in HomeWork6 .

-- Comment added by AndreaSterbini on 19 Dec 2003

---

Segmentation fault

Niente anche con la definizione lato*lato*sizeof(int) mi da sempre lo stesso subdolo errore, non so dove sia l'errore! Non riuscirò a consegnarlo corretto purtroppo se mi da quell'errore, però sono incavoltato perchè il resto funziona (non ho ancora fatto il sistema per trovare la migliore soluzione ma è inutile che ci provo se non risolvo il segmentation fault)

-- Comment added by JacopoBusso on 19 Dec 2003

---

E' corretto indirizzare il puntatore ad int come un vettore?
In altre parole è lecito parlare di campo[j*n---+k]=0 dove 'campo' è il puntatore? Se non è li l'errore non so dove cercarlo

-- Comment added by JacopoBusso on 19 Dec 2003

---

Re: segmentation fault

I vettori (arrays) sono a tutti gli effetti dei puntatori, per cui per creare un vettore ci sono 2 modi: se sai la dimensione a priori puoi inisizlizzare

int vettore[DIMENSIONE];

altrimenti dichiari un puntatore al tipo di dati interessato (int in questo caso), e una volta che sai la dimensione inizializzi lo spazio con malloc in questo modo

int * vettore; vettore = malloc(sizeof(int)*dimensione);

stesso discorso vale con le matrici multidimensionali, con i dovuti accorgimenti...

-- Comment added by StefanoNoffke on 19 Dec 2003

---

Output Matrice

Quindi in sostanza l'output della matrice deve essere una matrice n*n con ogni intero scritto in uno spazio di 3 caratteri (in sostanza nella forma cc1cc2cc3cc4) dove c e' uno spazio?

-- Comment added by StefanoGiachetti on 19 Dec 2003

---

I/O

da quello che mi sembra di capire l'input lo riceviamo dall'utente e l'output deve essere come quello nell'esempio, pero' nn mi e' chiaro quanti spazi bisogna mettere tra l'input e la matrice. io ho fatto una cosa del genere

input (\n) [matrice] (\n)

va bene? boh adios ocram

-- Comment added by MarcoValerioBarbera on 20 Dec 2003

---

Ancora seg fault

Grazie Stefano, ho fatto proprio così ma quando vado ad indirizzare il puntatore il debugger mi da l'errore. è davvero strano comunque ci passerò le notti insonni finchè non risolvo

-- Comment added by JacopoBusso on 20 Dec 2003

---

E' corretto il casting per forzare il tipo int al puntatore, che di norma è void, restituito dalla malloc? Ho fatto così: int* campo;
campo=(int*)malloc (sizeof(int)*lato*lato);

io credo di sì.

-- Comment added by JacopoBusso on 20 Dec 2003

---

Ok risolto

Il problema era del debugger non del programma! non so perchè il debugger del dev-c---++ (o per lo meno il mio!) quando si inseriscono valori dalla tastiera invece di considerare quelli genera a caso un numero siderale che chiaramente non poteva essere adatto per costruire un vettore. Me ne sono accorto solo ora perchè davo per scontato che il valore che prendeva era corretto, ma poi per puro scrupolo ho controllato ed era quello. Possibile?

-- Comment added by JacopoBusso on 20 Dec 2003

---

Posizione iniziale

Per quanto riguarda il sistema con la la migliore soluzione bisogna adottarlo sempre oppure solo per le matrici di piccole dimensioni (ad esempio con lato pari a 3 o 4).

-- Comment added by JacopoBusso on 20 Dec 2003

---

9 o piu' colonne

ho finito il programma, funziona tutto alla perfezione (credo) fino a quando uso matrici 8*8, (ci mette al massimo una manciata di secondi), ma appena do un valore leggermente piu' alto (anche solo 9) il programma si blocca (probabilmente per via dei numerosi calcoli che deve fare), la cosa pero' mi "puzza" un po' nel senso che io mi aspettavo un'aumento graduale del tempo di esecuzione, mentre invece tra 8*8 e 9*9 c'e' una distanza abissale (quest'ultimo l'ho runnato due ore fa e ancora nn ha finito.. :P), colpa delle funzioni esponenziali o del fatto che ho creato un codice che fa troppe cose inutili? mi piacerebbe sapere se a voi succede la stessa cosa... adios ocram

-- Comment added by MarcoValerioBarbera on 20 Dec 2003

---

ceil()

Possiamo usare la ceil() della libreria math.h?

-- Comment added by JacopoBusso on 20 Dec 2003

---

Re: 9 o più colonne

Io comincio ad avere problemi da 10 colonne in su, ma questo dipende molto dal tipo di processore che si ha. ad ogni modo l'aumento di calcoli che deve fare è esponenziale (ad un fattore molto elevato) per cui già da valori di n di 8 la differenza di 1 si fa sentire parecchio...

-- Comment added by StefanoNoffke on 20 Dec 2003

---

Re: ceil()

Sì

-- Comment added by AndreaSterbini on 20 Dec 2003

---

liste di adiacenza

scusate x la domanda forse stupida... Ma si devono usare le liste di adiacenza?

-- Comment added by MarcoGrechi on 20 Dec 2003

---

alberi ( o liste di adiacenza? )

riprendendo la domanda sulle liste di adiacenza, non e meglio usare gli alberi?

-- Comment added by RiccardoManni on 20 Dec 2003

---

Re: liste di adiacenza

dovete simulare i tre pioli ... che si comportano esattamente come una stack (pila) ... quindi conviene usare ... (indovinate).

-- Comment added by AndreaSterbini on 21 Dec 2003

---

Pioli ?

Scusi Prof., forse mi sono perso qualcosa, ma che c'entrano i 3 pioli ? Intende per immagazzinare i dati del filo d'arianna della badtrack ? In questo caso non basta tenerne uno, intendo quello che di volta in volta risulta maggiore come numero di elementi tra il tentativo appena compiuto ed un eventuale precedente ?

-- Comment added by LucaMarozzini on 21 Dec 2003

---

output

per quanto riguarda l'output volevo sapere se dopo aver stampato la soluzione sotto la matrice c'e' bisogno di un invio. grazie

-- Comment added by MorenoDeVincenzi on 21 Dec 2003

---

Funzionamento

E' possibile che per trovare la soluzione per la matrice 5x5 il mio prog. impieghi diversi minuti????

-- Comment added by MorenoDeVincenzi on 21 Dec 2003

---

Strano

Il computer con 9 come lato non mi trova soluzioni(almeno in tempi possibili), mentre per 10 ci mette veramente poco. Qualcuno sa il perchè?

-- Comment added by JacopoBusso on 21 Dec 2003

---

Mi corrego trova soluzione ma ci mette un po' (circa 15 min). Professore quando corregerà i compiti quanto tempo puo impiegare al massimo il pc per una ricerca prima che voi interrompiate l'esecuzione? Quale numero al massimo inserirà?

-- Comment added by JacopoBusso on 21 Dec 2003

---

Sigh

Stavolta non c'è la faccio proprio a consegnare, e dire che gli stack li avevo usati già per la torre di Hanoi... Ma non è detto l'ultimo invio

-- Comment added by LucaMarozzini on 21 Dec 2003

---

Forse è un po' tardi...

per finire il prog e consegnare ma tentare non nuoce. Volevo sapere se è possibile passare un array di struct bidimensionale ad una funzione... sto impazzendo con i segmentation fault...

-- Comment added by RiccardoManni on 21 Dec 2003

---

Re: Pioli?

accidenti ... ero rimasto alle torri di Hanoi ... che scemo!

-- Comment added by AndreaSterbini on 22 Dec 2003

No such template def TMPL:DEF{PROMPT:before}

• Ricordatevi di dare un titolo alla vostra domanda come segue:

<tre spazi>---+++<spazio>Titolo della domanda   "non dovete mettere <>" 
Testo della domanda