[ Foro de Pascal ]

matrices

17-Feb-2014 17:26
oscar gomez
16 Respuestas

cordial saludo profesor.
profesor estoy intentando resolver un programa pero tengo dudas en cual seria la forma mas correcta de poderlo realizar y de alguna manera de que forma a traves de tus brillantes ideas puedo conseguirlo.

la idea es que tengo  dos matrices, porejemplo:

A=  1     2     3                  y       B=      5     6     2     1     9
      4    5     6                                      8      1    2     3     10
                                                           11    4    5     6     21
                                                            1     2    3    5       4
                                                            4     5    6    7       8

bien necesito indicar si la matriz A esta contenida en la matriz B, diciendo la cantidad de veces que se encuentra y ademas las posiciones iniciales en las que estas se encuentran
para mi ejemplo el resultado deberia ser: la matriz A si se encuentra dentro de la matriz y se repite 2 veces, desde las posiciones (2,2) y (4,1) respectivamente.


tengo dudas en cual es la mejor forma de hacerlo y por eso acudo a ti para que me des la idea de como realizarlo, pues es que creo que debo hacer 4 fores , dos para el recorrido de la matriz A  y dos para el recorrido de la matriz B, si esto fuera correcto y eficiente, tengo la duda ademas  de como hacer para que cuando encuentre que un elemento de A este contenido en la matriz B siga continuando el proceso para verificar que los siguientes restantes elementos de A se encuentras en B, y como almacenar las posiciones una vez se encuentre que toda la matriz A esta B ...

si puedes hecharme una mano con este ejercicio profesor te lo agradezco inmensamente, es que incluso no se si se pueda utilizar un repeat, o un while a sabiendas de que se lo que hace cada bucle pero en este ejercicio no se que es lo mas conveniente , si puedes ayudarme quiza con algun seudocodigo que me aproxime a la solucion mil gracias por tu ayuda.


18-Feb-2014 22:18
Nacho Cabanes (+32)

Primero una pista: piensa cómo verías si una cadena de texto, como "Esto es bastante fácil" contiene una subcadena, como "tan".

Si consigues eso, que no es demasiado difícil, estarás muy cerca de la solución de tu problema.


18-Feb-2014 23:27
oscar gomez

hola profesor, se a lo que te refieres, en cadenas de texo:

pos.  Indica la posición de una subcadena dentro de una cadena: function pos(subcadena: string; cadena: string): byte; Por ejemplo, pos('Pérez', 'Juan Pérez') devolvería un 6.  Si la subcadena no es parte de la cadena, devuelve 0.

copy.  Devuelve una subcadena.  Su formato es  function copy(cad: string; posic: integer; cuantos: integer): string;  Es decir, le indicamos en qué cadena nos queremos basar, desde qué posición queremos empezar a tomar las letras y cuántas queremos leer.  Así, copy('JUAN PEREZ', 1, 4)  daría 'JUAN'

creo que con estas dos funciones de cadenas podria obtener lo que me mencionas....???

sin embargo disculpame pero no alcanzo a ver la relacion con respecto a mi ejercicio,puesto que no se y corrigeme en este caso se trataria de recorrer e ir mirando si los elementos de A estan en B, y no de posiciones, es que no se lo que intentas indicarme, por favor hechame una mano un poco mas profundizada es que no se como tratar el ejercicio para la solucion, yo pensaba que se trataba de reccorrer la submatriz A e ir mirando si sus elementos estan en B y es lo que no se como hacer, gracias de antemano por lo que puedas ayudarme y disculpame si no veo como pueden ayudarme las funciones de cadena en este caso....


20-Feb-2014 20:59
oscar gomez

Gracias profesor lo pude solucionar y si que tenias razon con tu idea, con ella al final lo consegui muy amable por responder siempre.


23-Feb-2014 12:59
Invitado (Eduardo95)

hola Nacho buenas.
queria preguntarte sobre este ejercicio que vi revizando como hago siempre cada link y me intereso este ejercicio propuesto por oscar y bueno queria pedirte me orientes tu a como puedo solucionarlo pues he leido la propuesta que le sugeriste a oscar pero yo no la entiendo nada, por favor si puedes ayudarme un poco mas a cual es la idea que propones para almenos intentar hacerlo, en lo que puedas ayudarme gracias profesor.


23-Feb-2014 15:51
Nacho Cabanes (+32)

La primera aproximación para ver cómo buscar una submatriz bidimensional dentro de una matriz bidimensional es pensar cómo buscarías una submatriz unidimensional dentro de una matriz unidimensional (o vector).

Dado que una cadena de texto es una caso concreto de matriz de una dimensión, puede ser más sencillo pensar cómo verías si una cadena de texto, como "Esto es bastante fácil" contiene una subcadena, como "tan". Eso es lo que proponía a Oscar.

Una forma de intentarlo puede ser ir mirando cada letra de la cadena ("Esto...") para ver si coincide con la primera letra de la subcadena ("t"): La "E" no es la "t", la "s" tampoco, y así sucesivamente. Eso se puede hacer con un "for". Si encuentras una letra que coincida (la tercera letra sí es una "t"), puedes usar un segundo "for" o un "while" para ver si todas las demás también coinciden.

