[c] aiuto algoritmo per neofita

[fsdfdsddijsdfsdfo]

Salve, sono un giovane studente di matematica alle prese con il C (avrò una 40ina di ore di laboratorio alle spalle, quindi pochissimo).


Vi spiego subito qual'è il mio obbiettivo.

Vorrei un programma che risolve un particolare gioco.

Quale gioco direte voi?
Consiste nel prendere una matrice 10*10. Mettere 1 nella prima casella v[0][0] e mettere la cifra successiva in una casella cosi scelta: o spostata di tre lungo le 4 direzioni cardinali, o spostata di due lungo le diagonali.
L'obbiettivo è, senza uscire mai dai bordi, riempire la matrice con 100 numeri.


Non ho la piu pallida idea di come fare.
Mi conviene indicizzare 100! matrici con tutte le combinazioni possibili? e poi verificare quali siano le matrici coerenti?

Oppure con una struttura ad albero provare tutte le combinazioni coerenti, andando avanti passo per passo e tornando indietro quando si arriva ad un assurdo?


Non ho nessuna idea su come implementare alcuno dei due modi.

Consigli?

[Isomarcus]

ma non ho capito, è il programma che decide dove mettere il numero successivo, oppure lui mette il primo numero e poi tu decidi in che direzione andare per piazzare il secondo?

[fsdfdsddijsdfsdfo]

Originariamente inviato da Isomarcus

ma non ho capito, è il programma che decide dove mettere il numero successivo, oppure lui mette il primo numero e poi tu decidi in che direzione andare per piazzare il secondo?

il programma deve trovare la soluzione al gioco.

Il primo numero è standard, cioè 1 in v[0][0] (uso la notazione C cosi è chiaro per tutti).

Partendo da qui, il programma deve trovare ALMENO un cammino (o forse tutti?) che riempa tutta la matrice fino a 100.

Capisci bene che non è banale trovare una soluzione, se prendete carta e penna vi accorgerete di quanto è difficile.

io personalmente in 6 mesi sono riuscito ad arrivare a 96.

Nota bene: Non voglio che mi scriviate il programma (anche se non mi darebbe fastidio ) ma vorrei qualche indirizzo su come muovermi.

[fsdfdsddijsdfsdfo]

io ho provato a buttare giu un paio di righe di codice. Ma a quanto pare non funziona.

Ho inserito i commenti sui pezzi. Ho compilato con

gcc -Wall -pedantic -lm

provate a darci un occhiata. grazie

definizione: una matrice è coerente quando rispetta le regole del gioco.

#include <stdio.h>
#include <time.h>
#include <unistd.h>
#include <stdlib.h>
#include <math.h>


int main () {
	
	int m[10][10], i, j, k, n, z, d;
	
	
	
	
	for(;;) {
              
                srand((unsigned)time(NULL));
	
		for(i=0; i<100; i++)	{
			m[i/10][i%10]=rand()%100+1;
		} //inizializzo una matrice con numeri casuali
	
	
		m[0][0]=1;


		for(n=100; n!=1; n--) {
			
			for(k=100; k!=0 ; k--) {
				if (m[k/10][k%10] == n) break;
			}
			
			
			for(z=100; z!=0 ; z--) {
				if (m[z/10][z%10] == n-1) break;
			}
			
			d=sqrt( (z/10 - k/10)*(z/10 - k/10) + (z%10 - k%10)*(z%10 - k%10) );
			
			// per ogni elemento cerco il suo elemento -1. Se la distanza tra 
loro è due vuol dire che o è spostato di due sugli assi cardinali, o è spostato di 
due sulla diagonale. In pratica verifico che la matrice sia coerente. 
Tecnicamente siccome d è intero dovrebbe buttare la parte decimale della
 radice no?
			
			if (d!=2) break;
			
			// esco dal ciclo for se la matrice non è coerente
		
		}
		
		if (n==1) break;
		
		//se la matrice è coerente per tutti i numeri da 1 a 100 allora mi fermo 
 e stampo. A quanto pare non termina mai e va in loop, probabilmente la 
matrice non potrà mai essere coerente secondo le regole da riga 25 a riga 40, 
probabilmente perchè c'è qualche variabile con un uno di troppo (off-by-one).
		
	}
	
	for (i=0; i<10;i++) {
		for(j=0; j<10; j++) {
			if ( m[i][j] < 10) printf(" %d ", m[i][j]); 
			else printf("%d ", m[i][j]);
		}
		printf("\n");
	}
	



return 0;
}

