[PASCAL] Esercizio sul calcolo della più grande sottomatrice di una matrice quadrata

[serfabio]

Salve a tutti amici del Forum!!!Ho da sottoporre alla vostra gentile attenzione un'altro piccolo problema che mi dà non pochi grattacapi. Si tratta di un programma redatto in linguaggio Pascal che ha il compito di calcolare la dimensione della più grande sottomatrice quadrata di elementi uguali di una matrice, quadrata anch'essa, letta da ingresso. Il programma, il cui testo riporto in calce a queste righe, risulta sintatticamente corretto ovvero il compilatore (Dev-Pascal) che uso non mi segnala errori. Tuttavia la verifica degli errori a tempo di esecuzione fornisce risultati discordanti; infatti mentre tutto va bene per matrici del tipo:

5 5 5 1
5 5 5 7
5 5 5 6
1 2 4 8

oppure

1 5 8 9
2 2 2 3
2 2 2 6
2 2 2 5

(con numeri ovviamente scelti a caso), con la sottomatrice quadrata in posizione "diversa", ossia "lontana" dalla prima colonna, il programma medesimo non individua la sottomatrice quadrata più grande e mi dà risultato pari ad 1. Forse è sbagliata la procedura CalcolaSottomatrice, che ha il compito di calcolare le varie sottomatrici di elementi uguali fino all'ordine i (con 0<i<k), dimensione delle sottomatrici stesse?
Il codice della procedura è il seguente:

procedure CalcolaSottomatrice(var mat : tipoar); 
var rig,col : integer; 
begin      
       for rig:=1 to i                 
                     do begin                         
                                col:=1;                         
                                finito:=true;                                   
                                while(col>=1)and(col<=i)and(finito)                         
                                do begin                                 
                                           for l:=rig to i                                            
                                                do begin
                                                           m:=col;
                                                           while(m>=col)and(m<=i)and(finito)
                                                           do begin if(mat[rig,col]<>mat[l,m])
                                                                       then finito:=false;
                                                           m:=m+1;
                                                    end;
                                            end;
                                col:=col+1;
                           end;
                   end;
end;(* fine procedura CalcolaSottomatrice *)

L'idea della soluzione proposta da me è la seguente: calcolare le sottomatrici quadrate della matrice di ordine k dalla dimensione 1 fino appunto a k, e mediante il ciclo while interno alla procedura CalcolaSottomatrice, associare il valore "true" a quelle tali che ogni elemento è uguale, e "false" alle altre, e poi riempire un vettore v di dimensione k, con elemento v[i] corrispondente alla dimensione i della sottomatrice (con 1<i<k) e tale che v[i]=i se la variabile di controllo finito=true, v[i]=0 altrimenti. In questo modo il calcolo della massima dimensione della sottomatrice quadrata si riduce al calcolo del massimo del vettore v.
Ecco il testo completo del programma:

program Minori(input,output);
(* Legge una matrice quadrata di interi e calcola la dimensione dalla più grande
sottomatrice quadrata con elementi uguali *)
label 99;
const n=10;
type tipoar=array[1..n,1..n]of integer;
var a : tipoar;
    v: array[1..n]of integer;
    i,k,l,m,max : integer;
    finito : boolean;

procedure LeggiEScriviMat(var mat : tipoar);
var rig,col : integer;
begin
     writeln('fornire gli elementi della matrice, ciascuno seguito da un <INVIO>:');
     writeln;
     for rig:=1 to k
                do for col:=1 to k
                             do readln(mat[rig,col]);
     writeln;
     for rig:=1 to k
                do begin
                        for col:=1 to k
                                   do write(' ',mat[rig,col],' ':3);
                        writeln;
                   end;
end;(* fine procedura LeggiEScriviMat *)
procedure CalcolaSottomatrice(var mat : tipoar);
var rig,col : integer;
begin
     for rig:=1 to i
                do begin
                        col:=1;
                        finito:=true;
                        while(col>=1)and(col<=i)and(finito)
                        do begin
                                for l:=rig to i
                                           do begin
                                                 m:=col;
                                                 while(m>=col)and(m<=i)and(finito)
                                                 do begin if(mat[rig,col]<>mat[l,m])
                                                          then finito:=false;
                                                          m:=m+1;
                                                    end;
                                            end;
                                col:=col+1;
                           end;
                   end;
end;(* fine procedura CalcolaSottomatrice *)

begin(*programma principale *)

  write('fornire la dimensione della matrice: ');
  readln(k);
  writeln;
  if k>n then begin
                   writeln('dimensione troppo grande della matrice! - STOP -');
                   goto 99;
              end
         else begin
                   LeggiEScriviMat(a);
                   for i:=1 to k
                            do begin
                                    CalcolaSottomatrice(a);
                                    if finito
                                    then v[i]:=i
                                    else v[i]:=0;
                               end;
                   writeln;
                   for i:=1 to k
                            do write(' ',v[i],' ':3);
                   writeln;
                   max:=v[1];
                   for i:=1 to k
                            do if v[i]>max
                               then max:=v[i];
                   writeln;
                   write('La dimensione della piu'' grande sottomatrice di elementi uguali e'': ');
                   writeln(max);
              end;
  99 :
  readln;