Intenta una solución y plantéala para que te ayudemos con ella.


23-Feb-2014 20:44
Invitado (Eduardo95)

profesor nacho, me sugieres acaso con tu explicacion que deba tomar las dos matrices como si fueran arreglos, como puedo definir una matriz como un arreglo en pascal y segundo si al hacerlo debo asumir que esos vectores son de contenido string?, no puedo tratarlos como enteros? si puedieras en seudocodigo ayudarme en algo me seria quiza mas facil, gracias pr la ayuda quiero resolverlo como lo ha podido lograr oscar, aunque por lo que veo el tiene mucha mas experiencia que yo por eso te pido me ayudes en lo que a mi pueda servirme gracias


24-Feb-2014 11:44
Invitado (Eduardo95)

Es que de ser asi, no entiendo lo siguiente:
si tengo la submatriz y la matriz:

 
     
A=     1    2             Y la matriz B =        9     8      7      5
         3    4                                             6     1      2      10
                                                              11   3      4      15
                                                              16   7      4       1

al pasar que no se como? a un vector supongo que quedaria:
A= 1    2     3     4
y

B= 9    8     7       5       6       1     2     10       11     3     4      15     16     7     4     1

como recorreria la matriz unidimensional B? si la recorro como si de un vector se tratara no encontraria nunca completa la submatriz A= 1    2     3    4,   o como deberia ser el recorrido en B, gracias por cualquier ayuda.
     


24-Feb-2014 11:48
Nacho Cabanes (+32)

No pienses en convertir un problema en otro. Se trata de empezar por resolver un problema más sencillo, pero que se va a parecer lo suficiente como para ayudarte a entender cómo resolver el problema original.


24-Feb-2014 15:52
Invitado (Eduardo95)

hola profesor, no es que intente convertir un problema en otro solo que es lo que te he entendido, o a caso mis preguntas se desvian total de lo que al final pretendes que sea parte de la solucion, pues primero indicas que se deberia pensar el problema como si de vectores unidimensionales se trataran de ahi mi primera pregunta profesor:

A= 1    2     3     4
y

B= 9    8     7       5       6       1     2     10       11     3     4      15     16     7     4     1

es decir , eso es lo que te entendi en primera instancia es decir ver el problema de esa forma? en que estoy equivocado si no es asi?

ahora si es correcta mi direccion con lo anterior a lo que intentas sugerirme , preguntaba luego que  si deberia tratar ese vector B tal cual o cual seria o deberia ser el recorrido en el pues si lo trato B como un array unidimensional de esa forma nota que A no estaria nunca dentro de B por que sus posiciones serian ahora diferentes, si pudieras ir un poco mas alla profesor te lo agradeceria es que lo de la cadena lo entiendo es decir:

"Una forma de intentarlo puede ser ir mirando cada letra de la cadena ("Esto...") para ver si coincide con la primera letra de la subcadena ("t"): La "E" no es la "t", la "s" tampoco, y así sucesivamente. Eso se puede hacer con un "for". Si encuentras una letra que coincida (la tercera letra sí es una "t"), puedes usar un segundo "for" o un "while" para ver si todas las demás también coinciden. "

pero no se ya llevandolo al terreno que lo quieres llevar y que no veo, como podria ser, si pudieras quiza a traves de un seudocodigo quiza me ayudaria un poco mas es que de otra forma no te comprendo, eso si agradezco infinitamente el tiempo que te tomas para intentar que lo entienda y en ayudarnos.


24-Feb-2014 19:12
Nacho Cabanes (+32)

Insisto. Simplifica.

Crea una función llamada "Contiene", que reciba como parámetro una cadena "contenedor" y otra cadena "contenido" y devuelva un boolean, que será "true" si la cadena contenido aparece dentro del contenedor, y "false" en caso contrario.

Si consigues hacer eso, será fácil extrapolarlo al caso de una matriz bidimensional.


24-Feb-2014 19:54
Invitado (Eduardo95)

gracias nacho, ya lo resolvio el profesor en clase y tienes razon era super facil y corto, aunque de otra forma, pero  gracias de todas formas.


28-Feb-2014 21:54
Invitado (rocioJ)

hola, tienen la solucion, no le entiendo nada de lo que propone el profesor ??? lastima que no lo desarrollaran, cuando por lo que veo hay compañeros que han insistido en la propuesta del profesor, eso desanima  al foro ....?????????


01-Mar-2014 11:15
Nacho Cabanes (+32)

Yo también soy partidario de que quien encuentre una solución la comparta, para que los demás también puedan aprender de ella (aunque siempre insistiré en que se aprende muchísimo más cuando uno lo intenta que cuando lee soluciones de otras personas).

Mi respuesta se refiere a que es más fácil plantear una función como ésta

 
if Contiene('Esto es bastante fácil', 'tan') then ...
 