[fsdfdsddijsdfsdfo]

già non è per nulla banale


credo che il codice che ho scritto non sia sbagliato concettualmente, ma di sicuro ho alcuni problemi:


a) Come faccio a inizializzare casualmente una matrice con 100 numeri da 1 a 100 tutti DIVERSI tra loro?


b) come faccio a passare ad una funzione i RIFERIMENTI (cioè che modifico l'originale e non una copia) ad una matrice 10*10?

[fsdfdsddijsdfsdfo]

incredibile ma lol!

avevo sentito parlare del debugger... mi sono scaricato una guida e ho iniziato ad usarlo...
fighissimo!

gli ho fatto fare un paio di cicli...

sembra funzioni ma sia troppo lento

mi serve proprio qualcosa che mi dia 100 numeri DIVERSI! :

[trallallero]

Originariamente inviato da dijo

mi serve proprio qualcosa che mi dia 100 numeri DIVERSI! :

per i numeri causali:

#include <stdlib.h>
#include <sys/types.h>
#include <unistd.h>

...
   srand(getpid());  // INIZIALIZZA IL GENERATORE DI NUMERI

   for ( y = 0; y < 100; y++ )
      for ( x = 0; x < 100; x++ )
         v[y][x] = rand();
...

EDIT: scusa non avevo capito ... tu vuoi 100 numeri casuali ma diversi ?
quindi 100 numeri da 0 a 99 ma in ordine casuale ?

[fsdfdsddijsdfsdfo]

Originariamente inviato da trallallero

per i numeri causali:

#include <stdlib.h>
#include <sys/types.h>
#include <unistd.h>

...
   srand(getpid());  // INIZIALIZZA IL GENERATORE DI NUMERI

   for ( y = 0; y < 10; y++ )
      for ( x = 0; x < 10; x++ )
         v[y][x] = rand();
...

EDIT: scusa non avevo capito ... tu vuoi 100 numeri casuali ma diversi ?
quindi 100 numeri da 0 a 99 ma in ordine casuale ?

esatto

solo non da 0 a 99 ma da 1 a 100. E che nella prima casella(m[0][0]) ci sia 1.

già che ci sei mi spieghi come passare un riferimento a matrice ad una funzione? grazie

[andbin]

Originariamente inviato da dijo

a) Come faccio a inizializzare casualmente una matrice con 100 numeri da 1 a 100 tutti DIVERSI tra loro?

Questo non sarebbe comunque un grosso problema, è abbastanza semplice, potrei pure postare del codice.

Piuttosto .... sei sicuro che sia la strada giusta??? Cioè tu generi la matrice in modo casuale e poi dopo verifichi se rispetta certe specifiche o condizioni, è così??

Personalmente vorrei capire meglio quali sono queste specifiche.

Originariamente inviato da dijo