end.

A scopo di verifica ho inserito anche la visualizzazione del vettore v. Ringraziandovi sin da ora per l'attenzione che vorrete riservare al mio problema vi saluto tutti. Ciao!!!

[serfabio]

Ho provato una soluzione alternativa al problema, eliminando il vettore v e usando una variabile contatore "conta", che ha il compito di calcolare la dimensione massima della più grande sottomatrice quadrata della matrice data, e ho usato una function in luogo di una procedura. Però il risultato è il medesimo. Grazie per l'aiuto che vorrete darmi. Il codice della soluzione alternativa lo trovate qui sotto:

program Minori(input,output);
(* Legge una matrice quadrata di interi e calcola la dimensione dalla più grande
sottomatrice quadrata con elementi uguali *)
label 99;
const n=10;
type tipoar=array[1..n,1..n]of integer;
var a : tipoar;
    i,k,l,m,conta : integer;
    finito : boolean;

procedure LeggiEScriviMat(var mat : tipoar);
var rig,col : integer;
begin
     writeln('fornire gli elementi della matrice, ciascuno seguito da un <INVIO>:');
     writeln;
     for rig:=1 to k
                do for col:=1 to k
                             do readln(mat[rig,col]);
     writeln;
     for rig:=1 to k
                do begin
                        for col:=1 to k
                                   do write(' ',mat[rig,col],' ':3);
                        writeln;
                   end;
end;(* fine procedura LeggiEScriviMat *)
function CalcolaSottomatrice(var mat : tipoar): boolean;
var rig,col : integer;
begin
     for rig:=1 to k-i+1
                do begin
                      col:=1;
                      finito:=true;
                      while(col>=1)and(col<=k-i+1)and(finito)
                      do begin
                              for l:=rig to rig+i-1
                                         do begin
                                                 m:=col;
                                                 while(m>=col)and(m<=col+i-1)and(finito)
                                                 do begin if(mat[rig,col]<>mat[l,m])
                                                          then finito:=false;
                                                          m:=m+1;
                                                    end;
                                            end;
                                col:=col+1;
                         end;
                   end;
     CalcolaSottomatrice:=finito;
end;(* fine CalcolaSottomatrice *)

begin(*programma principale *)

  write('fornire la dimensione della matrice: ');
  readln(k);
  writeln;
  if k>n then begin
                   writeln('dimensione troppo grande della matrice! - STOP -');
                   goto 99;
              end
         else begin
                   LeggiEScriviMat(a);
                   for i:=1 to k
                            do begin
                                    conta:=0;
                                    CalcolaSottomatrice(a);
                                    if(finito)
                                    then conta:=conta+1;
                               end;
                   writeln;
                   writeln('La dimensione della piu'' grande sottomatrice di elementi uguali e'': ',conta);
              end;
  99 :
  readln;

end.

Ciao a tutti!!!

[serfabio]

Scusate amici del Forum...Ho commesso un errore!!! Infatti per introdurre nel programma Minori la function CalcolaSottomatrice, devo definire la variabile h di tipo "boolean" e, poi, inserire la corretta istruzione h:=CalcolaSottomatrice(a) nel programma principale. Il testo completo, sintatticamente corretto è dunque:

program Minori(input,output);
(* Legge una matrice quadrata di interi e calcola la dimensione dalla più grande
sottomatrice quadrata con elementi uguali *)
label 99;
const n=10;
type tipoar=array[1..n,1..n]of integer;
var a : tipoar;
    i,k,conta : integer;
    finito,h : boolean;

procedure LeggiEScriviMat(var mat : tipoar);
var rig,col : integer;
begin
     writeln('fornire gli elementi della matrice, ciascuno seguito da un <INVIO>:');
     writeln;
     for rig:=1 to k
                do for col:=1 to k
                             do readln(mat[rig,col]);
     writeln;
     for rig:=1 to k
                do begin
                        for col:=1 to k
                                   do write(' ',mat[rig,col],' ':3);
                        writeln;
                   end;
end;(* fine procedura LeggiEScriviMat *)
function CalcolaSottomatrice(var mat : tipoar): boolean;
var rig,col,l,m : integer;
begin
     for rig:=1 to k-i+1
                do begin
                      col:=1;
                      finito:=true;
                      while(col>=1)and(col<=k-i+1)and(finito)
                      do begin
                              for l:=rig to rig+i-1
                                         do begin
                                                 m:=col;
                                                 while(m>=col)and(m<=col+i-1)and(finito)
                                                 do begin if(mat[rig,col]<>mat[l,m])
                                                          then finito:=false;
                                                          m:=m+1;
                                                    end;
                                            end;
                             col:=col+1;
                         end;
                   end;
     CalcolaSottomatrice:=finito;