que hacerlo con matrices de dos dimensiones:

 
if Contiene(matrizGrande, matrizPequena) then ...
 


pero si consigues resolver el primer caso, estarás muy cerca de la solución del segundo. Es la técnica de "divide y vencerás": si consigues descomponer un problema complejo en subproblemas más sencillos, te será más fácil encontrar la solución.

Para el caso de las cadenas de texto, una solución simple (aunque no la más eficiente) sería algo parecido a:

 
funcion Contiene(textoContenedor, textoContenido): boolean
    para i = 1 hasta longitud(textoContenedor) - longitud(textoContenido)
        si textoContenedor[i] = textoContenido[1] (* Si es el principio *)
            (* Compruebo si las n-1 letras siguientes también coinciden *)
            ...
 


La idea es que si nunca llega a aparecer la primera letra de la cadena que se busca, se termina rápidamente; en caso de que aparezca, se analiza si las siguiente también están en orden, bien sea con un "for" (fácil de programar) o con un "while" (más eficiente, porque termina si no coincide alguna de las letras).

En el caso de la matriz de dos dimensiones no es mucho más difícil, pero sí más largo (y, por tanto, más difícil de leer), porque hay que usar dos "for" anidados para comprobar si existe el primer elemento dentro de la matriz "grande" y otros dos "for" anidados (o "while") para ver si los demás también coinciden en ese caso.


01-Mar-2014 18:01
Invitado (rocioJ)

gracias profesor, eres muy amable, me suponia que al pasarlo a matrices seria mas complicado pero ya tengo la idea y la voy a aplicar muchisimas gracias, me gusta este foro


25-Apr-2014 23:48
Invitado (eduardo95)

hola profesor, retomo el link te pido disculpas estuve bastante delicado de salud peor gracias a Dios ya paso y queria poder continuar con este ejercicio esperando tu comprension y ayuda...
queria preguntarte por que en tu sugerencia de codigo haces:
para i = 1 hasta longitud(textoContenedor) - longitud(textoContenido)

por que haces la resta ???

y segundo en lo que mencionas:
(* Compruebo si las n-1 letras siguientes también coinciden *)

podria ser algo asi, sino por FAVOR AYUDAME A CORREGIRMELO te lo agradezco mucho, lo he intentado pero no se hasta que punto puede estar bien mi parte de codigo:

para i = 1 hasta longitud(textoContenedor) - longitud(textoContenido)
       si textoContenedor[i] = textoContenido[1] (* Si es el principio *)
           (* Compruebo si las n-1 letras siguientes también coinciden *):
             begin
j:=2;
        while j<=length(textoContenedor)-i do
                  begin
                       k:=2;
        while k<= length(textoContenido) do
                  if textoContenedor[j] =textoContenido[k] then
     k:=k+1;
                    j:=j+1;
                 end;
             end;


26-Apr-2014 02:27
Luis Torres (+12)

Aquí le dejo una solución a medias del problema en el que muestra la cantidad de veces que aparace la SubMatriz en la Matriz. Como ejercicio extra habrá que buscar en cuáles índices de la Matriz se dan las repeticiones. La clave de la solución fue estudiar muy bien cuáles valores toman los índices de la Matriz con cada valor de la SubMatriz:

 
program VecesSubMatrizEnMatriz;
uses Crt;
const
  Mat: array[1..5,1..5] of integer = ((5,6,2,1,9),
                                      (8,1,2,3,10),
									  (11,4,5,6,21),
									  (1,2,3,5,4),
									  (4,5,6,7,8));
 
  SubMat: array[1..2,1..3] of integer = ((1,2,3),
                                         (4,5,6));
 
var
 k,l,i,j,contador: integer;
 hayElementoDiferente: boolean;
 
procedure MostrarMatriz;
var
 i,j: integer;
Begin
  for i:=1 to 5 do
   begin
     for j:=1 to 5 do
	   write(Mat[i,j]:4);
	 writeln;  
   end;
End;
 
procedure MostrarSubMatriz;
var
 i,j: integer;
Begin
  for i:=1 to 2 do
   begin
     for j:=1 to 3 do
	   write(SubMat[i,j]:4);
	 writeln;  
   end;
End;
 
BEGIN
 ClrScr;
 MostrarMatriz;
 writeln; writeln;
 MostrarSubMatriz;
 contador:= 0;
 for k:=1 to 4 do
  for l:=1 to 3 do
    begin
	  hayElementoDiferente:= false;
	  for i:=1 to 2 do
	   for j:=1 to 3 do
	     begin
		   if SubMat[i,j]<>Mat[i+k-1,j+l-1] then
		     hayElementoDiferente:= true;
		 end;
	  if not(hayElementoDiferente) then
        contador:= contador + 1;	  	
	end;
 writeln; writeln;	
 writeln('La SubMatriz esta contenida ',contador,' veces en la Matriz');
 
 readln;
END.
 


Saludos.






(No se puede continuar esta discusión porque tiene más de dos meses de antigüedad. Si tienes dudas parecidas, abre un nuevo hilo.)