(Programma C) Un quadrato nella matrice - Revision history

Eddy: /* Altre considerazioni e un'altra soluzione (rd) */

2014-11-10T22:17:25Z

Altre considerazioni e un'altra soluzione (rd)

Eddy: /* Altre considerazioni e un'altra soluzione (rd) */

2014-11-10T22:15:45Z

Altre considerazioni e un'altra soluzione (rd)

Eddy: /* Altre considerazioni e un'altra soluzione (rd) */

2014-11-10T21:56:27Z

Altre considerazioni e un'altra soluzione (rd)

Eddy: /* Altre considerazioni e un'altra soluzione (rd) */

2014-11-10T20:22:01Z

Altre considerazioni e un'altra soluzione (rd)

Eddy: /* Altre considerazioni e un'altra soluzione (rd) */

2014-11-10T20:11:41Z

Altre considerazioni e un'altra soluzione (rd)

Nat: /* Soluzione di Nat (corretta) */

2014-11-09T17:47:42Z

Soluzione di Nat (corretta)

Nat: /* Soluzione di Nat */

2014-11-09T17:05:49Z

Soluzione di Nat

Nat: /* Soluzione di Nat (corretta)*/

2014-11-09T15:17:39Z

Soluzione di Nat (corretta)

Renzo: /* Altre considerazioni e un'altra soluzione (rd) */

2014-11-06T19:31:09Z

Altre considerazioni e un'altra soluzione (rd)

Renzo: /* Altre considerazioni e un'altra soluzione (rd) */

2014-11-06T19:30:44Z

Altre considerazioni e un'altra soluzione (rd)

@@ Line 475: / Line 475: @@
          /*Angolo in basso a destra*/
          find=0;
