Esercizio sul calcolo della più grande sottomatrice di elementi uguali di una matrice quadrata
Salve a tutti amici del Forum!!!Ho da sottoporre alla vostra gentile attenzione un 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:
CODICE
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:
CODICE
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. Qualcuno di voi è in grado di aiutarmi a trovare la soluzione corretta del problema?
Ringraziandovi sin da ora per l'attenzione che vorrete riservare al mio quesito vi saluto tutti. Ciao!!!