b) come faccio a passare ad una funzione i RIFERIMENTI (cioè che modifico l'originale e non una copia) ad una matrice 10*10?

In "C" (e C++) un array viene passato ad una funzione sempre per riferimento (viene passato l'indirizzo del primo elemento).

[trallallero]

Originariamente inviato da dijo

esatto

solo non da 0 a 99 ma da 1 a 100. E che nella prima casella(m[0][0]) ci sia 1.

già che ci sei mi spieghi come passare un riferimento a matrice ad una funzione? grazie

dammi un attimo di tempo che ho anche fare un lavoro (al lavoro si fa anche questo)

[cionci]

Io ti consiglierei di usare un algoritmo greedy: http://it.wikipedia.org/wiki/Algoritmo_greedy

[trallallero]

Allora, prova ad arrivarci da solo. Anzi magari ti viene un'idea migliore della mia

io farei un array intero di 100 inizializzato a 0.
Ottieni un numero causale, scorri l'array di 100, se il numero non c'é lo inserisci nell'array e lo aggiungi alla matrice altrimenti ottieni un altro random.
Non é molto performante ma é molto semplice

[andbin]

Ecco come riempire una matrice 10x10 con numeri unici da 1 a 100 (in cui la cella [0,0] sia sempre 1):

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int rand_int (int min, int max)
{
    double d;

    d = rand () / (RAND_MAX+1.0);
    return ((int) (d * (max-min+1))) + min;
}

void rand_matrice (int m[10][10])
{
    int numeri[100], i, j, idx, n;

    for (i = 0; i < 100; i++)
        numeri[i] = i+1;

    n = 99;

    for (i = 0; i < 10; i++)
    {
        for (j = 0; j < 10; j++)
        {
            if (i == 0 && j == 0)
                idx = 0;
            else
                idx = rand_int (0, n);

            m[i][j] = numeri[idx];
            numeri[idx] = numeri[n--];
        }
    }
}

void stampa_matrice (int m[10][10])
{
    int i, j;

    for (i = 0; i < 10; i++)
    {
        for (j = 0; j < 10; j++)
            printf ("%3d ", m[i][j]);

        printf ("\n");
    }
}

int main (void)
{
    int m[10][10];

    srand ((unsigned int) time (NULL));

    rand_matrice (m);

    stampa_matrice (m);

    return 0;
}

[trallallero]

Originariamente inviato da dijo

già che ci sei mi spieghi come passare un riferimento a matrice ad una funzione? grazie

puoi fare una funzione del genere:

void Funz( int mat[10][10], int y, int x, int Val )
{
   ...
   mat[y][x] = Val;
   ...
}

passi per riferimento ma specifichi anche le dimensioni della matrice

EDIT: scusa chiedevi come passare (sono sempre piú stordito)
in questo caso passi semplicemente il nome:

int Mat[10][10];
...
Funz( Mat, 9, 9, 6 );

[repne scasb]

Originariamente inviato da dijo

Mi conviene indicizzare 100! matrici con tutte le combinazioni possibili? e poi verificare quali siano le matrici coerenti?

Le matrici da analizzare secondo il tuo modello sono:

"933262154439441526816992388562667004907159682643816214685929638952175999932299\
156089414639761565182862536979208272237582511852109168640000000000000000000000\
00"

Oltretutto una volta generate, dovresti verificarle una per una fino a trovarne una che rispetti le condizioni del gioco....

[Ziosilvio]

Originariamente inviato da dijo

prendere una matrice 10*10. Mettere 1 nella prima casella v[0][0] e mettere la cifra successiva in una casella cosi scelta: o spostata di due lungo le 4 direzioni cardinali, o spostata di uno lungo le diagonali.
L'obbiettivo è, senza uscire mai dai bordi, riempire la matrice con 100 numeri.

C'è qualcosa che non mi quadra.

Immagina la tua matrice come se fosse una scacchiera.
Se ti muovi di due unità in su, in giù, a destra, o a sinistra, passi da una casella a un'altra casella dello stesso colore.
Se ti muovi in diagonale, passi da una casella a un'altra casella dello stesso colore.

Allora, se ti muovi come dici tu, potrai riempire o tutte le caselle bianche, o tutte le caselle nere; ma non tutte le caselle, cosa che invece è chiesta dall'esercizio.

Dove sbaglio?

[trallallero]

vabbé, ti posto anche la mia versione. Non é ordinata in funzioni come quella di andbin ma almeno hai un paio di esempi

int main()
{
   int Mat[10][10];
   int Vet[100];
   int x, y, i, Count;

   srand( getpid() );

   memset( Mat, 0, sizeof(Mat) );
   memset( Vet, 0, sizeof(Vet) );

   // INIZIALIZZA LA MATRICE DA 10 x 10
   for ( y = 0; y < 10; y++ )
      for ( x = 0; x < 10; x++ )
      {
         while(1)
         {
            int R = rand() % 100 + 1;

            for( i = 0; i < Count; i++ )
               if ( Vet[i] == R )
                  break; // IL NUMERO C'E' GIA'

            if ( Vet[i] == R )
               continue; // RICOMINCIA IL while(1)
         
            Mat[y][x] = Vet[Count++] = R;
            break; // OK IL NUOVO NUMERO E' INSERITO
         }
      }

   // STAMPA LA MATRICE
   for ( y = 0; y < 10; y++, putchar('\n') )
      for ( x = 0; x < 10; x++ )
         printf( "%3i", Mat[y][x] );
   
   return 0;
}

[trallallero]

Originariamente inviato da Ziosilvio

C'è qualcosa che non mi quadra.

Immagina la tua matrice come se fosse una scacchiera.
Se ti muovi di due unità in su, in giù, a destra, o a sinistra, passi da una casella a un'altra casella dello stesso colore.
Se ti muovi in diagonale, passi da una casella a un'altra casella dello stesso colore.

Allora, se ti muovi come dici tu, potrai riempire o tutte le caselle bianche, o tutte le caselle nere; ma non tutte le caselle, cosa che invece è chiesta dall'esercizio.

Dove sbaglio?

mi sembra di averlo giá sentito questo gioco. Ti devi muovere ripettando le regole postate da dijo, é un solitario non ci sono caselle nere o bianche

[Ziosilvio]

Originariamente inviato da trallallero

mi sembra di averlo giá sentito questo gioco. Ti devi muovere ripettando le regole postate da dijo, é un solitario non ci sono caselle nere o bianche

Allora te lo dico in un altro modo.

Considera la somma delle coordinare della casella della matrice.

Se ti muovi di 2 in su o in giù, cambi di 2 il valore dell'ordinata e lasci intatto quello dell'ascissa; quindi, se la somma dell'ascissa e dell'ordinata era pari, rimane pari, e se era dispari, rimane dispari.
Se ti muovi di 2 a destra o a sinistra, cambi di 2 il valore dell'ascissa e lasci intatto quello dell'ordinata; quindi, se la somma dell'ascissa e dell'ordinata era pari, rimane pari, e se era dispari, rimane dispari.
Se ti muovi di 1 in diagonale, cambi di 1 sia l'ascissa che l'ordinata; quindi, se la somma dell'ascissa e dell'ordinata era pari, rimane pari, e se era dispari, rimane dispari.

Ma allora, muovendosi così, puoi andare solo sulle caselle in cui la somma dell'ascissa e dell'ordinata ha la stessa parità che in quella di partenza: e questo copre solo metà della matrice.

Di nuovo: dove sbaglio?

[repne scasb]

Originariamente inviato da Ziosilvio

Allora te lo dico in un altro modo.

Considera la somma delle coordinare della casella della matrice.

Se ti muovi di 2 in su o in giù, cambi di 2 il valore dell'ordinata e lasci intatto quello dell'ascissa; quindi, se la somma dell'ascissa e dell'ordinata era pari, rimane pari, e se era dispari, rimane dispari.
Se ti muovi di 2 a destra o a sinistra, cambi di 2 il valore dell'ascissa e lasci intatto quello dell'ordinata; quindi, se la somma dell'ascissa e dell'ordinata era pari, rimane pari, e se era dispari, rimane dispari.
Se ti muovi di 1 in diagonale, cambi di 1 sia l'ascissa che l'ordinata; quindi, se la somma dell'ascissa e dell'ordinata era pari, rimane pari, e se era dispari, rimane dispari.

Ma allora, muovendosi così, puoi andare solo sulle caselle in cui la somma dell'ascissa e dell'ordinata ha la stessa parità che in quella di partenza: e questo copre solo metà della matrice.

Di nuovo: dove sbaglio?

Se parti dalla posizione (5,5), puoi andare in (5,8),(5,2),(2,5),(8,5) orizontale/verticale. (7,7),(7,3),(3,7),(3,3). Vai sia sugli ipotetiche caselle bianche che su quelle nere.