end;(* fine CalcolaSottomatrice *)

begin(*programma principale *)

  write('fornire la dimensione della matrice: ');
  readln(k);
  writeln;
  if k>n then begin
                   writeln('dimensione troppo grande della matrice! - STOP -');
                   goto 99;
              end
         else begin
                   LeggiEScriviMat(a);
                   for i:=1 to k
                            do begin
                                    conta:=0;
                                    h:=CalcolaSottomatrice(a);
                                    if(h)
                                    then conta:=conta+1;
                               end;
                   writeln;
                   writeln('La dimensione della piu'' grande sottomatrice di elementi uguali e'': ',conta);
              end;
  99 :
  readln;

end.

In esso ho corretto anche gli estremi dei cicli ricorsivi all'interno della funzione CalcolaSottomatrice.
Tuttavia il programma NON FUNZIONA ANCORA (ora la dimensione massima della più grande sottomatrice quadrata di elementi uguali risulta sempre pari a 0!!!), e non riesco a capire il perchè...Ciao a Tutti!!!

[serfabio]

...ovviamente mat va dichiarato, nella funzione Calcolasottomatrice, come parametro per valore e non per variabile (mannaggia il copia-incolla...)!!!

[serfabio]

E' meglio scrivere

 ....
else begin
                   LeggiEScriviMat(a);
                   conta:=0;
                   for i:=1 to k
                            do begin
                                    h:=CalcolaSottomatrice(a);
                                    if(h)
                                    then conta:=i;
                               end;
                   writeln;
                   writeln('La dimensione della piu'' grande sottomatrice di elementi uguali e'': ',conta);
              end;

....

altrimenti la variabile conta viene azzerata ad ogni occorrenza del ciclo for.

[Rising1]

MONOLOGHI
A VOLTE è MEGLIO FARLI NEI FORUM

[serfabio]

...cerco solo di fornire il maggior numero possibile di informazioni a tutti coloro che avranno la bontà di aiutarmi nella soluzione del problema che ho proposto. Poi ...se nessuno risponde...non posso farci nulla...

[serfabio]

A beneficio di tutti i frequentatori del forum che fossero interessati, ecco la corretta soluzione del problema:

program SottoMatriceOmogenea(input,output);
(* Legge una matrice quadrata di interi e calcola la dimensione dalla più grande
sottomatrice quadrata con elementi uguali *)

label 99;
const n = 10;

type tipoar = array[1..n, 1..n] of integer;

var mat : tipoar;
    k: integer;

procedure LeggiEScriviMat();
var rig,col : integer;
begin
	writeln('inserire elementi separati da uno spazio, una riga alla volta, ciascuna terminata da <INVIO>:');
	writeln;
	for rig := 1 to k do
		begin
			for col := 1 to k do read(mat[rig,col]);
			readln
		end;
     writeln;
     for rig :=1 to k do 
     	begin
     		for col := 1 to k do write(' ',mat[rig,col]:5,' ');
     		writeln
     	end;
end;(* fine procedura LeggiEScriviMat *)


function SottoMatriceOmogenea(riga0, col0, dim: integer): boolean; 
{ restituisce true se e solo se la sottomatrice dim x dim avente elem in alto a sx in posiz 
  (riga0, col0) è omogenea, cioè è costituita da elementi eguali }
var i, j, temp: integer;
begin
	temp := mat[riga0, col0];
	SottoMatriceOmogenea := true;
	for i := riga0 to riga0 + dim - 1 do
		for j := col0 to col0 + dim - 1 do
			if mat[i, j] <> temp then SottoMatriceOmogenea := false
end;

function CalcolaSottomatrice(d: integer): boolean;
{ restituisce true se e solo se mat ha una sottomatrice omogena di ordine d }
var i, j: integer;
	uscitaRapida : boolean;
begin
	uscitaRapida := false;
	i := 1;
	while (i <= k - d + 1) and not uscitaRapida do 
		begin
			j := 1;
			while (j <= k - d + 1) and not uscitaRapida do
				begin
					uscitaRapida := SottoMatriceOmogenea(i, j, d);
					j := j +1
				end;
			i := i + 1
		end;
	CalcolaSottomatrice := uscitaRapida
end;(* fine CalcolaSottomatrice *)

var conta, d: integer;

begin(*programma principale *)
	write('fornire la dimensione della matrice: ');
	readln(k);
	writeln;
	if k > n then 
		begin
			writeln('dimensione troppo grande della matrice! - STOP -');
			goto 99
        end
    else 
    	begin
    		LeggiEScriviMat();
    		conta := 0;
    		for d := 1 to k do 
    			if CalcolaSottomatrice(d) then conta := d;
    		writeln;
    		writeln('La dimensione della piu'' grande sottomatrice di elementi uguali e'': ',conta)
    	end;
    
    99 :
    readln

end.

Grazie a tutti per la collaborazione. Ciao!!!