-         for (i=n; i>=0; i--){
+         for (i=n-1; i>=0; i--){
-             for (j=n; j>=0 && !find; j--){ // controllo per righe
+             for (j=n-1; j>=0 && !find; j--){ // controllo per righe
                  if (M[i][j]=='#'){
                      bdx.x=i;

@@ Line 453: / Line 453: @@
          /*Angolo in alto a destra*/
          find=0;
-         for (i=n; i>=0; i--){
+         for (i=n-1; i>=0; i--){
              for (j=0; j<n && !find; j++){
                  if (M[j][i]=='#'){ // scambio indici, controllo per colonne
-                     adx.x=i;
+                     adx.x=j;
-                     adx.y=j;
+                     adx.y=i;
                      find=1;
+                 }
@@ Line 465: / Line 465: @@
          find=0;
          for (i=0; i<n; i++){
-             for (j=n; j>=0 && !find; j--){
+             for (j=n-1; j>=0 && !find; j--){
                  if (M[j][i]=='#'){ // scambio indici, controllo per colonne
-                     bsx.x=i;
+                     bsx.x=j;
-                     bsx.y=j;
+                     bsx.y=i;
                      find=1;
+                 }

← Older revision		Revision as of 21:56, 10 November 2014
Line 597:		Line 597:

	[[User:Renzo\|Renzo]] ([[User talk:Renzo\|talk]]) 20:30, 6 November 2014 (CET)		[[User:Renzo\|Renzo]] ([[User talk:Renzo\|talk]]) 20:30, 6 November 2014 (CET)
		+
		+
		+	''Funzionamento''
		+	<source lang=C>
		+	#include<stdio.h>
		+	#include<stdlib.h>
		+
		+	void error_n_die(char *s)
		+	{
		+	fprintf(stderr,"Error %s\n",s);
		+	exit(1);
		+	}
		+
		+	/* funzione che "si mangia" quel che resta della riga
		+	per portare l'indicatore di posizione del file alla riga successiva */
		+	void flushtonl(FILE *fin)
		+	{
		+	int c;
		+	while ((c=fgetc(fin)) != '\n' && c!=EOF)
		+	;
		+	}
		+
		+	int isacube(FILE *fin)
		+	{
		+	int dim,i,j,c;
		+	/* rappresentano rispettivamente la prima riga, l'ultima riga,
		+	prima colonna, ultima colonna del quadrato */
		+
		+	int mini,maxi,minj,maxj;
		+	fscanf(fin,"%d",&dim);
		+	flushtonl(fin);
		+	mini=maxi=minj=maxj=-1;
		+	for (i=0; i<dim+1; i++) {
		+	int n=0; // credo sia superfluo
		+	for (j=0; j<dim+1; j++) {
		+	c=(i<dim && j<dim)?fgetc(fin):'.';
		+
		+	/* partendo da "in alto a sinistra" se non ho ancora trovato la prima riga */
		+	if (mini<0) {
		+	if (c=='#') {
		+	/* so che e` la prima colonna */
		+	if (minj<0) minj=j;
		+	} else {
		+	/* se sono qui, vuol dire che ho gia` trovato la prima colonna e c=='.'
		+	ho trovato l'ultima colonna (era la precedente) e setto prima riga */
		+	if (minj>=0) maxj=j-1,mini=i;
		+	}
		+	/* ho gia` trovato la prima riga, la prima colonna e l'ultima colonna
		+	mi manca solo l'ultima riga */
		+	} else if (maxi<0) {
		+	/* entrero` qui soltanto se:
		+	1. c=='.' e sono nel range delle colonne
		+	2. c=='#' e sono fuori dal range delle colonne */
		+	if (c!='#' ^ (j < minj \|\| j > maxj))
		+	/* casi di errore:
		+	1. se c=='#' c'e` un '#' fuori dal quadrato
		+	2. e` stato aggiunto j != minj, poiche` non verrebbe riconosciuto
		+	##
		+	#. */
		+	if (c == '#' \|\| j != minj)
		+	mini=maxi=minj=maxj=dim;
		+	else
		+	maxi=i-1; // trovato ultima riga
		+	} else {
		+	/* trovato un "#" al di fuori del quadrato */
		+	if (c=='#')
		+	mini=maxi=minj=maxj=dim;
		+	}
		+	}
		+	if (i<dim) flushtonl(fin);
		+	}
		+	/* controllo che le dimensioni siano stato rispettate */
		+	return maxj-minj == maxi-mini && mini>=0 && maxi<dim;
		+	}
		+
		+	int main(int argc, char *argv[])
		+	{
		+	FILE *fin;
		+	int ncases;
		+	int i;
		+
		+	if ((fin=fopen("input.txt","r")) == NULL)
		+	error_n_die("opening file");
		+	fscanf(fin,"%d",&ncases);
		+	if (ncases>20 \|\| ncases<1) error_n_die("not valid # of cases");
		+	for (i=0;i<ncases;i++)
		+	printf("case #%d: %s\n",i,isacube(fin)?"YES":"NO");
		+	return 0;
		+	}
		+	</source>
		+
		+	[[User:Eddy\|Eddy]] ([[User talk:Eddy\|talk]]) 23:15 Monday, 10 November 2014 (CET)

@@ Line 486: / Line 486: @@
 </source>
--Eddy
+[[User:Eddy|Eddy]] ([[User talk:Eddy|talk]]) 21:40 Monday, 10 November 2014 (CET)
 La soluzione di Nat invece funziona dal punto di vista algoritmico. Lui controlla che il numero di # sia un quadrato perfetto N^2 e quindi controlla che a partire dal primo # che si incontra scandendo la matrice in senso lessicografico tutti gli elementi nel quadrato a destra e in basso di lato N siano '#'.

@@ Line 438: / Line 438: @@
 </pre>
 vi dice che e' un quadrato. Si potrebbe correggere il programma cambiando il modo per cercare i vertici... '''come'''?
 La soluzione di Nat invece funziona dal punto di vista algoritmico. Lui controlla che il numero di # sia un quadrato perfetto N^2 e quindi controlla che a partire dal primo # che si incontra scandendo la matrice in senso lessicografico tutti gli elementi nel quadrato a destra e in basso di lato N siano '#'.

@@ Line 172: / Line 172: @@
 Il codice che posto qui di seguito verifica che nella matrice presa in input da file ci sia un quadrato pieno, ma attraverso controlli diversi rispetto al codice precedente e con una matrice allocata dinamicamente (si possono passare in input matrici più grandi di 20*20).
-Il programma prende in input un file in questa forma
+Il programma prende lo stesso input della consegna postata da LorenzoV.
-<source lang="text">
 Se compilate con gcc va aggiunto  il flag -lm perchè con la libreria math.h (per la radice quadrata) ci sono problemi. <br>
 Es. gcc main.c -o programma -lm
 <source lang="c">
 #include <stdio.h>
 #include <stdlib.h>
@@ Line 194: / Line 185: @@
+{
      	FILE *text;
-     	int n,i,j,counter,tmp,isx,jsx,boole;
+     	int n,i,j,k,counter,tmp,isx,jsx,boole,cases; int* vect;
-	double squaroot; counter=0;
+	double squaroot; ;cases=0;
 	text=fopen("input.txt","r");
      	if(text==NULL)
@@ Line 204: / Line 196: @@
+     	}
 	/*Leggo la dimensione n della matrice in input*/
      	fscanf(text,"%d",&n);
-     	printf("%d \n",n);
+     	printf("n=%d \n",n);
 	/*Alloco una matrice M e un vettore r, che mi serve
 	 per copiare l'input su M.
@@ Line 256: / Line 264: @@
 			/*Ho risolto il problema del "quadrato di lato 0"
 			con un controllo sul counter dei cancelletti totali*/
-			squaroot=sqrt(counter);
+	squaroot=sqrt(counter);
-	if(squaroot!=(int)squaroot||counter==0)
+	{
-		printf("\nThere isn't any square.\n");
+		printf("\nThere isn't any square.\n\n");
-		exit(1);
+		vect[k]=0;
+	}
@@ Line 269: / Line 279: @@
 			/*Ho risolto il goto con una variabile
-			booleana che cambia di valore nel momento
+			booleana che cambia valore nel momento
-			in cui trovo il primo cancelletto */
+			in cui trovo il primo cancelletto.
 	boole=1;
@@ Line 292: / Line 305: @@
 			/*Ho risolto il segmentation fault controllando
 			che la mia visita della matrice non esca dal range n
 			oltre che dal range del lato del quadrato.
-                         Sottraggo 1 a i e j poichè nel momento in cui
+			Sottraggo 1 a i e j poichè nel momento in cui
-                         boole cambia valore i cicli incrementano di 1 gli indici.*/
+                        boole cambia valore i cicli incrementano di 1 gli indici.*/
 	isx=i-1; jsx=j-1; tmp=counter;
 	for(i=isx;i<(isx+(int)squaroot)&&i<n;i++)
+	{
@@ Line 307: / Line 321: @@
 	if(tmp==0)
-	printf("\n\nThere is a square! :D\n\n");
+	{printf("\nThere is a square! :D\n\n");
 	else
-	printf("\n\nThere isn't any square!\n\n");
+	{printf("\nThere isn't any square!\n\n");
 	fclose(text);
+}
 </source>

@@ Line 194: / Line 194: @@
+{
      	FILE *text;
-     	int n,i,j,counter,tmp,isx,jsx,bool;
+     	int n,i,j,counter,tmp,isx,jsx,boole;
 	double squaroot; counter=0;
 	text=fopen("input.txt","r");
@@ Line 272: / Line 272: @@
 			in cui trovo il primo cancelletto */
-	bool=1;
+	boole=1;
-	for(i=0;i<n&&bool;i++)
+	for(i=0;i<n&&boole;i++)
+	{
-        		 for(j=0;j<n&&bool;j++)
+        		 for(j=0;j<n&&boole;j++)
+         	{
              		if(M[i][j]=='#')
-             			bool=0;
+             			boole=0;
+         	}
+	}
@@ Line 292: / Line 292: @@
 			/*Ho risolto il segmentation fault controllando
 			che la mia visita della matrice non esca dal range n
-			oltre che dal range del lato del quadrato.*/
+			oltre che dal range del lato del quadrato.
-	isx=i; jsx=j; tmp=counter;
+                         Sottraggo 1 a i e j poichè nel momento in cui
 	for(i=isx;i<(isx+(int)squaroot)&&i<n;i++)
+	{

@@ Line 186: / Line 186: @@
 Es. gcc main.c -o programma -lm
 <source lang="c">
 #include <stdio.h>
 #include <stdlib.h>
@@ Line 192: / Line 193: @@
 int main()
+{
      	FILE *text;
-     	int n,i,j,counter,tmp,isx,jsx;
+     	int n,i,j,counter,tmp,isx,jsx,bool;
 	double squaroot; counter=0;
 	text=fopen("input.txt","r");
-−
      	if(text==NULL)
+     	{
@@ Line 205: / Line 206: @@
 	/*Leggo la dimensione n della matrice in input*/
      	fscanf(text,"%d",&n);
+    	printf("%d \n",n);
 	/*Alloco una matrice M e un vettore r, che mi serve
 	 per copiare l'input su M.
@@ Line 229: / Line 230: @@
 	               M[i][j]=r[j];
+	}
 	/*Stampa matrice*/
 	for (i=0; i<n; ++i)
@@ Line 237: / Line 239: @@
 		printf("\n");
+	}
 	/*Conto i cancelletti*/
 	for (i=0; i<n; ++i)
@@ Line 246: / Line 249: @@
+		}
+	}
 	/*Logicamente si ha che se il numero
 	di cancelletti non è un numero quadrato
 	allora la matrice non potrà mai contenere un quadrato pieno.*/
-	squaroot=sqrt(counter);
-	if(squaroot!=(int)squaroot)
+			/*Ho risolto il problema del "quadrato di lato 0"
+	{
 		printf("\nThere isn't any square.\n");
@@ Line 260: / Line 267: @@
 	in alto a sinistra del
 	mio potenziale quadrato*/
-	for(i=0;i<n;i++)
+	bool=1;
+	{
-        		 for(j=0;j<n;j++)
+        		 for(j=0;j<n&&bool;j++)
+         	{
              		if(M[i][j]=='#')
-             			goto final;
+             			bool=0;
+         	}
+	}
@@ Line 272: / Line 284: @@
 	/*Valuto solo la parte di matrice
 	che inizia con il mio angolo sx
-	, "spazzolo" solo per la lunghezza
+	e "spazzolo" solo per la lunghezza
 	del mio lato(radice quadrata del numero di cancelletti)
 	e scalo il numero dei cancelletti: se alla fine sono 0 vuol dire
@@ Line 278: / Line 290: @@
 	Quindi è un quadrato pieno. */
-	final:
+			/*Ho risolto il segmentation fault controllando
 	isx=i; jsx=j; tmp=counter;
+	for(i=isx;i<(isx+(int)squaroot)&&i<n;i++)
+	{
-	        for(j=jsx;j<(jsx+(int)squaroot);j++)
+	        for(j=jsx;j<(jsx+(int)squaroot)&&j<n;j++)
+	        {
 	            if(M[i][j]=='#')
@@ Line 297: / Line 310: @@
 	fclose(text);
+}
 </source>
 --[[User:Nat|Nat]] ([[User talk:Nat|talk]]) 18:05, 2 November 2014 (CET)
 == Soluzione di rd ==

@@ Line 498: / Line 498: @@
 ''c'era un bug. Ho corretto il confronto di riga 36 da "if (c == '#')" a "if (c == '#' || j != minj)"''.
-'''Chi riesce a trovare il caso che non veniva correttamente riconosciuto? (spigando il perch&eacute;!)'''
+'''Chi riesce a trovare il caso che non veniva correttamente riconosciuto? (spiegando il perch&eacute;!)'''
 [[User:Renzo|Renzo]] ([[User talk:Renzo|talk]]) 20:30, 6 November 2014 (CET)